domingo, 13 de junio de 2010

Unos y partes distintas en particiones

Para una partición P de un número, definimos A(P) como la cantidad de unos que aparecen en P y B(P) como la cantidad de números distintos en P. Demuestra que para cualquier n fija la suma de las A(P) sobre las particiones de n es igual a la suma de las B(P) sobre las particiones de n.

6 comentarios:

José Luis Miranda Olvera dijo...

como defines la particion de un numero?

Leo dijo...

Una partición de un número es escribirlo como la suma de otros números, pero que queden en orden no decreciente. Por ejemplo, las particiones de 4 son 1+1+1+1, 1+1+2, 1+3, 2+2 y 4. Las A(P) serían respectivamente 4,2,1,0,0 y las B(P) 1,2,2,1,1. Noten como la suma de las A(P) es igual a las de las B(P) como dice el problema.

Manuel Dosal dijo...

Ya intente el problema, y llevo que la suma de las A(P) para n es SA(P)=P_0+P_1+...+P_(n-1), donde P_k es el numero de particiones del numero k.

Leo dijo...

Bien Manuel! Ahora, podrás ver de alguna forma que para las B se cumple lo mismo?

Unknown dijo...

Pues hasta ahora he llegado a lo mismo que Manuel. Estoy buscando cómo relacionar la suma de las B((P) en las particiones de n+1 y n, pero no he encontrado una forma que me permita contar fácil.

Unknown dijo...

Pues creo que ya me salió, no estaba difícil, sólo era ver cómo contar. Sea a_n el número de particiones de n y b_n la suma de los A(P) de todas las particiones de n. Tenemos que b_{n+1}=a_n+b_n. Esto es porque podemos establecer una biyección entre las particiones de n+1 que tengan al menos un uno y las particiones de n. Hacemos esto agregando a cualquier partición de n un 1 y viceversa. Entonces la cantidad total de unos que aparecen en las particiones de n+1 es b_n+a_n porque hay que contar los unos de las particiones de n y agregamos a_n porque a cada partición le agregamos un 1. Entonces por la recursión tenemos que b_{n+1}=a_n+a_{n-1}+...+a_{1}+a_{0}, donde a_{0}=1. Luego sea c_n la suma de los B(P) de las particiones de n. Sea x(n,k) el número de particiones de n que contienen al menos un k. Tenemos que x(n,k)=a_{n-k} porque para contar las particiones de n que tengan al menos un k simplemente contamos las particiones de n-k, porque a cualquiera de estas le agregamos un k y ya. Entonces
c_{n+1}=x(n+1,1)+x(n+1,2)+...+x(n+1,n+1)
=a_{n}+a_{n-1}+...+a_1+a_0=b_{n+1}

Publicar un comentario