Conjuntos "gruesos" de enteros y números de Fibonacci

SUGERENCIA: Observe que cada subconjunto gordo de$\{1,\dots,n\}$es automáticamente un subconjunto gordo de$\{1,\dots,n+1\}$; eso da cuenta$f(n)$subconjuntos de grasa de$\{1,\dots,n+1\}$, por lo que solo necesita mostrar que hay$f(n-1)$subconjuntos de grasa de$\{1,\dots,n+1\}$que no son ya subconjuntos gordos de$\{1,\dots,n\}$. Claramente esos deben ser los subconjuntos gordos de$\{1,\dots,n+1\}$que incluye$n+1$. En este punto, puede que no sea una mala idea recopilar algunos datos enumerando los subconjuntos gordos de$\{1,\dots,n\}$para algunos pequeños valores de$n$:

$$\begin{array}{c|l} n&\text{Fat subsets}\\ \hline 0&\varnothing\\ 1&\varnothing,\{1\}\\ 2&\varnothing,\{1\},\{2\}\\ 3&\varnothing,\{1\},\{2\},\{3\},\{2,3\}\\ 4&\varnothing,\{1\},\{2\},\{3\},\{2,3\},\{4\},\{2,4\},\{3,4\}\\ 5&\varnothing,\{1\},\{2\},\{3\},\{2,3\},\{4\},\{2,4\},\{3,4\},\{5\},\{2,5\},\{3,5\},\{4,5\},\{3,4,5\} \end{array}$$

Ahora intente hacer coincidir los nuevos conjuntos en cada línea con los conjuntos dos líneas atrás:

$$\begin{array}{c|l|c|l} n&\text{Fat subsets}&n+2&\text{New fat subsets}\\ \hline 0&\varnothing&2&\{2\}\\ 1&\varnothing,\{1\}&3&\{3\},\{2,3\}\\ 2&\varnothing,\{1\},\{2\}&4&\{4\},\{2,4\},\{3,4\}\\ 3&\varnothing,\{1\},\{2\},\{3\},\{2,3\}&5&\{5\},\{2,5\},\{3,5\},\{4,5\},\{3,4,5\}\\ \end{array}$$

Si observa esa tabla por un momento, debería poder ver cómo derivar los nuevos subconjuntos gordos de$\{1,\dots,n+1\}$, los que no son subconjuntos gordos de$\{1,\dots,n\}$, de los subconjuntos gordos de$\{1,\dots,n-1\}$. Una vez que lo ves, probar que es correcto no es demasiado difícil.

Este problema tiene una solución simple utilizando funciones generadoras ordinarias.

Observe que la función generadora de subconjuntos de$\{k, n\}$indexado por número de elementos ($u$) y la suma total ($x$) por inspección se ve que es

$$\prod_{m=k}^n (1+ux^m).$$ Por lo tanto, la función generadora de los conjuntos considerados es $$\sum_{k=0}^n [u^k] \prod_{m=k}^n (1+ux^m)$$ dónde$[u^k]$es el operador de extracción de coeficientes.

Para nuestros propósitos, no necesitamos el parámetro de suma de esta función generadora, por lo que podemos establecerlo en uno, obteniendo

$$\sum_{k=0}^n [u^k] \prod_{m=k}^n (1+u) = \sum_{k=0}^n [u^k] (1+u)^{n-k+1} = \sum_{k=0}^n {n-k+1\choose k}.$$

Ahora calcularemos la función generadora$f(z)$de esta suma, obteniendo

$$f(z) = \sum_{n\ge 0} z^n \sum_{k=0}^n {n-k+1\choose k} = \sum_{k\ge 0} \sum_{n\ge k} {n-k+1\choose k} z^n = \sum_{k\ge 0} \sum_{n\ge 0} {n+1\choose k} z^{n+k} \\= \frac{1}{1-z} + \sum_{k\ge 1} \sum_{n\ge 0} {n+1\choose k} z^{n+k} = \frac{1}{1-z} + \sum_{k\ge 1} \sum_{n\ge k-1} {n+1\choose k} z^{n+k} \\= \frac{1}{1-z} + \sum_{k\ge 1} \sum_{n\ge 0} {n+k\choose k} z^{n+2k-1} = \frac{1}{1-z} + \sum_{k\ge 1} z^{2k-1} \sum_{n\ge 0} {n+k\choose k} z^n \\= \frac{1}{1-z} + \sum_{k\ge 1} z^{2k-1} \frac{1}{(1-z)^{k+1}} = \frac{1}{1-z} + \frac{1}{1-z} \frac{1}{z} \sum_{k\ge 1} z^{2k} \frac{1}{(1-z)^k} \\ = \frac{1}{1-z} + \frac{1}{1-z} \frac{1}{z} \frac{z^2/(1-z)}{1-z^2/(1-z)} = \frac{1}{1-z} + \frac{1}{1-z} \frac{1}{z} \frac{z^2}{1-z-z^2}.$$ Esto finalmente se simplifica a $$\frac{1}{1-z} \left(1 + \frac{z}{1-z-z^2}\right) = \frac{1}{1-z} \frac{1-z-z^2 + z}{1-z-z^2} = \frac{1+z}{1-z-z^2}.$$

Ahora recuerda que la función generadora de los números de Fibonacci está dada por

$$\frac{z}{1-z-z^2}$$ y por lo tanto $$[z^n] \frac{1+z}{1-z-z^2} = F_{n+1} + F_n = F_{n+2}.$$

Apéndice. Una evaluación alternativa del OGF procede de la siguiente manera:

$$f(z) = \sum_{n\ge 0} z^n [w^{n+1}] (1+w)^{n+1} \sum_{k\ge 0} \frac{w^{2k}}{(1+w)^k} \\ = \frac{1}{z} \sum_{n\ge 0} z^{n+1} [w^{n+1}] (1+w)^{n+1} \frac{1}{1-w^2/(1+w)} \\ = \frac{1}{z} \sum_{n\ge 0} z^{n+1} [w^{n+1}] (1+w)^{n+2} \frac{1}{1+w-w^2}.$$

La contribución de$w$es

$$\;\underset{w}{\mathrm{res}}\; \frac{1}{w^{n+2}} (1+w)^{n+2} \frac{1}{1+w-w^2}.$$

Ahora pon$w/(1+w)=v$de modo que$w = v/(1-v)$y$dw = 1/(1-v)^2 \; dv$Llegar

$$\;\underset{v}{\mathrm{res}}\; \frac{1}{v^{n+2}} \frac{1}{1+v/(1-v)-v^2/(1-v)^2} \frac{1}{(1-v)^2}.$$

Esto da para el OGF

$$\frac{1}{z} \sum_{n\ge 0} z^{n+1} [v^{n+1}] \frac{1}{(1-v)^2+v(1-v)-v^2} \\ = \frac{1}{z} \sum_{n\ge 0} z^{n+1} [v^{n+1}] \frac{1}{1-v-v^2} = \frac{1}{z} \left[ -1 + \frac{1}{1-z-z^2} \right] \\ = \frac{1}{z} \frac{z+z^2}{1-z-z^2} = \frac{1+z}{1-z-z^2},$$

lo mismo de antes.

Pista: haría esto justificando las siguientes tres afirmaciones.

1. Un subconjunto gordo de$\{1,2,\ldots,n-1\}$es también un subconjunto gordo de$\{1,2,\ldots,n\}$.
2. Si$X$es un subconjunto gordo de$\{1,2,\ldots,n-2\}$, entonces el conjunto $$X_+=\{n\}\cup\{t+1\mid t\in X\}$$ es un subconjunto gordo de$\{1,2,\ldots,n\}$.
3. Si un subconjunto gordo$S\subseteq\{1,2,\ldots,n\}$satisface$n\in S$, entonces$S=X_+$para algún subconjunto gordo$X$de$\{1,2,\ldots,n-2\}$.