Análise combinatória matemática

azules y tres bolas doradas.
86 Caṕıtulo 6. Funciones generadoras
106. Encuentre la función generadora ordinaria que permite
determinar el número de combinaciones de las letras M , A,
T , E, tomando 5 de ellas a la vez, con la condición de que
las letras M y A pueden aparecer cualquier número de veces,
pero las letras T y E pueden aparecer a lo sumo una vez.
¿Cuál coeficiente en esta función generadora necesitamos?
107. Encuentre el número total de selecciones de seis ob-
jetos, seleccionados a partir de tres tipos de objetos, con
repeticiones de a lo sumo cuatro objetos de un tipo.
108. Considere una clase con 27 estudiantes, que se encuen-
tran realizando la elección del presidente de la misma. Hay
cuatro candidatos y cada uno de los 27 estudiantes vota por
uno de estos cuatro candidatos.
(a) Encuentre la función generadora para el número de
diferentes resultados de la elección. ¿Cuál coeficiente
andamos buscando?
(b) Suponga que cada uno de los candidatos vota por śı
mismo. ¿Ahora cuál es la función generadora y el coe-
ficiente requerido?
(c) Suponga que ningún candidato recibe mayoŕıa absoluta
en la votación. Repita la parte (a) con esta información.
109. Encuentre la función generadora ordinaria del número
de maneras Ak de distribuir k objetos idénticos en cinco cajas
distintas, con un número par de objetos que no excede a 10
en las primeras dos cajas y entre tres y cinco en las otras
cajas.
110. Encuentre la función generadora para Ak, el número
de enteros entre 0 y 999999 cuya suma de sus d́ıgitos es k.
111. Utilice las funciones generadoras para hallar el número
de distintas maneras de recolectar $15 de 20 personas, si
6.5. Ejercicios 87
suponemos que las primeras 19 personas pueden dar $1 o
nada, mientras que la persona número 20 puede dar $5, $1,
o nada.
112. Encuentre la función generadora para Ak, el número
de soluciones enteras de la ecuación x1 + x2 + x3 + x4 = k,
con −3 ≤ xi ≤ 3.
113. ¿Cuántas diferentes maneras hay de distribuir 25 bolas
idénticas en siete cajas distintas, si la primera caja puede
contener a lo sumo 10 bolas y el resto de las cajas tiene
capacidad ilimitada para recibir bolas?
114. Encuentre la función generadora para el número de
maneras en que n dados distintos pueden mostrar una suma
igual a k.
115. Encuentre la función generadora exponencial para el
número de maneras de situar k personas en tres cuartos difer-
entes, con al menos una persona en cada cuarto. Haga lo
mismo, con la restricción de que cada cuarto quede con un
número par de personas.
116. Encuentre la función generadora para el número de
maneras de seleccionar cinco enteros no-consecutivos, entre
los enteros 1, 2, . . . , n. ¿Cuál coeficiente necesitamos para
n = 20? ¿Y en general, cuál coeficiente necesitamos para n?
117. Encuentre el número distinto de secuencias de k d́ıgitos
en base 4 que contengan un número par de 0’s y un número
impar de 1’s.
118. ¿De cuántas maneras puede recolectarse $24 de 4 niños
y k adultos, si cada persona dona al menos $1, pero cada
niño puede donar a lo sumo $4 y cada adulto puede donar a
lo sumo $7?
Caṕıtulo 7
Particiones de un entero
7.1 Introducción
¿De cuántas maneras distintas, Pn, se puede particionar un
entero positivo n como la suma de sumandos positivos y de-
crecientes?
Introducimos en este caṕıtulo los rudimentos de este in-
teresante problema, estudiado intensamente por Hardy1 y
Ramanujan2 a principios del siglo XX.
Los primeros valores de Pn se muestran en la Tabla 1.1,
a modo de ilustración.
1Godfrey Harold Hardy (1877–1947) Matemático inglés, nacido
en Cranleigh, Surrey, considerado uno de los más grandes matemáticos
ingleses del siglo XX. Proveniente de una familia pobre, desde niño
destacó su prodigio para las matemáticas.
Asistió a la escuela pública de Cranleigh con gran suceso hasta la
edad de 12 años. Obtuvo una beca para estudiar la secundaria en el
Colegio de Winchester en 1889, entrando al año siguiente. Winchester
era el mejor colegio de Inglaterra para el entrenamiento matemático
en ese entonces. Mientras estudiaba alĺı, ganó una beca para estudiar
matemática en el Trinity College Cambridge, adonde ingresó en 1896 a
realizar sus estudios doctorales. En esta misma universidad empezó a
trabajar a partir de 1900. En 1919 se trasladó a trabajar a la Universidad
de Oxford, en donde estuvo hasta 1931, cuando regresó a Cambridge a
ocupar la Cátedra Sadleirian, cuando Hobson se retiró.
Escribió muchos art́ıculos sobre el tema de la convergencia de se-
ries, integrales y otros tópicos conexos. Aunque estos trabajos le es-
tablecieron su reputación como analista, sin embargo posiblemente su
89
90 Caṕıtulo 7. Particiones de un entero
7.2 Definiciones y relaciones
por recurrencia
Definición 44 Una partición del entero positivo n en k suman-
dos positivos y decrecientes (o “partes”) es un k-étuplo de
enteros (λ1, λ2, . . . , λk), que satisface
n = λ1 + λ2 + · · ·+ λk,
λ1 ≥ λ2 ≥ · · · ≥ λk ≥ 1.
El número total de particiones del entero n en sumandos pos-
itivos y decrecientes será denotado por Pn. El número total
de particiones en exactamente k partes será denotado por
P kn .
De la Figura 7.1, se tiene que P 36 = 3, pues hay 3 parti-
ciones del entero 6 en exactamente 3 partes (4+1+1, 3+2+1,
2+2+2), mientras que P 46 = 2, pues hay solamente 2 parti-
ciones de 6 en exactamente 4 partes (3+1+1+1, 2+2+1+1).
servicio más grande a las matemáticas en este temprano peŕıodo fue su
libro Un curso de Matemática Pura (1908). Esta obra fue la primera ex-
posición rigurosa de números, funciones, ĺımites y otros, adaptada para
pregrado, que transformó la enseñanza universitaria.
Hardy fue un maestro de la colaboración matemática. En este aspecto
destaca su alianza con J. E. Littlewood, con quien trabajó intensamente
por alrededor de 35 años, produciendo matemáticas del más alto nivel.
Aún más extraordinaria fue su colaboración con el mı́tico matemático
hindú Ramanujan, a quien identificó como genio en 1913 al recibir por
correo un manuscrito de éste. De inmediato invitó a Ramanujan a Cam-
bridge y trabajó con él hasta la prematura muerte del hindú en 1920,
publicando cinco notables art́ıculos conjuntamente. Destacan también
sus trabajos en colaboración con otros grandes matemáticos, tales como
Titchmarsh, Ingham, Landau, Pólya, E. M. Wright, W. W. Rogosinski
y Riesz.
Los intereses matemáticos de Hardy cubrieron muchos tópicos de la
matemática pura, tales como el análisis diofantino, la sumación de se-
ries divergentes, las series de Fourier, la función zeta de Riemann y la
distribución de los números primos. Era el tipo de matemático que es-
peraba que su matemática nunca pudiera ser aplicada. Sin embargo,
en 1909, apenas comenzando su carrera, brindó una importante ley que
7.2. Definiciones y relaciones por recurrencia 91
n Particiones de n Pn
1 1 1
2 2 1+1 2
3 3 2+1 1+1+1 3
4 4 3+1 2+2 5
2+1+1 1+1+1+1
5 4+1 3+2
5 3+1+1 2+2+1 2+1+1+1 7
1+1+1+1+1
6 5+1 4+2
6 4+1+1 3+3 3+2+1 11
3+1+1+1 2+2+2 2+2+1+1
2+1+1+1+1 1+1+1+1+1+1
Figura 7.1: Primeros valores de Pn.
Claramente, de la definición, Pn = P 1n + P
2
n + · · ·+ P nn .
Veamos a continuación las relaciones por recurrencia para el
cálculo de P kn .
describ́ıa cómo las proporciones de los genes dominantes y recesivos
podŕıan ser propagados en una población grande.
Hab́ıa solamente otra pasión en la vida de Hardy, aparte de las
matemáticas: el cricket. Era además famoso por sus excentricidades
de todo tipo y su notorio buen humor. Su libro Apoloǵıa de un
matemático (1940) es una de las más v́ıvidas descripciones del pen-
samiento matemático y el placer que brindan las matemáticas. Otra de
sus obras principales, su libro Series Divergentes (1949), fue publicado
póstumamente.
Obtuvo muchos honores por su trabajo. En 1901 recibió el premio
Smith, conjuntamente con J. H. Jeans. Fue electo miembro de la Real
Sociedad en 1910.