Muy curioso propiedades de ordenada particiones relativas a los números de Fibonacci

Question

Me encontré con algunas de las interesantes propuestas que se encuentran en algunos de los cálculos que hice y me preguntaba si alguien sería tan amable de proporcionar algunas explicaciones de este fenómeno.

Llamamos a una ordenó la Partición de un número entero positivo de $n$ como la forma de escribir $$ n como suma de uno o más números enteros positivos, donde el orden de la suma NO importa. Por ejemplo, hay $4$ ordenó particiones de $3 dólares, es decir,$1+1+1, 1+2,2+1,3$

Ahora supongamos que vamos a reemplazar el último término de cada uno por encima de la partición con un $1$, se multiplican los términos de cada una de las particiones, luego agregar los resultados a todos juntos. De esta manera, se obtiene: $(1\cdot 1 \cdot 1 )+ (1 \cdot 1 )+ (2 \cdot 1) +(1)$, respectivamente, lo que equivale a $5$, que curiosamente es un número de Fibonacci! Por favor alguien puede explicar por qué este resultado es siempre un número Fibonacci? (Hacer algunos cálculos más si todavía no te has convencido.)

Ahora, aquí es más difícil la relación que he encontrado. Dado cualquier partición de la suma, mantener sólo la primera, tercera, quinta,... plazo. Sustituir cada término $x$ $2^{x-1}$ y multiplicar los resultados. Así, como ejemplo, la suma $2+4+1+3+5$ sería $2^12^02^4=32$. Ahora haz esto para todos los pedidos de partición de $n$ y sumar el resultado. Curiosamente, la suma es siempre $F_{2n}$. Por favor alguien puede explicar esto?

Muchas gracias por su tiempo!

Edit: esto es problemático, ya que yo no puedo escribir comentarios como no soy usuario, pero sí En el primer ejemplo la sustitución de un 1 o no se va a producir de fibonacci de suma-producto, pero ya he probado el caso de que usted nt reemplazar con un 1

Answer 1

La primera relación es en realidad más interesante de lo que sugieren. Específicamente, la aplicación de su receta a la orden de las particiones de $n$ produce $F_{2n-1}$, mientras que la adición de los productos sin la reducción de la última entrada a $1$ produce $F_{2n}$.

No es demasiado difícil ver por qué esto funciona. Supongamos que es cierto para algunos $n$, y considerar la posibilidad de la orden de las particiones de $n+1$. Son de dos tipos: los que terminan en $1$, y los que no. Cada partición de $n+1$ que termina en $1$ es obtenido a partir de una partición de $\pi$ $n$ anexando $+1$; su reducido del producto es el producto de las entradas en $\pi$, por lo que la suma de la reducción de los productos de estas particiones de $n+1$ es $F_{2n}$.

Cada partición de $n+1$ que hace que no terminan en $1$ es obtenido a partir de una partición de $\pi$ $$ n por la adición de $1$ a su último elemento; su reducido del producto es la misma que la reducción del producto de $\pi$, por lo que la suma de la reducción de los productos de estas particiones de $n+1$ es $F_{2n-1}$. Por lo tanto, la suma de la reducción de los productos de todos los de la orden de las particiones de $n+1$ es $F_{2n}+F_{2n-1}=F_{2n+1}=F_{2(n+1)-1}$, como se desee.

La suma de los sin diluir productos de las particiones de $n+1$ que terminan en $1$ es igual a la suma de su reducido de productos, o $F_{2n}$, por lo que para completar el argumento, sólo tenemos que demostrar que la suma de los sin diluir productos de las particiones que no terminan en $1$ es $F_{2n+1}$. Pero esto es clara: si $\pi'$ es una ordenó la partición de $n+1$ obtiene mediante la suma de $1$ para el último elemento de algunos ordenó la partición de $\pi$ $$ n, el producto sin diluir de $\pi'$ es la suma de la reducción y no reducido de productos de $\pi$. Sumando sobre todas las particiones de $n+1$, a continuación, se obtiene un total de $F_{2n}+F_{2n-1}=$ $F_{2n+1}$, al igual que en el último párrafo.

Por supuesto, la inducción se obtiene del suelo con ninguna dificultad, ya que las sumas de $n=1$ son $F_1=1=F_2$.

Yo había pensado para agregar esto hace un tiempo, pero estuve ocupado y se olvidó de:

Esto difiere de savicko1 del argumento, principalmente, en que se ve sólo en el inmediatamente anterior entero.

La segunda pregunta puede ser tratado del mismo modo. Deje que $P(n)$ el conjunto de ordenadas de las particiones de $n$. Llamar a una ordenó la partición de $n$ o impares según el número de términos es par o impar. Deje de $P_o(n)$ el conjunto de impares ordenó particiones de $n$, $P_o^-$ el conjunto de impares ordenó particiones de $n$, cuyo último término es de $1$ y $P_o^+(n)$ el conjunto de impares ordenó particiones de $n$, cuyo último término es mayor que $1$, y definir $P_e(n)$, $P_e^-(n)$ y $P_e^+(n)$ el mismo modo para ordenó incluso las particiones de $n$. Para cada ordenó la partición de $\pi$ $$ n deje que $f(\pi)$ es el producto de los factores de $2^{x-1}$ como $x$ rangos de los números impares términos de $\pi$. Por último, vamos a $$s(n)=\sum_{\pi\en P(n)}f(\pi\text{ y }t(n)=\sum_{\pi\en P_o(n)}f(\pi)\;.$$

Entonces $$\begin{align*} &\sum_{\pi\en P_o^-(n+1)}f(\pi)=\sum_{\pi\en P_e(n)}f(\pi)=s(n)-t(n)\;,\\ &\sum_{\pi\en P_o^+(n+1)}f(\pi)=2\sum_{\pi\en P_o(n)}f(\pi)=2t(n)\;,\\ &\sum_{\pi\en P_e^-(n+1)}f(\pi)=\sum_{\pi\en P_o(n)}f(\pi)=t(n)\;,\text{ y}\\ &\sum_{\pi\en P_e^+(n+1)}f(\pi)=\sum_{\pi\en P_e(n)}f(\pi)=s(n)-t(n)\;, \end{align*}\etiqueta{1}$$

y desde la izquierda lados de $(1)$ suma $s(n+1)$, $$ s(n+1)=2s(n)+t(n)\etiqueta{2}$$ y $$t(n+1)=\sum_{\pi\en P_o^-(n+1)}f(\pi)+\sum_{\pi\en P_o^+(n+1)}f(\pi)=s(n)+t(n)\;.$$ Si $s(k)=F_{2k}$ para $k\le n$, entonces $$\begin{align*} s(n+1) y=2F_{2n}+t(n)\\ &=2F_{2n}+s(n-1)+t(n-1)\\ &=2F_{2n}+s(n-1)+\big(s(n)-2(n-1)\big)\qquad\text{(a partir de }(2)\text{)}\\ &=3F_{2n}-F_{2n-2}\\ &=2F_{2n}+F_{2n-1}\\ &=F_{2n}+F_{2n+1}\\ &=F_{2n+2}\;, \end{align*}$$

y el resultado sigue por inducción.

Answer 2

La segunda parte de la pregunta

Vamos a denotar una suma de productos ($\prod 2^{x_{2k+1}-1}$) definido en el segundo problema para un conjunto de particiones de $\Pi$ $S(\Pi$.

Cada partición de $\pi$ consiste en ya sea par o impar el número de sumandos. Voy a llamar a un par o impar partición respectivamente. Ahora: cada partición de $\pi$ de $n>0$ es una partición de unos $m<n$ con un adicional sumando: $n-m$. Hay incluso un bijection entre particiones de $n$ y particiones de $m<n$ si suponemos que hay un vacío de la partición de $m=0$.

Ahora, una observación clave: el conjunto $E_n$ incluso de particiones de $n$ se derivan de extraño particiones de $m$ y simétricamente para el conjunto de $O_n$ impar de particiones. Lo que es más, un número $S(O_n)$ es igual a $F_{2n-1}$ y el número $S(E_n)$ es $F_{2n-2}$. Mediante la adición de los dos tenemos la tesis.

Pero tenemos que probar esas igualdades. Va a ser un "paralelo" inductivo de la prueba de la tesis por $O_m\ \& \ E_m$ conseguiremos la tesis de $O_n\ \& \ E_n$. Primeros $S(E_n)$. $$S(E_n) = S(O_{n-1}) + S(O_{n-2}) + \ldots + S(O_{1}) = $$ $$= F_{2n-3} + F_{2n-5} + \ldots + F_1 = (F_0=0) = F_{2n-2}.$$

$S(O_n)$ es un poco más difícil. $$S(O_n) = S(E_{n-1})\cdot 2^{1-1} + S(E_{n-2})\cdot 2^{2-1} + \ldots S(E_{2})\cdot 2^{(n-2)-1} + 2^{n-1} = $$ (tenga en cuenta que $E_1$ está vacía) $$= F_{2n-4} + F_{2n-6}\cdot 2 + \ldots + F_2\cdot 2^{(n-2)-1} + 2^{n-1} = $$ $$= F_{2n-4} + 2 (F_{2n-6} + \ldots + F_2\cdot 2^{(n-3)-1} + 2^{(n-1)-1}) = $$ $$ = F_{2n-4} + 2 S(O_{n-1}) = F_{2n-4} + 2F_{2n-3} = F_{2n-2} + F_{2n-3} = F_{2n-1} \ \square$$

Comentario acerca de la primera parte de la pregunta

El mismo truco se puede hacer en el caso de la primera pregunta, donde se calcula una suma diferente de $\hat{S}(\Pi)$ a partir de un conjunto de particiones de $\Pi$. En ese caso uno no tiene que dividir el conjunto $\Pi_n$ de particiones de $n$ en $E_n$ y $O_n$ y en lugar de $S(E_{n-x})2^{x-1}$ simplemente se $\tilde{S}(\Pi_{n-x})\cdot 1$ ($1$ en lugar de $2^{n-1}$). Tenga en cuenta que uno construye una "reducción" de la suma de $\hat{S}$ añadiendo "sin diluir" las sumas de $\tilde{S}$. Ya que hay una muy evaluó la respuesta anterior y no es tan duro para la formalización de este enfoque cuando el sketch es siempre y, finalmente, es una tarea, yo omitir los detalles.

Answer 3

Este problema tiene una solución con el uso ordinario de la generación de funciones.

La primera pregunta. Observar que $$\sum_{q\ge 0} q z^q = \frac{z}{(1-z)^2}.$$

Por lo tanto, la generación de la función de la contribución de las particiones con $k$ términos está dada por $$\left(\frac{z}{(1-z)^2}\right)^{k-1} \frac{z}{1-z}$$ y la contribución de todas las particiones $$p(z) = \sum_{k\ge 1} \left(\frac{z}{(1-z)^2}\right)^{k-1} \frac{z}{1-z} = \frac{z}{1-z} \frac{1}{1-z/(1-z)^2} \\= \frac{z}{1-z} \frac{(1-z)^2}{(1-z)^2-z} = \frac{z(1-z)}{1 - 3z + z^2}.$$ Recordemos que la generación de la función de los números de Fibonacci es $$\sum_{q\ge 0} F_q z^q = \frac{z}{1-z-z^2}.$$ De ello se sigue que $$\sum_{q\ge 0} F_{2t+1} z^{2t+1} = \frac{1}{2}\frac{z}{1-z-z^2} + \frac{1}{2}\frac{z}{1+z-z^2} \\= z \frac{1-z^2}{(z^2+z-1)(z^2-z-1)} = z \frac{1-z^2}{(z^2-1)^2-z^2}$$ así que $$\sum_{q\ge 0} F_{2t+1} z^{q+1} = z \frac{1-z}{1-3z+z^2}$$ que finalmente los rendimientos $$[z^n] p(z) = F_{2n-1}.$$

Segunda pregunta.

Para empezar a observar que $$\frac{1}{2} \sum_{q\ge 1} 2^p z^q = \frac{z}{1-2z}.$$

Aquí la generación de la función es de $k=2q$ incluso ($k$ -- número de elementos de la partición) $$\left(\frac{z}{1-2z}\right)^q \left(\frac{z}{1-z}\right)^p$$ y por $k=2t+1$ impar $$\left(\frac{z}{1-2z}\right)^{q+1} \left(\frac{z}{1-z}\right)^q.$$ La recogida de ambas contribuciones obtenemos $$p(z) = \sum_{q\ge 1} \left(\frac{z}{1-2z}\right)^q \left(\frac{z}{1-z}\right)^q + \sum_{q\ge 0} \left(\frac{z}{1-2z}\right)^{q+1} \left(\frac{z}{1-z}\right)^q.$$ Simplificar para obtener $$\frac{z^2/(1-2z)/(1-z)}{1-z^2/(1-2z)/(1-z)} + \frac{z}{1-2z} \frac{1}{1-z^2/(1-2z)/(1-z)}$$ o $$\frac{z^2}{(1-2z)(1-z)-z^2} + \frac{z(1-z)}{(1-2z)(1-z)-z^2}$$ que es $$\frac{z}{(1-2z)(1-z)-z^2} = \frac{z}{1-3z+z^2}.$$ Recordar que la generación de la función de los números de Fibonacci para obtener $$\sum_{q\ge 0} F_{t2} z^{t2} = \frac{1}{2}\frac{z}{1-z-z^2} - \frac{1}{2}\frac{z}{1+z-z^2} = \frac{z^2}{(1-z^2)^2-z^2}$$ así que $$\sum_{q\ge 0} F_{t2} z^q = \frac{z}{(1-z)^2-z} = \frac{z}{1-3z+z^2}.$$ Esto finalmente se rinde $$[z^n] q(z) = F_{2n}.$$

Adenda. El siguiente Arce código puede ser usado para verificar los resultados anteriores y de investigar más a fondo estos números. Arce tiene una rutina de Fibonacci con el nombre de fibonacci.

con(planta);

q := proc(n)
opción de recordar;
local de s, p, q, x, k;
 s := 0;

 para p en la partición(n) hacer
 por q en la permutar(p) ¿
 x := [seq(p[k], k = 1 .. nops(q) - 1), 1];
 s := s + mul(x[k], k = 1 .. nops(x))
od;
od;
s
end;


p2 := proc(n)
opción de recordar;
local de s, p, q, x, k;
 s := 0;

 para p en la partición(n) hacer
 por q en la permutar(p) ¿
 x := [seq(p[2*k+1], k=0..iquo(nops(q)-1, 2))];
 s := s + mul(2^(x[k]-1), k = 1 .. nops(x))
od;
od;
s
end;