Publicado el 23 de Marzo, 2015, 16:01
|
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 |