Ordenado las particiones de un entero (con un giro)

Question

Me gustaría saber cómo probar (preferiblemente en forma algebraica) que $P_1(2,n)=F_{2n+1}$ donde $P_1(2,n)$ es lo que yo defino como el número de ordenadas las particiones de un entero, donde el número de $1$ tiene 2 colores posibles. Por ejemplo, \begin{align} 2 &=2\\ &={\color\red{1}}+{\color\red{1}}\\ &={\color\green{1}}+{\color\green{1}}\\ &={\color\green{1}}+{\color\red{1}}\\ &={\color\red{1}}+{\color\green{1}}\\ \end{align} así que en este caso, $P_1(2,2)=5$.

Este es mi (fallido) intento de derivar una fórmula para $P_1(k,n)$. Considere un caso donde el número de $n$ se expresa como una suma de $m$ números naturales, de los cuales hay $j$ número de $1$s. El número de posibles formas de hacerlo es dada por $$\binom{m}{j}[x^n]x^j(x^2+x^3+...)^{m-j}$$ Ahora nos fijamos en cuántas particiones que podemos obtener de este caso en particular. Desde allí se $j$ número de $1$s, tendríamos que multiplicar por $k^j$, y desde $0\le j \le m$ $1 \le m \le n$ hemos \begin{align} P_1(k,n) &=\sum^{n}_{m=1}\sum^{m}_{j=0}k^j\binom{m}{j}[x^n]x^j(x^2+x^3+...)^{m-j}\\ &=\sum^{n}_{m=1}\sum^{m}_{j=0}k^j\binom{m}{j}[x^{n-2m+j}](1-x)^{-(m-j)}\\ &=\sum^{n}_{m=1}\sum^{m}_{j=0}k^j\binom{m}{j}\binom{m-j+n-2m+j-1}{n-2m+j}\\ &=\sum^{n}_{m=1}\sum^{m}_{j=0}k^j\binom{m}{j}\binom{n-m-1}{m-j-1}\\ &=2^{n-1}+\sum^{n-1}_{m=1}\sum^{m}_{j=0}k^j\binom{m}{j}\binom{n-m-1}{m-j-1}\\ \end{align} He intentado usar la "serpiente-aceite" método para calcular esta suma, que es, $$P_1(2,n)=2^{n-1}+[x^{n-1}]\sum_{n\ge 1}\sum^{n-1}_{m=1}\sum^{m}_{j=0}k^j\binom{m}{j}\binom{n-m-1}{m-j-1}x^{n-1}$$ pero yo, vergonzosamente, tienen problemas con cambiar el orden de la suma y la determinación de los límites de la suma.

Esto es donde estoy atascado, y me gustaría pedir su ayuda en la búsqueda de una forma cerrada para esta suma, y, en particular, demostrando que \begin{align} P_1(2,n) &=2^{n-1}+\sum^{n-1}_{m=1}\sum^{m}_{j=0}2^j\binom{m}{j}\binom{n-m-1}{m-j-1}\\ &=F_{2n+1} \end{align} La ayuda será muy apreciada. Gracias.

Answer 1

Observación 1: Para el entero positivo $k$, $F_{2k}=F_{2k-1}+F_{2k-2}=F_{2k-1}+F_{2k-3}+F_{2k-4}=\dots=F_{2k-1}+F_{2k-3}+\dots+F_1$. (No sería una $F_0$ plazo en el fin, sino $F_0=0$.)

Su identidad puede ahora ser establecido de forma recursiva. Para ordenó particiones de $n$, nos fijamos en los casos de acuerdo con el primer término de una partición. Si el primer término es $1$, tenemos dos formas (colores) a elegir ese $1$, y luego tenemos a $P(2,2n-1)$ a organizar el resto de los términos. Esto le da a $2\cdot P(2,n-1)$ ordenado particiones de $n$ a partir de con $1$. Si el primer término es $2$, entonces no se $P(2,n-2)$ maneras de hacer la partición. Y así sucesivamente. Por lo tanto $P(n)=2P(2,n-1)+P(2,n-2)+\cdots+ P(2,1)$. Si asumimos inductivamente que $P(2,k)=F_{2k+1}$, entonces obtendremos

$$\begin{array}{ccl} P(2,n)&=&2F_{2n-1}+F_{2n-3}+F_{2n-5}+\cdots+F_{1}\\&=&F_{2n-1}+(F_{2n-1}+F_{2n-3}+F_{2n-5}+\cdots+F_{1})\\&=&F_{2n-1}+F_{2n} \hspace{1in}\\&=&F_{2n+1} \end{array}$$

Answer 2

Gracias a la explicación profunda de @paw88789, pude obtener una forma cerrada para $P_1(2,n)$ sin usar ningún conocimiento previo de la respuesta. La relación de recurrencia es\begin{align} a_n &=2a_{n-1}+a_{n-2}+...+a_1+1\\ &=1+a_{n-1}+\sum^{n-1}_{m=1}a_m \end{align} aplicando la diferencia hacia adelante operador $\Delta_n$ a los rendimientos de ambos lados\begin{align} a_{n+1}-a_n&=a_n-a_{n-1}+a_n\\ a_{n+2}&=3a_{n+1}-a_n \end {Alinee el} definen la función generadora $$A(x)=\sum_{n\ge 1}a_nx^n$ $ $A(x)$, la relación de recurrencia es de %#% de #% $ problemas para $$\frac{A(x)-2x-5x^2}{x^2}=\frac{3A(x)-6x}{x}-A(x)$ da\begin{align} A(x) &=\frac{2x-x^2}{1-3x+x^2}\\ &=\frac{1-x}{1-3x+x^2}-1\\ \end {Alinee el} extraer la coeficiente\begin{align} a_n &=[x^n]\left(\frac{1-x}{1-3x+x^2}\right)\\ &=\frac{1}{\sqrt{5}}[x^n]\left(\frac{\tau}{x-(\tau+1)}-\frac{\phi}{x-(\phi+1)}\right)\\ &=\frac{1}{\sqrt{5}}\left(\phi\left(\frac{1}{\phi +1}\right)^{n+1}-\tau\left(\frac{1}{\tau +1}\right)^{n+1}\right)\\ &=\frac{1}{\sqrt{5}}\left(\phi(1+\tau)^{n+1}-\tau(1+\phi)^{n+1}\right)\\ &=\frac{1}{\sqrt{5}}\left(\phi^{2n+1}-\tau^{2n+1}\right)\\ \end {Alinee el} donde $A(x)$ y $\phi=\dfrac{1+\sqrt 5}{2}$.

Answer 3

La derivación de la generación de función también puede hacerse a partir de primeros principios, sin el uso de la recurrencia. Hemos inequívoca que estas particiones tienen la función de la generación de $$\sum_{q\ge 0} \left(\frac{z}{1-z} + z\right)^q$$ donde hemos añadido en la cantidad de $z$ a cuenta del hecho de que hay dos tipos de un valor. El índice empieza en cero, lo que produce un recuento de un vacío ordenó la partición. El parámetro $q$ cuenta el número de elementos en la orden de la partición.

Este rendimientos $$\sum_{q\ge 0} \left(\frac{2z-z^2}{1-z}\right)^q = \frac{1}{1-(2z-z^2)/(1-z)} = \frac{1-z}{1-z-2z+z^2} = \frac{1-z}{1-3z+z^2}.$$ Ahora la generación de la función de los números de Fibonacci es $$\sum_{k\ge 0} F_k z^k =\frac{z}{1-z-z^2}$$ de modo que los impares números de Fibonacci son generados por $$\sum_{k\ge 0} F_{2k+1} z^{2k+1} = \frac{1}{2} \frac{z}{1-z-z^2} + \frac{1}{2} \frac{z}{1+z-z^2}.$$ Por lo tanto $$\sum_{k\ge 0} F_{2k+1} z^{2k} = \frac{1}{2} \frac{1}{1-z-z^2} + \frac{1}{2} \frac{1}{1+z-z^2} = \frac{1}{2} \frac{2-2z^2}{(1-z^2)^2-z^2}.$$ Por lo tanto $$\sum_{k\ge 0} F_{2k+1} z^k = \frac{1-z}{(1-z)^2-z} = \frac{1-z}{1-3z+z^2}.$$ Esto demuestra la reclamación.