Logo Studenta
Gratis
179 pág.
Análise combinatória matemática

Vista previa | Página 19 de 30

parte más
larga es k.
7.4 Particiones auto-conjugadas
Una partición de n en k clases se dice ser auto-conjugada si
ésta es igual a su partición conjugada. Una caracterización
interesante se discute a continuación.
Proposición 47 El número de particiones auto-conjugadas
de n coincide con el número de particiones de n con todas
las partes desiguales e impares.
96 Caṕıtulo 7. Particiones de un entero
Demostración: Veamos cómo establecer una biyección en-
tre las particiones de n con todas las partes desiguales e im-
pares y las particiones de n auto-conjugadas.
Empecemos con un ejemplo: la partición 9+5+3, de 17
en 3 partes desiguales e impares. Con la primera parte (el
9) escribimos el diagrama de Ferrars que se indica en el paso
I de la figura, poniendo 5 cuadrados horizontales y luego 4
verticales.
Luego, con la segunda parte (el 5) continuamos llenando
el diagrama de Ferrars, agregándole 3 cuadrados horizontales
y 2 verticales, como se indica en el paso II. Finalmente con
la última parte (el 3) terminamos de llenar el diagrama de
Ferrars, agregándole 2 cuadrados horizontales y 1 vertical,
como se indica en el paso III.
9→
I
9+5→
II
9+5+3→
III
De esta manera obtenemos la partición auto-conjugada
5 + 4 + 4 + 3 + 1. En general puede llevarse a cabo este pro-
cedimiento. En efecto, si la partición original de n en partes
desiguales e impares la denotamos por λ = (λ1, λ2, . . . , λk),
entonces λ1 > λ2 > · · · > λk y cada una de las partes λi
es un impar, digamos λi = 2ni + 1, con i = 1, 2, . . . , k.
En la etapa i-ésima agregamos al diagrama de Ferrars ni + 1
cuadrados horizontales a la derecha y ni cuadrados verticales
hacia abajo.
Como cada una de las cantidades λi es menor que la an-
terior, el diagrama resultante corresponderá al diagrama de
Ferrars de una partición. Además por construcción la par-
7.5. Particiones en partes impares 97
tición resultante es auto-conjugada. Claramente con este pro-
cedimiento estamos estableciendo la biyección buscada.
7.5 Particiones en partes impares
Proposición 48 El número de particiones de n en partes
desiguales coincide con el número de particiones de n en
partes impares.
Demostración: Veamos como establecer una biyección en-
tre las particiones con todas las partes impares y las parti-
ciones con todas las partes desiguales. Empecemos con un
ejemplo de una partición con todas las partes impares:
5 + 5 + 5 + 5︸ ︷︷ ︸
4
+3 + 3 + 3 + 3 + 3 + 3 + 3︸ ︷︷ ︸
7
+1 + 1 + 1 + 1 + 1︸ ︷︷ ︸
5
.
Cada uno de los exponentes anteriores puede ser expresado
de manera única en base 2:
grupos de 5’s = 4 = 22,
grupos de 3’s = 7 = 20 + 21 + 22,
grupos de 1’s = 5 = 20 + 22.
Luego, agrupamos todas las 2k partes idénticas de la par-
tición original en una sola parte: agrupamos 22 × 5, agru-
pamos 22 × 3, agrupamos 21 × 3, agrupamos 20 × 3, agru-
pamos 22 × 1 y finalmente agrupamos 20 × 1, para obtener
finalmente la nueva partición con todas sus partes desiguales
20 + 12 + 6 + 4 + 3 + 1.
En general puede aplicarse este procedimiento a cualquier
partición que tenga todas las partes impares. La partición
obtenida al aplicar este procedimiento tendrá siempre todas
las partes desiguales, pues éstas serán todas de la forma 2k×
(2m+1) y es bien sabido que todo entero se puede escribir de
manera única como el producto de un impar y una potencia
de 2.
98 Caṕıtulo 7. Particiones de un entero
7.6 Funciones generadoras de particiones
Proposición 49 (Funciones generadoras asociadas a
particiones)
(a) La función generadora de Pn, el número de particiones
de n, es
F1(t) =
1
(1− t)(1− t2)(1− t3) · · ·
.
(b) La función generadora de P mn , el número de particiones
de n en m partes, es
F2(t) =
tm
(1− t)(1− t2) · · · (1− tm)
.
(c) La función generadora del número de particiones de n
cuyas partes son todas impares es
F3(t) =
1
(1− t)(1− t3)(1− t5) · · ·
.
(d) La función generadora del número de particiones de n
cuyas partes son todas desiguales es
F4(t) = (1 + t)(1 + t2)(1 + t3) · · · .
(e) La función generadora del número de particiones de n
cuyas partes son todas impares y desiguales es
F5(t) = (1 + t)(1 + t3)(1 + t5) · · · .
(f) La función generadora del número de particiones de n
cuya parte mayor no excede a k es
F6(t) =
1
(1− t)(1− t2) · · · (1− tk)
.
7.6. Funciones generadoras de particiones 99
Demostración: Tan solo demostraremos el caso a), quedando
el resto como ejercicio para el lector. Debemos probar que
1
(1− t)(1− t2)(1− t3) · · ·
=
∞∑
n=0
Pn t
n.
Para |t| < 1 considere el producto
A =
1
(1− a1t)(1− a2t2) · · · (1− aktk) · · ·
.
Desarrollando cada factor, realizando los productos y agru-
pando en potencias de t, obtenemos
A = (1 + a1t+ a21t
2 + · · ·) · · · (1 + akt+ akt2 + · · ·) · · ·
= 1 + a1t+ · · ·+ (aλ11 a
λ2
2 · · · a
λk
k + · · ·) t
n + · · · .
En el coeficiente de tn cada término aλ11 a
λ2
2 · · · a
λk
k define una
partición de n, a saber:
n = (k + · · ·+ k)︸ ︷︷ ︸
λk
+ · · ·+ (2 + · · ·+ 2)︸ ︷︷ ︸
λ2
+(1 + · · ·+ 1)︸ ︷︷ ︸
λ1
.
De esta manera todas las particiones de n serán enumeradas,
sin repeticiones ni omisiones. Finalmente, sustituyendo 1 =
a1 = a2 = · · ·, obtenemos la fórmula para F1(t).
Algunos de los resultados analizados en este caṕıtulo pueden
ser obtenidos mediante una simple comparación de las fun-
ciones generadoras asociadas. Por ejemplo, la proposición 48
establece que el número de particiones de n en partes de-
siguales coincide con el número de particiones de n en partes
impares. Lo anterior es evidente si se demostrara que las
funciones F3(t) y F4(t) son idénticas, en algún vecindario de
0. Esto es fácil de establecer:
100 Caṕıtulo 7. Particiones de un entero
F3(t) =
1
(1− t)(1− t3)(1− t5) · · ·
=
(1− t2)(1− t4)(1− t6) · · ·
(1− t)(1− t2)(1− t3) · · ·
=
(1− t)(1 + t)(1− t2)(1 + t2)(1− t3)(1 + t3) · · ·
(1− t)(1− t2)(1− t3) · · ·
= (1 + t)(1 + t2)(1 + t3) · · · = F4(t).
Aunque el procedimiento anterior, debido a Euler, es ab-
solutamente elemental, sin embargo no tiene la virtud de
mostrarnos la biyección existente entre ambas clases de par-
ticiones.
El tema de las particiones de un entero y sus ramifi-
caciones es fuente inagotable de resultados insospechados.
Por ejemplo, Hardy y Ramanujan demostraron la siguiente
aproximación, que ayuda a comprender el tipo de crecimiento
asintótico de Pn:
Pn ≈ π
√
2n/3− ln(4n
√
3).
7.7 Ejercicios
119. Muestre que el número de particiones de n en tres
partes es igual al número de particiones de 2n en tres partes
de tamaño menor que n.
120. Muestre que el número de particiones de n es igual al
número de particiones de 2n en n partes.
121. Muestre que el número de particiones de 2r+k en r+k
partes es el mismo, para cada k ∈ N.
7.7. Ejercicios 101
122. Demuestre la proposición 49, de las funciones gener-
adoras asociadas con los números de particiones.
123. Muestre que el número de particiones de r + k en k
partes es igual a:
(a) El número de particiones de r + (k+12 ) en k partes dis-
tintas.
(b) El número de particiones de r en partes de tamaño
menor o igual a k.
Caṕıtulo 8
Otros tópicos de la
teoŕıa de combinatoria
Presentamos en este caṕıtulo una breve enumeración de
otros temas de la teoŕıa de combinatoria no tratados en este
trabajo introductorio, sin pretender ser exhaustivos.
8.1 Denumerantes
El denumerante D(n; a1, . . . , am) es el número de particiones
del entero n en las partes espećıficas a1, . . . , am (terminoloǵıa
introducida por Sylvester), o lo que es lo mismo, el número
de soluciones en enteros positivos de la ecuación
a1x1 + a2x2 + · · ·+ amxm = n.
No es dif́ıcil demostrar que la función generadora ordi-
naria de estos números es
F (t; a1, . . . , am) =
∞∑
n=0
D(n; a1, . . . , am) tn
=
1
(1− ta1)(1− ta2) · · · (1− tam)
.
103
104 Caṕıtulo 8. Otros tópicos de la teoŕıa de combinatoria
Hay mucha teoŕıa compleja acerca de los denumerantes,
analizando algunas propiedades o fórmulas recursivas
Página1...151617181920212223...30