Funciones de partición de un número

Nota de actualidad: Cuando ya estaba programada esta entrada, apareció en la prensa la noticia del descubrimiento de una fórmula para particiones de números grandes basada en un número finito de sumandos. Puedes informarte en estos blogs:

 http://francisthemulenews.wordpress.com/2011/01/22/una-suma-finita-para-calcular-la-funcion-de-particion/

http://www.cienciakanija.com/2011/01/21/nueva-teoria-revela-la-naturaleza-de-los-numeros/

--------------------------

Hemos llamado P(N) al número de particiones en sumandos decrecientes del número N, pero se pueden definir otras funciones.Esta definición básica de número de particiones P(N) se puede someter a condicionamientos de los que surgirán nuevas definiciones. Las expresaremos así:

P(N / condicionamiento)

Vemos algunos ejemplos y sus propiedades

FUNCIÓN DE PARTICIÓN P_K(N)

Es la misma función P(N) condicionada a que sólo intervenga un número K de sumandos:
Pk(N)= P(N / k sumandos): Particiones con un número k de sumandos fijado.

Su interés radica en que permite una fórmula de recurrencia para el cálculo de P(N). La demostración se puede consultar en manuales especializados.

Se parte de P₁(k)=1 y de P_k(k)=1 y se van calculando todos los P_k(N) por recurrencia.

Es claro que después de encontrar los valores de P_k(N) bastará sumarlos todos para k menor o igual a N a fin de obtener P(N), pues la suma abarcaría todas las posibilidades.

El siguiente esquema está copiado de una hoja de cálculo programada para encontrar P(7)

		K	1	2	3	4	5	6	7
N
1	1		1
2	2		1	1
3	3		1	1	1
4	5		1	2	1	1
5	7		1	2	2	1	1
6	11		1	3	3	2	1	1
7	15		1	3	4	3	2	1	1

Al final de esta entrada puedes leer un código que te puede valer para implementar esta función en una hoja de cálculo.

FUNCIÓN DE PARTICIÓN Q(N)

Como la anterior, cuenta el número de particiones, pero en este caso se exige que los sumandos sean todos distintos. Por ejemplo, el entero 7 admite las siguientes particiones como números distintos: 7 = 6+1 = 5+2 = 4+3 = 4+2+1, luego Q(7)=5

Euler demostró que esta función coincide con el número de particiones de n en partes impares.

Código para implementar P(N)

Es válido para Excel y OpenOffice

Public function partic(n)

dim a(40,40) En lugar de 40 puedes escribir un número mayor
dim i,s,h,k


if n=1 then partic=1:exit function
k=n
for i=1 to n
a(1,i)=1  a(k,n) representa la función P(k,n) explicada más arriba
a(i,i)=1   Se dan valores iniciales
next i

for h=2 to n
for i=2 to h-1
m=h-i
s=0
for j=1 to i:s=s+a(j,m):next j   Se implementa la fórmula de recurrencia
a(i,h)=s
next i
next h
For h=1 to n Se van sumando las funciones
s=0
for i=1 to k
s=s+a(i,h)
next i
next h

partic=s

end function

Con esta función hemos construido la tabla siguiente

N	1	2	3	4	5	6	7	8	9	10
P(N)	1	2	3	5	7	11	15	22	30	42
N	11	12	13	14	15	16	17	18	19	20
P(N)	56	77	101	135	176	231	297	385	490	627
N	21	22	23	24	25	26	27	28	29	30
P(N)	792	1002	1255	1575	1958	2436	3010	3718	4565	5604

¿Te animas?