sábado, 5 de febrero de 2011

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 PK(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 P1(k)=1 y de Pk(k)=1 y se van calculando todos los Pk(N) por recurrencia.

Es claro que después de encontrar los valores de Pk(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?