Análise combinatória matemática

para su
cálculo. Sin embargo, la función generadora ordinaria sigue
siendo el mejor método para calcular los denumerantes de
cantidades pequeñas. Por ejemplo, ¿de cuántas maneras dis-
tintas puede particionarse //C100 colones, en monedas de //C50,
//C25, //C20, //C10, //C5, //C2 y //C1? La solución es el denumerante
D(100; 1, 2, 5, 10, 20, 25, 50) = 6730,
cantidad que se obtuvo directamente desarrollando la función
generadora ordinaria F (t)=
∑∞
n=0D(n; 1, 2, 5, 10, 20, 25, 50) t
n =
1/(1− t)(1− t2)(1− t5)(1− t10)(1− t20)(1− t25)(1− t25)(1− t50),
con la ayuda del paquete de matemática simbólica Maple.
8.2 Composiciones
Paralela a la teoŕıa de particiones de un entero se encuentra
la teoŕıa de las composiciones del mismo. Una composición
de un entero n es una colección ordenada de enteros positivos
cuya suma es igual a n. A diferencia de las particiones, en las
composiciones śı interesa el orden de las partes. Por ejemplo,
2+1+3 es una composición de n = 6 diferente de 3+2+1.
Es elemental comprobar que el número de composiciones
de n en exactamente m partes, cn,m es igual a
cn,m =
(
n− 1
m− 1
)
.
Luego, el número de composiciones de n, denotado por Cn,
es
Cn =
n∑
m=1
(
n− 1
m− 1
)
= 2n−1,
con C0 = 0, de donde la función generadora ordinaria de las
8.2. Composiciones 105
composiciones Cn es
C(t) =
∞∑
n=0
Cn t
n =
t
1− 2t
.
La enumeración de las composiciones está ı́ntimamente
ligada a la de las combinaciones con repetición. Si Cm(t)
denota la función generadora de las composiciones con exac-
tamente m partes, entonces se puede demostrar que
Cm(t) =
∞∑
n=1
cn,m t
m
= (t+ t2 + t3 + · · ·)m = t
m
(1− t)m
.
Las composiciones con exactamente m partes, ninguna de
las cuales es mayor que s, tiene función generadora
Cm(t; s) = (t+ t2 + · · ·+ ts)m,
mientras que la función generadora del número de composi-
ciones en exactamente m partes impares es
Om(t) = (t+ t3 + t5 + · · ·)m,
y la función generadora del número de composiciones en ex-
actamentem partes impares, todas menores o iguales a 2s+1,
es
Om(t; s) = (t+ t3 + t5 + · · ·+ t2s+1)m.
Finalmente, la función generadora del número de com-
posiciones de n en cualquier número de partes, ninguna de
las cuales excede a s, puede probarse que es igual a
C(t; s) =
∞∑
m=1
Cm(t; s) =
t− ts+1
1− 2t+ ts+1
.
106 Caṕıtulo 8. Otros tópicos de la teoŕıa de combinatoria
Algunas otras funciones generadoras de composiciones
pueden ser obtenidas, para casos particulares y restricciones
espećıficas.
8.3 Teoŕıa de Grafos
Un grafo G = (V,U) es un conjunto finito V de vértices y un
conjunto U de arcos, o parejas de vértices (x, y). Una arista
es un conjunto {x, y} de dos vértices unidos por un arco. En
los grafos hay caminos, circuitos, componentes conectadas,
cliques, cadenas, ciclos, valencias, números cromáticos, ı́ndices
ćıclicos y otros conceptos involucrados.
La teoŕıa de grafos es un campo muy vasto de la combi-
natoria en el cual se realiza mucha investigación en la actu-
alidad. Existen libros y tratados completos y profundos que
se dedican al estudio exclusivo de esta interesante materia.
Los árboles, las redes, las series paralelas y los grafos
lineales son casos especiales de grafos. En este trabajo, por
su carácter introductorio, no hemos presentado nada acerca
de la teoŕıa de grafos, a excepción de los grafos mencionados
en el caṕıtulo 5.
8.4 Teoŕıa de Ramsey
Una de las ideas más simples y naturales en el pensamiento
matemático es el Principio del Palomar , también llamado
Principio de los n cajones de Dirichlet , el cual establese lo
siguiente:
Si hay más palomas que palomares, entonces al-
gunos palomares deberán contener al menos dos
palomas. Más generalmente, si tenemos más de
k veces palomas que palomares, entonces algún
palomar deberá contener al menos k+1 palomas.
8.4. Teoŕıa de Ramsey 107
Por ejemplo, en una ciudad con más de 1,000,000 de habi-
tantes (como San José), existirán al menos 11 personas que
tienen el mismo número de cabellos en su cabeza. En efecto,
se sabe que una cabellera promedio tiene alrededor de 100,000
cabellos. Entonces, tenemos más de k = 10 veces más habi-
tantes que tipos de cabezas (cada tipo de cabeza corresponde
al número de cabellos en ella), de donde existirá un grupo de
al menos k + 1 = 11 habitantes con la misma cantidad de
cabellos en su cabeza.
En 1930 Frank Ramsey1 demostró un notable teorema
como parte de sus investigaciones en lógica formal. Su teo-
rema es una profunda generalización del Principio del Palo-
mar. Como ha sucedido con algunas otras ideas hermosas
en las matemáticas, el teorema de Ramsey extiende justa-
mente los aspectos correctos de una observación elemental
y deriva consecuencias que son extremadamente naturales,
aunque lejanas de ser obvias. Recientemente se ha recono-
cido que muchos resultados en la teoŕıa de combinatoria y en
otras áreas tienen el mismo sabor que el teorema de Ram-
sey. El intento por capturar este sabor común y desarrollar
las ideas generales basadas en él, ha conducido a la prolif-
1Frank Plumpton Ramsey (1903–1930) Matemático inglés,
nacido en el condado de Cambridge, hijo de un tutor de matemática.
Realizó sus estudios de matemática en la Universidad de Cambridge,
obteniendo su doctorado en 1923.
Trabajó brevemente en Viena y luego retornó a Inglaterra, obte-
niendo una plaza en el King’s College, donde hizo una corta pero bril-
lante carrera universitaria. Sus lecciones sobre los fundamentos de las
matemáticas causaban una fuerte impresión en los jóvenes estudiantes,
por su notable claridad y entusiasmo.
Realizó interesantes y profundas investigaciones en los campos de los
fundamentos de la matemática, la combinatoria y la lógica, destacándose
particularmente por sus resultados que condujeron al desarrollo de la
actualmente llamada Teoŕıa de Ramsey . Sus principales publicaciones
fueron “Los fundamentos de las Matemáticas”, en la cual realizó algunas
mejoras parciales a los trabajos de Russell y Whitehead y “Sobre un
Problema en Lógica Formal”, publicado en 1930 —el mismo año de su
muerte— en el cual planteó y resolvió el resultado central que dio origen
108 Caṕıtulo 8. Otros tópicos de la teoŕıa de combinatoria
eración de resultados que constituyen lo que se ha convenido
en llamar Teoŕıa de Ramsey . En muchos casos —incluyendo
el propio teorema original de Ramsey— se establece tan solo
la existencia de ciertos números mı́nimos. Un largo esfuerzo
ha sido llevado a cabo para encontrar los valores exactos en
algunos pocos casos y cotas superiores en general para estos
números de Ramsey .
Consideremos el siguiente problema: Dado un entero pos-
itivo k, qué tan grande (Rk) debe ser un grupo de personas
para asegurar que, o bien existe un subconjunto de k per-
sonas en el grupo que mutuamente se conocen entre śı, o
bien existe un subconjunto de k personas en el grupo que
mutuamente no se conocen entre śı?
Una “simple” enumeración de casos nos lleva a la solución
del problema cuando k = 3, la cual es R3 = 6. Ya para k = 4
el problema se nos escapa de toda posibilidad práctica de
enumeración de casos, aunque se sabe que la solución es R4 =
18, esto es, en un grupo de 18 o más personas, siempre habrá
4 personas que se conocen mutuamente o 4 personas que no
se conocen mutuamente. Sorprendentemente, los valores de
Rk para k ≥ 5 se desconocen (problema aún abierto). Tan
solo se conocen algunas cotas superiores bastante burdas,
como consecuencia del teorema de Ramsey, el cual pasamos
a enunciar.
Sea S un conjunto con n elementos y sea Pr(S) el conjunto
de todos los subconjuntos de S con r elementos. Supongamos
que Pr(S) está particionado en t componentes o coloraciones
A1, A2, . . . , At:
Pr(S) = A1 ∪A2 ∪ · · · ∪At.
a la teoŕıa de Ramsey. También publicó notables art́ıculos sobre teoŕıa
de probabilidades, economı́a y filosof́ıa.
Ramsey era un hombre de gran estatura, modesto, sencillo y desin-
hibido, que