Angel "Java" Lopez en Blog

Publicado el 23 de Marzo, 2015, 16:01

Post Anterior
Siguiente Post

Veamos una forma de generar las particiones de n+1 conociendo la enumeración de las particiones de n, expresadas en forma normal (con su elementos en forma descendente).

Sea una partición de 5, como:

2+1+1+1

Siempre se le puede agregar un uno al final, para obtener una partición de 6:

2+1+1+1+1

Lo mismo a la partición de 5:

3+2

se le puede agregar un uno a la derecha, para obtener la partición de 6:

3+2+1

O sea que a CADA partición de 5, le corresponde UNA partición de 6, que termina en 1. Se puede ver también que a toda partición de 6 que contenga un 1, le corresponde UNA partición de 5 (simplemente sacando ese uno).

También, dada una partición de 5 en forma normal como

3+2

Obtenemos otra partición de 6, sumándole un uno al último término, en este caso sumando uno al último elemento el dos:

3+3

Pero eso no es posible en una partición de 5 en forma normal como:

2+1+1+1

Porque sumándole uno al último término:

2+1+1+2

obtenemos una partición de 6, pero no en forma normal, no en forma tal que todos sus elementos vayan siendo iguales o decrecientes cuando los recorremos de izquierda a derecha. Si nos fijamos en el ejemplo anterior y otros, el truco de agregar uno al último elemento NO FUNCIONA, porque ese último elemento está repetido.

Si llamamos

p(n)

a la cantidad de particiones de n, y llamamos

r(n)

a la cantidad de particiones de n que NO TIENE su menor elemento repetido, llegamos a nuestra primera conclusión:

p(n+1) = p(n) + r(n)

El primer término de la derecha, es la cantidad de particiones de n+1 que nacen de agregar el número 1 a cualquier de las particiones de n. El segundo término, viene de las particiones de n a las que se les puede sumar uno a su término menos. Y si lo miramos fijo, es claro que cada partición de n+1 NACE de una Y SOLO UNA de esas dos formas.

Igual, mucho no avanzamos, porque no parece a simple vista que r(n) tenga una forma sencilla de calcularse. Pero todo suma ;-)

Nos leemos!

Angel "Java" Lopez
http://www.ajlopez.com
http://twitter.com/ajlopez