Particiones

Algunas cuestiones sobre particiones de enteros
Matem´atica Discreta
Tercero de Matem´aticas, UAM (curso 2001/2002)
Pablo Fern´
andez Gallardo

1

C´
alculo de p(n)

Nota inicial : en los c´alculos que haremos a continuaci´on utilizaremos la notaci´on
y los argumentos que desarrollamos en clase (el 21 de mayo de 2002).
En su momento, y con la ayuda de los diagramas de Ferers, obtuvimos unas
umerode particiones de n con k
relaciones de recurrencia para los pk (n) (n´
partes): si k > 1,
pk (n) = pk−1 (n − 1) + pk (n − k) .
Junto con los valores frontera p1 (n) = 1 = pn (n) para cada n ≥ 1, pod´ıamos
umero
calcular los pk (n) y, sumando en todos los valores de k, tambi´en p(n), el n´
de particiones de n, para cada n ≥ 1.
Nos ponemos en el contexto de las funciones generatrices. Ya vimos enclase
que la funci´
on generatriz asociada a los n´
umeros p(n) es
∞

p(n)xn =

n=0

∞

1
.
1 − xj
j=1

Necesitamos calcular la funci´on generatriz asociada a un tipo particular de particiones.

Ejemplo 1.1 Obtengamos la funci´on generatriz de las particiones
de n que tienen todas sus partes distintas.
Si llamamos, como siempre, bj al n´
umero de veces que aparece el s´ımbolo j
en la partici´
on,contar esas particiones es lo mismo que contar el n´
umero de
soluciones de
 ∞
 ∞




j bj = n
aj = n
o
bien
el
de
j=1
j=1




0 ≤ bj ≤ 1
aj ∈ Lj = {0, j}
(n´
otese que ahora cada conjunto Lj es finito, as´ı que aparecer´an polinomios).
Con los argumentos habituales, llegamos a que
∞

p n
n=0

cada parte, a lo
sumo 1 vez

xn =

∞

1 + xj .

j=1

♣
1

Llamemos P (x) a esta funci´ongeneratriz, asociada a las particiones de n
cuyas partes son todas distintas:
∞

n

p(n | partes distintas)x =
n=0

∞

(1 + xj ) ≡ P (x) .

j=1

Es decir, cada partici´
on de n cuyas partes sean todas distintas contribuye con un
on P (x). ¿Y si consider´aramos
uno al coeficiente de xn del desarrollo de la funci´
la funci´
on
∞

P (x) =

(1 − xj ) ?

j=1

(es como la funci´on P (x), pero cambiamos unsigno). Ahora, cada partici´
on de
n con partes distintas sigue contribuyendo al coeficiente de xn del desarrollo de
P (x); pero la contribuci´
on es ahora (−1)s , donde s es el n´
umero de partes que
tenga la partici´
on: si tiene un n´
umero impar de partes, contribuir´
a con un −1
y si tiene un n´
umero par, con un 1. Es decir,


Coefn 

∞

(1 − xj ) = ppar (n) − pimpar (n) ,

j=1

dondellamamos
ppar (n)
pimpar (n)

= p(n | n´
umero par de partes, todas distintas)
= p(n | n´
umero impar de partes, todas distintas)

Se puede ver (si alguien est´
a interesado en los detalles, que me lo haga saber)
que esta diferencia es cero excepto cuando n coincide con
m
(3m ± 1)
2

para cierto entero m ≥ 1 ,

en cuyo caso vale (−1)m . Esto es,
∞

P (x) =

(1 − xj ) = 1 +

j=1

∞

m

m

(−1)m x 2 (3m−1)+ x 2 (3m+1) .

m=1

Lo que explica el curioso comportamiento del desarrollo de P (x):
∞

(1 − xj ) = 1 − x − x2 + x5 + x7 − x12 − x15 + x22 + x26 − x35 − x40 + · · · ,

j=1

un desarrollo con muchos coeficientes nulos y un patr´
on de signos aparentemente
reconocible: dos signos m´as, dos signos menos, etc.

2

Interludio. Los n´
umeros

m
(3m − 1)
2
reciben un nombre especial: son los n´
umerospentagonales, cuyos primeros
valores son
ω(m) =

m
m/2 (3m − 1)

1 2
1 5

3
12

4
5
22 35

6
51

7
70

···
···

La explicaci´on de este nombre reside en la casi inmediata identidad
m−1

(3k + 1) ,

ω(m) =
k=0

y su interpretaci´
on geom´etrica:

1+4=5

1

1 + 4 + 7 + 10 = 22

1 + 4 + 7 = 12

Esta sorprendente identidad tiene su aplicaci´
on, como ya viera Euler, al
c´alculo de p(n). Porque lafunci´
on generatriz de los p(n)
∞

p(n)xn =

n=0

∞

1
1 − xj
j=1

es precisamente la rec´ıproca de la funci´
on P (x). Es decir, que
∞

1 =

(1 − xj )

j=1

∞
k=1

∞

=

p(n)xn

n=0

1
1 − xk
∞

1+

m

m

(−1)m x 2 (3m−1) + x 2 (3m+1)

m=1

As´ı que el coeficiente n-´esimo de este producto de series es cero para cada n ≥ 1.
Utilizando la regla habitual de multiplicaci´
on de series de potencias,...