Máximo producto en la partición de un número (1)

Ya sabemos que una partición de un número entero positivo N es una suma de números también enteros positivos cuyo resultado es ese número. Ya hemos tratado en este blog el tema de las particiones, y lo volveremos a desarrollar próximamente. Si no tienes claro el concepto puedes acudir a las direcciones

http://hojaynumeros.blogspot.com.es/2011/02/particiones-de-un-numero.html

https://es.wikipedia.org/wiki/Partici%C3%B3n_(teor%C3%ADa_de_n%C3%BAmeros)

Está muy estudiado el tema del desarrollo de las particiones y el del cálculo de su número. Aquí nos interesará el máximo producto que se puede lograr multiplicando los sumandos de cada partición. Lo introducimos con ejemplos:

Máximo producto logrado con particiones

Tomemos el número 6. Mentalmente se pueden escribir sus particiones (no se tiene en cuenta el orden): 6=5+1=4+2=3+3=4+1+1=… En cada partición calculamos el producto entre sumandos: 6, 5, 8, 9, 4,… y nos quedamos con el máximo. En el esquema lo verás mejor:

Figuran las once particiones del 6 y en la columna de la derecha los productos de sumandos. En la partición de sumando único lo elegimos como producto. Se observa que el máximo producto es 9. Como el resultado es único, constituye una función del número elegido, que podríamos escribir como MPP (Máximo Producto en Particiones) y se tendría que MPP(6)=9.

Otro ejemplo: En PARI las particiones se obtienen con la función partitions. Si pedimos las particiones del número 8 las obtenemos como vectores independientes:

Si multiplicas los sumandos dentro de cada vector descubrirás que el máximo producto es 18=2*3*3, luego MPP(8)=18

Estos resultados figuran en la página de OEIS http://oeis.org/A000792 con una definición recursiva que ya trataremos:

1, 1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54, 81, 108, 162, 243, 324, 486, 729, 972, 1458, 2187, 2916, 4374, 6561, 8748, 13122, 19683, 26244, 39366, 59049, 78732, 118098, 177147, 236196, 354294, 531441, 708588, 1062882, 1594323, 2125764, 3188646, 4782969,…

Como era de esperar, los valores son crecientes (cada uno es un máximo que se apoya en los anteriores) y pronto adquieren una buena tasa de crecimiento. La página citada contiene una fórmula recursiva que es fácil de entender.

a(n) = max{ (n-i)*a(i) : i<n}; a(0) = 1

Se define a(0) como 1, y también es fácil entender las siguientes: a(1)=1, a(2)=2, a(3)=3,… La recursividad tampoco es difícil de captar. Se trata de multiplicar cada valor menor que n por el máximo correspondiente a su diferencia con n. En efecto, las particiones de n se forman eligiendo esos valores i:1…n-1 para luego unirlos con las particiones de n-i. Por ejemplo, en las particiones del 7, si elegimos el valor 4, se deberá combinar con las particiones del 3 para formar las particiones del 7 que contengan un 4. Igual ocurre con todos los valores: 5 se añadirá a las particiones del 2 y 3 se unirá a las particiones de 4.

Si conservamos los valores máximos de cada partición de n-i, al multiplicarlos por i resultarán productos de la partición superior, candidatos a ser máximos. Al recorrer todos los valores menores que n dispondremos de n-1 posibles máximos, y uno de ellos será el MPP.

Algoritmo de construcción de la función MPP

Las ideas anteriores nos permitirán construir la función  MPP. En VBA de Excel se puede usar esta definición de función:

Public Function mpp(n)
Dim mx, i, m, j, mm
Dim a(50) ‘Está preparado para n<=50. Se puede ampliar a otro número

If n = 0 Or n = 1 Then mpp = 1: Exit Function
If n = 2 Then mpp = 2: Exit Function ‘Casos particulares
a(0) = 1: a(1) = 1: a(2) = 2: mx = 2
If n > 2 Then
For i = 1 To n ‘Se recorren los valores anteriores para la recursión
m = 1 ‘Valor provisional del máximo
For j = 1 To i
mm = j * a(i - j)
If m < mm Then m = mm ‘Se busca un máximo nuevo mediante los productos con los anteriores
Next j
mx = m: a(i) = m ‘Se incorpora el máximo a la lista
Next i
End If
mpp = mx ‘Máximo final
End Function

Con esta función podemos encontrar el máximo producto entre particiones de cualquier número. Si es mayor que 50 bastará cambiar la dimensión del vector de máximos. En la tabla siguiente hemos recogidos los valores de MPP para los números comprendidos entre 30 y 40:

Para quienes conozcan el lenguaje PARI (gratuito y muy recomendable para estos temas) se inserta un código para esta función, que también devuelve los valores entre 30 y 40:

mpp(n)=my(a=vector(50), m, mm, mx=2,mp=1);a[1]=1;a[2]=2;if(n<2,mp=1,if(n==2,mp=2,for(i=3,n,m=1;for(j=1,i, d=i-j;if(d>0,mm = j * a[d],mm=j);if(m<mm,m=mm));mx=m;a[i]=m));mp=mx;mp)
for(k=30,40,print1(mpp(k),", "))

Aquí tienes el resultado, que coincide con el de Excel:

Interpretación algebraica

Estos valores coinciden con los cardinales máximos de los subgrupos del grupo simétrico S(n). Usando la descomposición en ciclos se les puede dar un significado (ver http://hojaynumeros.blogspot.com.es/2013/10/ciclos-2-descomposicion-en-ciclos.html)

Por ejemplo, en el caso del 8 visto más arriba, mpp(8)=18, y puede dársele el significado de que es el cardinal máximo de un subgrupo propio del grupo de permutaciones de 8. En concreto, usando la descomposición en ciclos, podría ser G=(1,2)(3,4,5)(6,7,8) o cualquiera de sus isomorfos. En el caso del 6 es fácil ver que el subgrupo maximal es el GM=(1,2,3)(4,5,6), de cardinal 3*3=9, que es el valor de mpp(6).

Existe una forma directa y simple para calcular mpp(n), sin recurrencias ni algoritmos. Como es un cambio importante en el desarrollo que hemos llevado hasta ahora, lo dejamos para la próxima entrada.