Particiones y funciones generatrices

Unimos hoy dos conceptos que ya hemos tratado en el blog

http://hojaynumeros.blogspot.com.es/2011/01/montones-de-piezas.html y siguientes
http://hojaynumeros.blogspot.com.es/2013/03/funciones-generatrices-en-combinatoria.html y siguiente.

y que al unirse dan resultados mucho más potentes. Recomendamos la lectura previa de ambas. Recorreremos ahora los principales tipos de particiones, ayudados también por nuestra hoja de cálculo Cartesius.

Particiones ordinarias P(n)

En la entrada ya referida las estudiamos desde un punto de vista general. Aplicaremos ahora el concepto de función generatriz.

Supongamos que deseamos encontrar todas las particiones ordinarias del número 6 (formas de representar 6 como suma con posible repetición de sumandos). Para ello no necesitamos ni funciones ni técnicas informáticas. Con un poco de atención llegaremos a que el 6 se descompone en suma de las siguientes formas:

6 = 5+1 = 4+2 = 4+1+1 = 3+3 = 3+2+1 = 3+1+1+1 = 2+2+2 = 2+2+1+1 = 2+1+1+1+1 = 1+1+1+1+1+1

Son once en total

Si queremos expresar este proceso mediante funciones generatrices hay que recordar que los sumandos provenían de exponentes en un polinomio. En efecto, en este caso del 6 podemos considerar la función

Si multiplicamos todo, el término de grado 6 se compondrá de todos los productos en los que el primer paréntesis aporta los sumandos iguales a 1, el segundo los que valen 2, el tercero, 3, y así hasta llegar al 6. Hemos tomado infinitas potencias en cada uno porque las mayores que 6 no van a influir, pero gracias a ello la expresión se simplifica como una progresión geométrica:

O expresado de forma sintética y generalizando hasta n:

Después volveremos a esta función generatriz para adaptarla a casos particulares. La comprobamos para n=6. Vimos en anteriores entradas que con PARI se pueden desarrollar fácilmente.

print(taylor(1/(1-x)/(1-x^2)/(1-x^3)/(1-x^4)/(1-x^5)/(1-x^6),x,7))

Resultado: 1+x+2x^2+3x^3+5x^4+7x^5+11x^6+O(x^7) con el coeficiente 11 para x^6, como era de esperar. Serían las once particiones esperadas. Como en ocasiones anteriores, este método nos da más, pues podemos leer otros coeficientes: con el 5 tendríamos 7 particiones, con el 4, 5, y así…A la inversa, si en lugar de pararnos en el 6 hubiéramos seguido escribiendo factores, obtendríamos más particiones, para 7, 8,… Así que recordemos la función generatriz (F.G.) para las particiones ordinarias del número n:

Podemos comprobar el resultado con nuestra hoja Cartesius. Basta programar esto:

Concreta un total de 6 conjuntos, formado cada uno por el rango 0..6, en el que sólo se seleccionan los arreglos crecientes (para evitar duplicidades) y con suma 6.
Obtendríamos once resultados

Intenta obtener otros resultados similares. Lo importante es que recuerdes la definición de partición de un número y su F.G.

Particiones en sumandos distintos Q(N)

Si al descomponer un número en sumandos no permitimos que figuren repetidos, obtendríamos resultados muy distintos, recogidos como la función de partición Q(n).

En este caso la función generatriz se simplifica mucho, pues en los paréntesis no han de figurar todas las potencias sino una sola por cada sumando. Así, para n=7 la F.G. sería

y generalizando para n

Para el caso de 7 podemos expandir la F.G. mediante wxMaxima

Obtendremos un desarrollo en forma de polinomio, pero sólo serán útiles los coeficientes menores o iguales a 7:

Ya tenemos la solución, el 7 se puede descomponer en 5 formas diferentes como suma de números naturales distintos:

7=6+1=5+2=4+3=4+2+1

Además, hemos obtenido que el 6 tiene 4 descomposiciones, el 5, 3 y así hasta el 1. Recuerda: estos son los únicos fiables en el desarrollo.

Con Cartesius:

5 soluciones

Particiones en partes impares P(N/Impar)

Aquí vemos rápidamente la utilidad de la función generatriz. Si en la fórmula general de las particiones eliminamos los pares de los paréntesis quedaría

que fácilmente se traduce, al igual que en las particiones ordinarias, a cocientes:

O bien

Por ejemplo, para n=7, usando PARI, nos resultaría

print(taylor(1/(1-x)/(1-x^3)/(1-x^5)/(1-x^7),x,8))

1+x+x^2+2*x^3+2*x^4+3*x^5+4*x^6+5*x^7+O(x^8)

Como el coeficiente de 7 es 5, ese será el número de particiones en impares. Como son tan pocas, las podemos escribir directamente: 7 = 5+1+1 = 3+3+1 = 3+1+1+1+1 = 1+1+1+1+1+1+1
Intenta comprobar, como en los casos anteriores, que con 6 resultarían 4, con 5, 3, y así con todos los coeficientes resultantes.

Comprobación con Cartesius

La instrucción CONCERO significa que a los impares les adjuntamos el cero para representar los sumandos que no entran en una suma determinada. Además, se impone la condición de ser impares.
5 soluciones:

Este resultado coincide con el de representar 7 con sumandos distintos. En realidad siempre es así, como demostró Euler usando funciones generatrices:

El número de particiones de un número en sumandos distintos coincide con el de particiones en sumandos impares

Con el uso de las F.G. todo se reduce a un artificio algebraico:

Demostración

Todo se basa en que

Así que partiendo de la F.G. de la partición en elementos distintos, representamos cada factor de esta forma, se simplificarán los factores de exponente par y sólo quedarán los impares en el denominador

En el caso de n=7 te proponemos una correspondencia biyectiva por el método de Sylvester. Para que pienses un poco más sólo daremos el proceso y tú sacas tus consecuencias:

7=6+1=5+2=4+3=4+2+1 = 2*3+1 = 5+2*1=4*1+3=4*1+2*1+1 y ahora sustituimos cada producto por la suma correspondiente: 7 = 3+3+1 = 5+1+1 = 1+1+1+1+3 = 1+1+1+1+1+1+1

¿Puedes generalizarlo?

Para el camino inverso deberíamos expresar cada suma de repetidos como suma respecto a potencias de 2 distintas que se sacan como factor común.

7 = 3+3+1 = 5+1+1 = 1+1+1+1+3 = 1+1+1+1+1+1+1 = 3*2+1=5+2*1=4*1+3=4*1+2*1+1

Serían siempre todos distintos, porque o se diferencian en el números sacado factor común o en las distintas potencias de 2