Teoría Combinatoria - J

Vista previa del material en texto

La Universidad del Zulia
Facultad Experimental de Ciencias
Departamento de Matemática y Computación
Teoŕıa Combinatoria
José Heber Nieto Said
Maracaibo, 1996
TEORIA COMBINATORIA
ISBN 980-232-573-2
autor: José H. Nieto
Departamento de Matemática y Computación
Facultad Experimental de Ciencias
La Universidad del Zulia - Apartado Postal 526
Maracaibo, Venezuela
Fax: 58 61 515390
dirección electrónica: jhnieto@luz.ve
c© La Universidad del Zulia, 1996.
Índice General
1 Conceptos básicos 1
1.1 Qué es la Combinatoria . . . . . . . . . . . . . . . . . . . . . 1
1.2 Oŕıgenes y evolución de la Combinatoria . . . . . . . . . . . . 2
1.3 Los principios básicos . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2 Las configuraciones clásicas 13
2.1 Arreglos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Arreglos con repetición . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Permutaciones . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4 Permutaciones con repetición . . . . . . . . . . . . . . . . . . 16
2.5 Combinaciones . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.6 Combinaciones con repetición . . . . . . . . . . . . . . . . . . 19
2.7 Algoritmos combinatorios . . . . . . . . . . . . . . . . . . . . 21
2.8 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3 Coeficientes binomiales y multinomiales 25
3.1 Los coeficientes binomiales . . . . . . . . . . . . . . . . . . . . 25
3.2 Coeficientes multinomiales . . . . . . . . . . . . . . . . . . . . 32
3.3 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4 Principio de Inclusiones y Exclusiones y aplicaciones 39
4.1 El Principio de Inclusiones y Exclusiones . . . . . . . . . . . . 39
4.2 Funciones sobreyectivas . . . . . . . . . . . . . . . . . . . . . 41
4.3 Desarreglos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.4 Aplicaciones a la teoŕıa de números . . . . . . . . . . . . . . . 43
4.5 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
iii
5 Relaciones de recurrencia y funciones generatrices 47
5.1 Números de Fibonacci . . . . . . . . . . . . . . . . . . . . . . 47
5.2 Funciones generatrices . . . . . . . . . . . . . . . . . . . . . . 50
5.3 Relaciones de recurrencia lineales . . . . . . . . . . . . . . . . 53
5.4 Números de Catalan . . . . . . . . . . . . . . . . . . . . . . . 58
5.5 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
6 Permutaciones y particiones 65
6.1 Permutaciones . . . . . . . . . . . . . . . . . . . . . . . . . . 65
6.2 Números de Stirling de primera clase . . . . . . . . . . . . . . 69
6.3 Aplicación al análisis de algoritmos . . . . . . . . . . . . . . . 73
6.4 Particiones, números de Stirling de segunda clase y números
de Bell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
6.5 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
7 Teoremas de existencia 85
7.1 El Teorema de Ramsey . . . . . . . . . . . . . . . . . . . . . . 86
7.2 Aplicaciones a la teoŕıa de grafos . . . . . . . . . . . . . . . . 89
7.3 Una aplicación geométrica . . . . . . . . . . . . . . . . . . . . 92
7.4 El Teorema de Graham - Rothschild . . . . . . . . . . . . . . 94
7.5 Conjuntos parcialmente ordenados . . . . . . . . . . . . . . . 96
7.6 Sistemas de representantes distintos . . . . . . . . . . . . . . 99
7.7 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
8 Enumeración bajo acción de grupos 103
8.1 Acción de un grupo sobre un conjunto . . . . . . . . . . . . . 104
8.2 La Acción de Polya . . . . . . . . . . . . . . . . . . . . . . . . 107
8.3 Enumeración de grafos no isomorfos . . . . . . . . . . . . . . 112
8.4 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
iv
Prefacio
Este libro nació a partir de las notas de varios cursos de matemática discre-
ta y de combinatoria dictados por el autor en la Facultad de Ciencias de la
Universidad del Zulia durante los últimos diez años, para estudiantes de ma-
temática y de computación. Una versión parcial del texto [N1] fué utilizada
por estudiantes de esos y otros cursos. En 1988 esta obra fué seleccionada
entre las ganadoras del Concurso de Textos Universitarios auspiciado por
el Vice-Rectorado Académico de LUZ. Sin embargo, dificultades de orden
tipográfico retardaron y finalmente impidieron su oportuna publicación. La
presente edición se debe a la iniciativa del profesor Gustavo Oquendo, quien
preparó la versión en LATEX en tiempo record.
Esta obra se benefició de los aportes y comentarios de mis alumnos y de
varios colegas del Departamento de Matemática de la F.E.C., en particular
del profesor Genaro González, con quien sostuve largas conversaciones sobre
temas combinatorios. Deseo expresar aqúı mi agradecimiento a todos ellos,
aśı como al profesor Gustavo Oquendo y al Instituto de Cálculo Aplicado
de la Facultad de Ingenieŕıa de LUZ, en cuyas instalaciones se realizó el
trabajo de composición del texto. Debo aclarar sin embargo que cualquier
posible error es de mi exclusiva responsabilidad. Aśımismo agradezco al
Vice-rectorado Académico de LUZ el apoyo brindado a la presente edición.
José Heber Nieto Said
Maracaibo, 14 de febrero de 1996.
vi
Introducción
En los últimos años el interés por la Combinatoria ha aumentado conside-
rablemente. En gran parte esto se debe al desarrollo de la Ciencia de la
Computación, en la cual juega un rol central el concepto de algoritmo. Para
estimar la eficiencia de un algoritmo es necesario contar el número de veces
que se ejecutará cada paso del mismo, y esto es un t́ıpico problema combi-
natorio. Asimismo la Combinatoria tiene aplicaciones en las ciencias f́ısicas
(ver por ejemplo la discusión del modelo de Ising en [P1]). Por otra parte
las técnicas combinatorias son ampliamente usadas en toda la Matemática,
desde la Teoŕıa de Grupos hasta la Teoŕıa de Probabilidades. La demostra-
ción de Wielandt del teorema de Sylow (ver [H3]) y la teoŕıa de paseos al
azar (ver [F1]) son dos hermosos ejemplos de lo afirmado. Otros ejemplos se
encuentran en geometŕıa combinatoria (ver [H1]), teoŕıa de grafos (ver [B2],
[H2]), optimización combinatoria (ver [F2]), etc.
Sin embargo, no abundan las obras dedicadas a la exposición sistemáti-
ca de los principios fundamentales de la Combinatoria. Por ese motivo es
frecuente encontrar, en libros dedicados a diversas ramas de la matemáti-
ca, estad́ıstica y computación, secciones más o menos extensas en las cuales
se desarrollan los conceptos y técnicas combinatorias requeridos por cada
autor. Se trata sin embargo de exposiciones parciales, más o menos circuns-
criptas a ciertas necesidades espećıficas. En idioma castellano, en especial,
las obras de Combinatoria son muy escasas y de dif́ıcil obtención. Estas con-
sideraciones nos motivaron a preparar este trabajo, en el cual tratamos de
afirmar la unidad de la Combinatoria desarrollándola a partir de un pequeño
número de principios básicos. No pretendemos sin embargo realizar una ex-
posición exhaustiva de los innumerables problemas, resultados y teoŕıas que
comprende la Combinatoria, sino más bien exponer sus fundamentos y pre-
sentar un buen número de tópicos representativos de las diversas direcciones
que ha tomado la investigación en el área. La selección hecha inevitable-
mente refleja de algún modo las preferencias e intereses del autor, aunque
hemos hecho un esfuerzo por inclúır un conjunto variado y equilibrado de re-
sultados, que puedan ejemplificarse con aplicaciones a diferentes campos de
la matemática (algebra, geometŕıa, teoŕıa de grafos, probabilidades, teoŕıa
de números, etc.)
La exposición trata de enfatizar en todo momento el enfoque t́ıpicamen-
te combinatorio de los problemas tratados, aunque también se explican (y
utilizan cuando es necesario)otros métodos. Los números de Stirling, por
ejemplo, se definen por su propiedad de contar el número de permutaciones y
particiones de determinada clase, y no de la manera usual como coeficientes
de ciertos cambios de base en un espacio vectorial de polinomios.
Al final de cada caṕıtulo se incluyen ejercicios y problemas que ilustran
o ampĺıan el material tratado y brindan al lector la oportunidad de poner
a prueba su comprensión del texto. En un Apéndice se proporcionan solu-
ciones y sugerencias, pero las mismas no debeŕıan ser consultadas antes de
haber hecho un serio esfuerzo para solucionar cada problema. Este tipo de
actividad es fundamental para aprovechar cabalmente este o cualquier otro
libro de matemática.
Los prerrequisitos para comprender este libro no son muchos, siendo
suficiente lo que suele enseñarse en un curso de matemáticas generales de
nivel universitario. Las excepciones se encuentran en el Caṕıtulo 8, que
presupone cierta familiaridad con la teoŕıa de grupos, y en algunos ejemplos
y ejercicios.
El texto puede ser usado de varias maneras. Los tres primeros caṕıtulos
son de naturaleza elemental y proporcionan una introducción a la combina-
toria adecuada para cursos universitarios de matemática general, algebra,
probabilidad y otros que lo requieran. Los caṕıtulos 4, 5 y 6 contienen
material algo más sofisticado y son apropiados para cursos de matemáti-
ca discreta, en especial para carreras de computación, por sus aplicaciones
al análisis de algoritmos. Los dos últimos caṕıtulos requieren una mayor
madurez matemática, y están dirigidos fundamentalmente a estudiantes y
profesores de esta disciplina.
viii
Caṕıtulo 1
Conceptos básicos
“La matemática es rica en técnica y argumentos. En esta gran
variedad de situaciones una de las más esenciales herramien-
tas de trabajo es el conteo. Y sin embargo, aunque parezca
extraño, es una de las cosas más dif́ıciles. Al hablar de conteo,
a lo que queremos referirnos es al proceso de saber en forma
precisa cuántas son las posibilidades en situaciones altamente
complejas.”
I.N. Herstein [H3] pag. 87–88.
1.1 Qué es la Combinatoria
Si se les pregunta qué es la Combinatoria, la mayoŕıa de los matemáticos
responderán algo aśı como “el arte y ciencia de contar”. Sin embargo esta
definición es inadecuada, pues t́ıpicos problemas combinatorios como el de
describir todos los grafos con un cierto número de vértices o el de la exis-
tencia de cuadrados latinos ortogonales, quedaŕıan fuera de su alcance. Si
bien los métodos de recuento forman parte esencial de la Combinatoria, ésta
contempla también otros aspectos. Además de contar el número de árbo-
les con n vértices, por ejemplo, interesa también describirlos, decir cuáles
son. En este sentido Claude Berge [B1] propone definir la Combinatoria
como el estudio de las configuraciones formadas con los elementos de un
conjunto finito, entendiendo por tales las aplicaciones del conjunto en otro
(posiblemente provisto de cierta estructura) que satisfagan unas restriccio-
nes determinadas. Dentro de esta concepción pueden considerarse varios
aspectos, entre ellos: el estudio de configuraciones conocidas, el estudio de
2 José H. Nieto
la existencia de ciertas configuraciones, el conteo del número de configura-
ciones de un tipo dado, la enumeracion o descripción de configuraciones, la
optimización combinatoria, es decir la determinación de las configuraciones
que maximizan o minimizan una función dada, etc.
Otros autores, como Aigner [A1], distinguen dentro de la Combinatoria
varias áreas principales, tales como los problemas de enumeración, el estudio
de estructuras de orden en conjuntos finitos, los teoremas de existencia tipo
Ramsey, Sperner, etc. y el estudio de configuraciones. En cualquier caso el
campo abierto a la Combinatoria es amplio y fascinante, repleto de bellos
resultados e interesantes problemas abiertos.
1.2 Oŕıgenes y evolución de la Combinatoria
En cierto sentido la combinatoria puede considerarse tan vieja como la pro-
pia Matemática, ya que la operacion básica de contar los elementos de un
conjunto está ligada al origen mismo del concepto de número en los tiempos
prehistóricos.
Los matemáticos griegos no prestaron mucha atención a los problemas
combinatorios, si exceptuamos el estudio de los números poligonales reali-
zado por los pitagóricos. Según Bourbaki [B3] la fórmula
(
n
2
)
= n(n−1)2 ya
era conocida en el siglo III de nuestra era. En el siglo XII el matemático
hindú Bhaskara conoćıa ya la fórmula general para
(
n
p
)
y Lev́ı Ben Gerson
(1288–1344) realizó un estudio más detallado de las permutaciones, arreglos
y combinaciones de un conjunto de objetos. Sin embargo sus escritos apa-
rentemente no alcanzaron mucha difusión, y varios de sus resultados fueron
redescubiertos varias veces por los matemáticos de los siglos siguientes.
Cardano (1501–1576) mostró que el número de partes de un conjunto de
n elementos es 2n. Nicolo Fontana de Brescia, contemporáneo de Cardano y
más conocido como Tartaglia, estudió un rectángulo aritmético equivalente
al triángulo que posteriormente recibiŕıa el nombre de Pascal y que apare-
ció en su obra (en parte póstuma) “Tratado general sobre el número y la
medida” (1556–1560).
Pascal y Fermat, en el curso de sus estudios sobre los juegos de azar y en
particular sobre el problema de “la división de la apuesta” (planteado por el
caballero de Meré) volvieron a encontrar la fórmula para
(
n
p
)
. Dichos estudio
constituyeron, por otra parte, el punto inicial del cálculo de probabilidades
moderno. Pascal parece haber sido el primero en relacionar los números
(
n
p
)
con el teorema del binomio (el cual en alguna forma era ya conocido por los
Teoŕıa Combinatoria 3
árabes en el siglo XIII y por los chinos en el siglo XIV). Publicó su célebre
“Tratado del triángulo aritmético” en 1665 y aunque dicho triángulo ya era
conocido por matemáticos anteriores como Tartaglia, Stevin y Stifel, desde
entonces es conocido con su nombre.
Leibniz (1646–1716) dedicó bastante atención a la Combinatoria, no sólo
desde el punto de vista matemático sino también desde una perspectiva fi-
losófica. En un ensayo de juventud (“De Arte Combinatoria”, 1666) escribe:
. . . todo brota interiormente de la teoŕıa de las variaciones, la
cual conduce al esṕıritu que a ella se conf́ıa, casi por śı mismo,
a través de la totalidad infinita de los problemas, abarcando en
śı la armońıa del universo, la estructura más ı́ntima de las cosas
y toda la serie de las formas.
Hacia 1676 obtuvo la fórmula para los coeficientes multinomiales, redescu-
bierta y publicada por De Moivre veinte años más tarde.
Newton extendió el teorema del binomio al caso de exponentes fracciona-
rios. De Moivre (1667–1754) usó por primera vez funciones generatrices para
resolver la relación de recurrencia xn = xn−1 + xn−2, la cual tiene su origen
en el problema de la multiplicación de los conejos tratado por Leonardo de
Pisa (Fibonacci) en su “Liber abaci” hacia el año 1202.
Bernoulli extendió la teoŕıa de combinaciones en su “Ars Conjectandi”
(1713), el primer libro de importancia dedicado al cálculo de probabilida-
des. Euler (1707–1783) hizo aportes fundamentales. Debemos destacar su
solución al problema de los siete puentes de Königsberg usando argumentos
combinatorios, que lo convirtieron simultáneamente en el padre de la Topo-
loǵıa y de la Teoŕıa de Grafos. También desarrolló el método de las funciones
generatrices, aplicándolo al problema de las particiones (entre otros).
Cailey (1821–1895) atacó el problema de determinar el número de isóme-
ros de los hidrocarburos saturados CnH2n+2, para cualquier valor de n, lo cual
equivale a un problema de enumeración de cierto tipo de árboles.
En el presente siglo F. P. Ramsey (1903–1930) descubrió un importante
teorema combinatorio de existencia trabajando en el contexto de la lógica
matemática.En la década de 1930 Paul Erdös y otros matemáticos húngaros
dieron un nuevo impulso a la Combinatoria. De hecho Erdös ha sido, hasta
el presente, uno de los investigadores más proĺıficos en este campo.
Motivado en problemas de la teoŕıa de grafos con origen en la qúımica,
como Cailey, George Polya [P2] desarrolló en 1937 una poderosa técnica
(en parte anticipada por J. H. Redfield [R1]) para resolver problemas de
4 José H. Nieto
enumeración. Su método, basado en la teoŕıa de grupos, ha tenido gran
influencia en el desarrollo contemporáneo de la Teoŕıa combinatoria.
En la actualidad la Combinatoria “pura” evoluciona en la dirección de
buscar principios y teoŕıas unificadoras que permitan ordenar y sistematizar
el gran número de resultados existentes, aparentemente dispersos e incone-
xos. Ejemplo de tales teoŕıas son: el estudio combinatorio de los conjuntos
parcialmente ordenados (ver [A1]) y en particular la extensión a estos con-
juntos de las funciones de Möbius y fórmulas de inversión (ver [R7], [RS1] y
[G2]), la teoŕıa de matroides (ver [A1]), los “tableaux” (ver [B1] y [R4]) y la
teoŕıa de especies combinatorias (ver [M2]). Al mismo tiempo, tiene lugar
un gran desarrollo de las ramas más ricas en aplicaciones inmediatas, tales
como la optimización combinatoria.
1.3 Los principios básicos
Denotaremos Nn al conjunto de los números naturales entre 1 y n, es de-
cir Nn = {1, 2, . . . , n} = {i ∈ N : 1 ≤ i ≤ n}. Dos conjuntos A y B se
dicen coordinables si existe una función biyectiva f : A → B. En este ca-
so escribiremos A ∼ B. Un conjunto A es finito si es vaćıo o si existe un
número natural n tal que A ∼ Nn. En este caso, si f : Nn → A es biyec-
tiva, poniendo ai = f(i) para i = 1, . . . , n podemos denotar el conjunto A
como {a1, a2, . . . , an}. Los conjuntos finitos pueden caracterizarse también
intŕınsecamente por la propiedad de no ser coordinables con ninguno de sus
subconjuntos propios (ver por ejemplo [R3]). Denotaremos mediante |A|
al número de elementos (o cardinal) del conjunto finito A. Si A es vaćıo,
entonces |A| = 0, y si A ∼ Nn entonces |A| = n.
En todo lo que sigue, salvo mención expresa en sentido contrario, consi-
deraremos solamente conjuntos finitos.
Principio de correspondencia. 1.3.1. Si A ∼ B entonces |A| = |B|.
Demostración. Si A = ∅ y A ∼ B entonces B = ∅ y |A| = |B| = 0. Si
|A| = n y f : Nn → A y g : A → B son biyectivas, entonces la composición
g ◦ f : Nn → B es biyectiva, lo cual prueba |B| = n = |A|
El principio de correspondencia es usado muy frecuentemente en Combina-
toria. A pesar de su sencillez permite resolver muchos problemas de conteo
Teoŕıa Combinatoria 5
de manera sorprendente, como en el ejemplo siguiente:
Ejemplo: En un campeonato de béisbol jugado por el sistema de elimina-
torias se enfrentan n equipos. En cada ronda los equipos perdedores salen
del torneo. Al formar los pares de equipos que se van a enfrentar puede
eventualmente quedar un equipo sin jugar; éste descansa y pasa a la ronda
siguiente. Se desea saber cuántos juegos se realizarán durante el campeona-
to.
Aparentemente una forma de resolver este problema seŕıa contar el núme-
ro de juegos en cada ronda y sumar. Pero este cálculo se complica por la
posibilidad de tener un número impar de equipos en algunas rondas, y un
número par en otras. El caso más simple se da cuando el número de equipos
participantes es una potencia de 2, digamos n = 2k. Entonces evidentemen-
te habrá k rondas, y el número total de juegos será 2k−1 + 2k−2 + · · · + 1,
o sea 2k − 1 = n − 1. Usando el principio de correspondencia podemos
demostrar que, en general, el número de partidos será siempre n − 1. En
efecto, al finalizar el campeonato tendremos un equipo campeón y n − 1
equipos eliminados. Cada uno de ellos fue eliminado en algún partido (y
sólo en uno), y en cada partido fue eliminado un equipo. Esto significa que
la correspondencia que asigna a cada partido jugado el equipo eliminado en
dicho partido, es biyectiva. Por lo tanto se jugaron tantos partidos como
equipos resultaron eliminados, esto es n− 1.
Principio de la suma. 1.3.2. Si A∩B = ∅ entonces |A∪B| = |A|+ |B|.
Demostración: Este principio es obvio, pero si se desea una demostra-
ción rigurosa puede procederse de la siguiente manera: sean f : Nm → A y
g : Nn → B ambas biyectivas. Entonces la función h : Nm+n → A ∪B defi-
nida del modo siguiente:
h(i) =
{
f(i) si i ≤ m
g(i−m) si m < i ≤ m+ n.
es biyectiva, probando aśı que |A ∪B| = m+ n = |A|+ |B|.
El principio de la suma se enuncia a veces en los términos siguientes: “Si un
suceso A puede ocurrir de m maneras y otro suceso B puede ocurrir de n
maneras, y no pueden ocurrir ambos simultáneamente, entonces el suceso ‘A
o B’ puede ocurrir dem+nmaneras”. Este enunciado puede parecer un poco
impreciso, pero es posible convertirlo en una proposición matemáticamente
6 José H. Nieto
aceptable mediante el modelo siguiente: sea X un conjunto cuyos elementos
representan los posibles resultados de un cierto experimento E. Llamemos
sucesos a los subconjuntos de X. Si A es un suceso y el resultado x del
experimento E pertenece al conjunto A, entonces diremos que “ocurrió el
suceso A”. Sea B otro suceso. Es claro que el suceso ‘A o B’ ocurre cuando
el resultado del experimento E está en A∪B, y decir que “A y B no pueden
ocurrir simultáneamente” significa que A ∩ B = ∅. Asimismo la frase “A
puede ocurrir de m maneras” no significa otra cosa que |A| = m. Vemos
entonces que el enunciado del principio de la suma en términos de sucesos,
bajo esta interpretación, afirma que si |A| = m, |B| = n y A∩B = ∅ entonces
|A ∪B| = m+ n, lo cual no es más que el enunciado original.
Veamos algunas consecuencias del principio de la suma:
Proposición 1.3.3. Si A ⊂ B entonces |A| ≤ |B|.
Demostración: Si A ⊂ B entonces B = A ∪ (B\A) y A ∩ (B\A) = ∅, por
lo tanto |B| = |A|+ |B\A| ≥ |A|
Proposición 1.3.4. Si f : A→ B es inyectiva entonces |A| ≤ |B|.
Demostración. Si f es inyectiva entonces A ∼ f(A), por lo tanto |A| =
|f(A)| ≤ |B|.
Proposición 1.3.5. Si f : A→ B es sobre entonces |A| ≥ |B|.
Demostración. Para cada elemento b ∈ B escojamos una preimagen suya
g(b) en A. De este modo resulta una función g : B → A inyectiva, ya que
g(b) = g(b′) implicaŕıa b = f(g(b)) = f(g(b′)) = b′. Entonces por 1.3.4
tenemos |B| ≤ |A|.
Proposición 1.3.6. Si A1, . . . , An son disjuntos dos a dos entonces:
|A1 ∪ · · · ∪An| = |A1|+ · · ·+ |An|.
Demostración. Esta generalización del principio de la suma se prueba
fácilmente por inducción.
(Más adelante veremos una generalización aún mayor de este resultado: el
principio de inclusiones y exclusiones)
Principio del producto (versión 1) 1.3.7. |A×B| = |A| · |B|.
Teoŕıa Combinatoria 7
Demostración. Este principio puede visualizarse disponiendo todos los
elementos del producto cartesiano A × B en una tabla. Suponiendo que
A = {a1, . . . , am} y B = {b1, . . . , bn} entonces los elementos de A × B son
los pares ordenados:
(a1, b1) (a1, b2) . . . (a1, bn)
(a2, b1) (a2, b2) . . . (a2, bn)
...
...
...
...
(am, b1) (am, b2) . . . (am, bn)
Se ve claramente que el cuadro tiene m filas y n columnas, y por lo tanto
m · n = |A| · |B| elementos.
Una demostración más rigurosa podŕıa seguir las siguientes lineas: si A
o B son vaćıos entonces A×B es vaćıo y se cumple |A×B| = 0 = |A| · |B|.
En caso contrario sean f : Nm → A y g : Nn → B biyectivas y definamos
h : Nmn → A × B de la manera siguiente: dado i ∈ Nmn sean q y r el
cociente y el resto respectivamente de la división entera de i − 1 entre m.
Entonces,
h(i) = (f(r + 1), g(q + 1))
la función h aśı definida es biyectiva: su inversa es
h−1(f(k), g(j)) = (j − 1)m+ k
lo cual prueba que |A×B| = m · n.
Un enunciado algo más general del principio del producto es el siguiente:
Principio del producto (versión 2) 1.3.8. Si un primer objeto puede
escogerse entre m posibles, y después de realizada esta selección puede es-
cogerseun segundo entre n posibles, entonces pueden escogerse m · n pares
diferentes.
Demostración. En esta versión el conjunto de objetos entre los cuales se
puede seleccionar el segundo puede depender del primer objeto elegido. La
situación puede representarse en el cuadro:
(a1, b11) (a1, b12) . . . (a1, b1n)
(a2, b21) (a2, b22) . . . (a2, b2n)
...
...
...
...
(am, bm1) (am, bm2) . . . (am, bmn)
8 José H. Nieto
y vemos que también aqúı el número total de pares es m · n.
El principio del producto puede generalizarse fácilmente para varios fac-
tores:
Principio del producto (versión 3) 1.3.9.
|A1 ×A2 × · · · ×An| = |A1| · |A2| · · · · · |An|
Demostración: inducción en n, basándonos en (1.3.7).
La generalización correspondiente de la segunda versión del principio
seŕıa la siguiente:
Principio del producto (versión 4) 1.3.10. Si un primer objeto puede
escogerse entre n1 posibles, y para cada selección puede escogerse un segundo
objeto entre n2 posibles, y luego un tercero entre n3 posibles, etc., hasta un
k-esimo objeto que se puede escoger de nk maneras, entonces el número de
grupos ordenados de k objetos que pueden seleccionarse es n1 · n2 · · · · · nk.
Demostración: Inducción en k, basándonos en (1.3.8).
Ejemplo: Si en la serie armónica 1 + 1/2 + · · · + 1/n + · · · (que como
se sabe es divergente) se suprimen todos los términos en cuyo denominador
aparezcan uno o más sietes (tales como 1/7, 1/17, etc.) ¿la serie resultante
converge o diverge?.
Para responder a esta pregunta calculemos en primer lugar la cantidad
de números de n cifras entre cuyos d́ıgitos no aparece el 7. La primera cifra
puede escogerse de ocho maneras, ya que no puede ser ni 7 ni 0. Cada una de
las restantes puede escogerse de 9 maneras. La cantidad buscada es entonces
8 · 9n−1. Todos los términos de la serie en cuestión con denominador de n
cifras son menores que 10−(n−1) por lo tanto la serie se puede acotar por la
serie geométrica:
8 + 8 ·
(
9
10
)
+ 8 ·
(
9
10
)2
+ · · ·+ 8 ·
(
9
10
)n−1
+ · · · = 80
por lo cual la serie propuesta es convergente. Este resultado puede parecer
paradójico, pues aparentemente al quitar los términos con 7 estamos quitan-
do relativamente pocos términos de la serie armónica. Pero es una ilusión
provocada por el examen de los números de pocas cifras. De hecho, entre los
números de n cifras la proporción de números sin sietes es (8/9)(9/10)n−1,
la cual tiende a cero al aumentar n.
Teoŕıa Combinatoria 9
Ejemplo: ¿De cuántas maneras pueden colocarse una torre blanca y
una torre negra en un tablero de ajedrez de modo que se ataquen?
El tablero de ajedrez tiene 8 × 8 = 64 casillas, y este es el número de
maneras en que se puede ubicar la torre blanca. Una vez ubicada la torre
blanca, la torre negra debe colocarse en una casilla de la misma columna
o fila ocupada por la torre blanca. Como el número de estas casillas es
7 + 7 = 14 la respuesta al problema es 64× 14 = 896.
Observemos que si se tratase de colocar dos torres del mismo color, indis-
tinguibles, defendiéndose mutuamente, entonces el número anterior debeŕıa
dividirse entre 2, resultando 448.
Como otra aplicación interesante del principio del producto demostrare-
mos el siguiente resultado:
Proposición (Erdös - Szekeres [ES1]) 1.3.11. Toda sucesión de
mn+ 1 números diferentes contiene una subsucesión creciente de longitud
mayor que n o una subsucesión decreciente de longitud mayor que m.
Demostración. Sea a1, a2, . . . , amn+1 la sucesión y denotemos li la longitud
de la subsucesión decreciente más larga que comience con ai. Análogamente
sea Li la longitud de la subsucesión creciente más larga que comience en ai.
Supongamos por absurdo que li ≤ m y que Li ≤ n para i = 1, . . . ,mn +
1. Sea f : Nmn+1 → Nm × Nn la aplicación definida asi: f(i) = (li, Li).
Esta función es inyectiva, ya que si i < j entonces o bien ai < aj o bien
ai > aj . En el primer caso anteponiendo el elemento ai a una subsucesión
creciente de Lj elementos que comience con aj obtenemos una subsucesión
creciente de primer elemento ai y Lj + 1 elementos, probando que Li > Lj .
En el segundo caso se prueba por un razonamiento similar que li > lj , y
entonces en cualquier caso se tiene que f(i) 6= f(j). Pero esto conduce a
una contradicción, ya que por (1.3.4) tendŕıamos que |Nmn+1| ≤ |Nm×Nn|,
o sea mn+ 1 ≤ mn, lo cual es absurdo.
El conjunto de todas las funciones de un conjunto A en otro B lo deno-
tamos BA. Si A y B son finitos entonces el cardinal de BA viene dado por
la siguiente proposición:
Proposición 1.3.12. |BA| = |B||A|.
Demostración. Supongamos que |A| = n y sea f : Nn → A biyectiva. Esta
función f nos permite definir una correspondencia T : BA → BNn poniendo
T (h) = h◦f para toda h ∈ BA. Esta correspondencia es biyectiva, ya que f
10 José H. Nieto
lo es. Pero BNn no es otra cosa que el producto cartesiano B ×B × · · · ×B
(n factores) y entonces por (1.3.9)
|BA| = |BNn | = |B ×B × · · · ×B| = |B|n = |B||A|
Proposición 1.3.13. El conjunto de partes de un conjunto finito A tiene
2|A| elementos.
Demostración. A cada subconjunto X de A hagámosle corresponder su
función caracteŕıstica fX : A→ {0, 1} definida aśı:
fX(x) =
{
1 si x ∈ X
0 en caso contrario
De este modo resulta una correspondencia entre subconjuntos de A y fun-
ciones de A en {0, 1}, y fácilmente se ve que se trata de una biyección. Por
lo tanto en virtud de (1.3.12) el número de elementos del conjunto de partes
de A es |2A| = 2|A|
Usaremos la notación [x]n para indicar el producto de n factores decre-
cientes x(x−1)(x−2) · · · (x−n+1), a veces llamado factorial inferior de x de
orden n. Observemos que [n]n es el factorial ordinario n! = n(n−1) · · · 3·2·1.
Adoptaremos además la convención [x]0 = 1.
Proposición 1.3.14. El número de funciones inyectivas de un conjunto A
en otro B es [|B|]|A|.
Demostración. Sean n = |A| y m = |B|. Si n > m entonces por (1.3.4) no
hay funciones inyectivas de A en B y el producto m(m− 1) · · · (m− n+ 1)
nos da el resultado correcto pues uno de los factores será nulo. Supongamos
entonces que n ≤ m y sea A = {a1, . . . , an}. Si queremos definir una
función inyectiva de A en B, tenemos m posibilidades para elegir f(a1),
m − 1 para f(a2), . . . , m − n + 1 posibilidades para f(an). Entonces, por
el principio del producto, el número de funciones inyectivas de |A| en |B| es
m(m− 1) · · · (m− n+ 1) = [m]n.
1.4 Ejercicios
1. Pruebe que si A y B son conjuntos finitos entonces se cumple
|A ∪B| = |A|+ |B| − |A ∩B|
Teoŕıa Combinatoria 11
2. Sean A y B dos conjuntos finitos y f una función de A sobre B tal
que |f−1(b)| = k (constante) para todo b ∈ B. Pruebe que entonces
|A| = k · |B|
3. (Principio de Dirichlet)
Sean a1, . . . ak enteros no negativos. Si n objetos se distribuyen en
k cajas C1, . . . , Ck y n ≥ a1 + . . . + ak − k + 1 entonces para algún
i (1 ≤ i ≤ k) la caja Ci contiene al menos ai objetos.
4. En un acto deben hablar Luis, Maŕıa, Pedro, Pablo y Luisa. ¿De
cuántas maneras se puede confeccionar la lista de oradores con la con-
dición de que Luis hable antes que Pedro? ¿Y si la condición es que
Maŕıa hable inmediatamente después que Luis? ¿Y si deben alternarse
oradores de distinto sexo?
5. ¿De cuántas maneras se pueden seleccionar cuatro cartas de un mazo
de 52, de modo que haya una de cada palo?
6. De un mazo de 52 naipes se extraen diez al azar. ¿Cuál es la pro-
babilidad de no sacar ningún as? ¿Y de sacar al menos un as? ¿Y
exactamente uno?
7. ¿Cuál es la probabilidad de que al escoger un número de tres cifras al
azar las tres cifras sean diferentes?
8. Supongamos que cada automóvil se identifica mediante una sucesión
de tres letras seguidas de tres d́ıgitos, y que las placas se otorgan en
orden alfabético-numérico comenzando con la AAA000. Las letras que
se utilizan son las veintiséis siguientes:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
¿Cuántas placas diferentes son posibles con este sistema? ¿Cuántoscarros se matricularon antes que el CGU735 ?
9. ¿Cuántos pares ordenados de fichas de dominó pueden formarse de
modo tal que “liguen”, es decir, que tengan al menos un d́ıgito en
común? (Suponga que hay suficientes fichas de todos los tipos.)
10. ¿De cuántas maneras pueden colocarse en un tablero de ajedrez tres
torres blancas idénticas de modo que no se ataquen?
12 José H. Nieto
11. ¿De cuántas maneras pueden colocarse un alfil blanco y uno negro en
un tablero de ajedrez de modo que se ataquen mutuamente (es decir,
que estén en una misma diagonal)?
12. Pruebe que el número máximo de fichas que se pueden colocar en un
tablero cuadrado de n× n sin que haya dos en una misma diagonal es
2n− 2, y que el número de estas configuraciones maximales es 2n.
Caṕıtulo 2
Las configuraciones clásicas
combinar tr. Unir cosas diversas, de manera que formen un
compuesto o agregado.
Diccionario de la Lengua española 20a. edición,
Real Academia Española, 1984.
Dado un conjunto de m objetos existen ciertas formas t́ıpicas de agru-
par, distribuir o seleccionar sus elementos. En este caṕıtulo consideraremos
esas configuraciones estudiadas por la teoŕıa combinatoria clásica, indicando
también el punto de vista moderno.
2.1 Arreglos
Se llaman arreglos de m objetos tomados de n en n a las sucesiones de n
términos diferentes que pueden formarse con los m objetos. Aśı por ejemplo
los arreglos de las letras a, b, c tomadas de dos en dos son: ab, ac, ba, bc, ca, cb.
Varios términos se han usado como sinónimos de arreglos, entre ellos:
variaciones, disposiciones, coordinaciones, etc.
Observemos que si A = {a1, . . . , an} entonces los arreglos de los elemen-
tos de A tomados de n en n no son otra cosa que las funciones inyectivas de
Nn en A. For lo tanto en vista de (1.3.14) tenemos que:
Proposición 2.1.1. El número de arreglos de m elementos tomados de n
en n es [m]n = m(m− 1) · · · (m− n+ 1).
Regla de formación recursiva de los arreglos 2.1.2. Para formar los
arreglos de m elementos tomados de n en n, suponiendo que ya han sido
14 José H. Nieto
formados los de n− 1 en n− 1, se colocan a la derecha de cada uno de estos
últimos, sucesivamente, los elementos que no figuran en ellos.
Ejemplo
Sea A = {a, b, c, d}. En el cuadro siguiente se ilustra la formación de los
arreglos según la regla anterior:
de 1 en 1 de 2 en 2 de 3 en 3 de 4 en 4
a ab abc abcd
abd abdc
ac acb acbd
acd acdb
ad adb adbc
adc adcb
b ba bac bacd
bad badc
bc bca bcad
bcd bcda
bd bda bdac
bdc bdca
c ca cab cabd
cad cadb
cb cba cbad
cbd cbda
cd cda cdab
cdb cdba
d da dab dabc
dac dacb
db dba dbac
dbc dbca
dc dca dcab
dcb dcba
Es fácil probar por inducción que la regla enunciada es correcta. Si ya se
ha formado una lista con todos los arreglos de m objetos tomados de n− 1
en n − 1 entonces dado cualquier arreglo de n en n, quitándole el último
elemento queda un arreglo de n − 1 en n − 1 que debe estar en la lista.
Esto garantiza la aparición del arreglo dado al aplicar la regla. Además
no aparecen arreglos repetidos, ya que si en la lista son todos diferentes al
Teoŕıa Combinatoria 15
aplicar la regla resultarán arreglos que, si no difieren en los primeros n− 1
elementos, diferirán en el último.
De la regla de formación se deduce que el número de arreglos de m
objetos tomados de n en n, que denotaremos Amn , satisface la relación de
recurrencia siguiente:
Amn = (m− n+ 1)Amn−1
ya que de cada arreglo de n − 1 en n − 1 se obtienen m − (n − 1) arreglos
diferentes de n en n, agregando al final cada uno de los m−(n−1) elementos
que no figuran en él. Puesto que obviamente Am1 = m esta relación de
recurrencia nos da:
Am2 = (m− 2 + 1)Am1 = (m− 1)m,
Am3 = (m− 3 + 1)Am2 = (m− 2)(m− 1)m
y en general Amn = (m − n + 1) · · · (m − 1)m, en concordancia con nuestro
resultado anterior.
2.2 Arreglos con repetición
Se llaman arreglos con repetición de m elementos tomados de n en n a
las sucesiones de n términos que pueden formarse con los m elementos,
entendiendo que cada uno de ellos puede aparecer repetido. Aśı por ejemplo
los arreglos con repetición de los elementos a, b y c tomados de dos en dos
son los siguientes:
aa ab ac ba bb bc ca cb cc
Proposición 2.2.1. El número de arreglos con repetición de m elementos
tomados de n en n es mn.
Demostración. Los arreglos con repetición de m elementos a1, a2, . . . , am no
son otra cosa que las funciones de Nn en el conjunto {a1, a2, . . . , am} y por
lo tanto su número es mn como vimos en (1.3.12).
2.3 Permutaciones
Los arreglos de n objetos tomados de n en n son llamados permutaciones
de los n objetos. Se tiene obviamente que:
16 José H. Nieto
Proposición 2.3.1. El número de permutaciones de n objetos es n!
Demostración: En efecto,
[n]n = n(n− 1) · · · (n− n+ 1) = n(n− 1) · · · 2 · 1 = n!
Regla de formación de las permutaciones 2.3.2.
Puede particularizarse la regla de formación de los arreglos, o seguir este
otro procedimiento: ya formadas las permutaciones de los n − 1 elementos
a1, . . . , an agreguemos el elemento an a cada una de ellas, en todas las posi-
ciones posibles.
Ejemplo
Formación sucesiva de las permutaciones de {a}, {a, b} y {a, b, c}:
abc
ab acb
cab
a
bac
ba bca
cba
2.4 Permutaciones con repetición
Dados los elementos a1, a2, . . . , ar y números naturales k1, k2, . . . , kr consi-
deremos las sucesiones de n = k1 + k2 + · · · + kr términos que se pueden
formar con los ai de modo que a1 aparezca k1 veces, a2 aparezca k2 veces,
. . . y ar aparezca kr veces. A estas sucesiones se les llama permutaciones
con repetición de los elementos dados (con multiplicidades k1, . . . , kr ). Para
contar su número consideremos un conjunto A de n elementos, particionado
en clases disjuntas C1, C2, . . . , Cr tales que |Ci| = ki. Digamos que dos per-
mutaciones f y g de los elementos de A son equivalentes si los elementos f(i)
y g(i) pertenecen a la misma clase en A para i = 1, 2, . . . , n. Los elementos
de Ci pueden permutarse entre si de ki! maneras. Como esto ocurre para
cada i de 1 hasta r es claro que para cada permutación de los elementos
de A hay k1! k2! . . . kr! permutaciones equivalentes. El número de clases de
equivalencia será entonces el cociente entre el total de permutaciones de A
y este número k1! k2! . . . kr! . Pero es claro que estas clases de equivalen-
cia pueden ponerse en correspondencia biyectiva con las permutaciones con
repetición, por lo tanto hemos establecido que:
Teoŕıa Combinatoria 17
Proposición 2.4.1. El número de permutaciones con repetición de r ele-
mentos con multiplicidades k1, k2, . . . , kr es:
n!
k1! k2! . . . kr!
siendo n = k1 + k2 + · · ·+ kr.
Ejemplo
Determinemos cuántas palabras diferentes pueden formarse permutando
las letras de la palabra MATEMATICA. Tenemos d́ıez letras, que se reparten
en tres A, dos M, dos T , una E una I y una C . Por lo tanto la respuesta
se obtiene dividiendo 10! entre 3! 2! 2! 1! 1! 1! lo cual resulta ser 151200.
2.5 Combinaciones
Llamaremos combinaciones de m elementos a1, a2, . . . , am tomados de n en
n a los subconjuntos de n elementos del conjunto {a1, a2, . . . , am}. Denota-
remos el número de tales combinaciones mediante el śımbolo
(
m
n
)
, notación
introducida por Andreas von Ettingshausen en su obra Die Combinatorische
Analysi (Viena, 1826).
Ejemplo
Las combinaciones de los cuatro elementos a, b, c, d tomadas de dos en dos
son : {a, b}, {a, c}, {a, d}, {b, c}, {b, d} y {c, d}. Por lo tanto
(4
2
)
= 6.
Nota: Generalmente se escriben las combinaciones sin las llaves que se usan
para denotar conjuntos. Aśı en el ejemplo anterior tendŕıamos ab, ac, ad,
bc, bd, cd. Sin embargo al usar esta notación hay que tener en cuenta que
no importa el orden de los elementos dentro de cada grupo, a diferencia de
lo que sucede con 1os arreglos.
Para cada combinación de m elementos tomados de a n formemos las
n! permutaciones posibles con sus elementos. De este modo se obtendrán
arreglos de m elementostomados de a n. Es claro que todos los arreglos
formados serán distintos, pues si provienen de combinaciones distintas di-
fieren en algún elemento, y si provienen de la misma difieren en el orden
de los elementos. Además es evidente que se obtendrán todos los arreglos
de los m elementos tomados de n en n. Puesto que cada una de las
(
m
n
)
combinaciones origina n! arreglos resulta que
(
m
n
)
n! = [m]n y por lo tanto:
18 José H. Nieto
Proposición 2.5.1. El número de combinaciones de m elementos tomados
de n en n es:(
m
n
)
=
[m]n
n!
=
m(m− 1) · · · (m− n+ 1)
n(n− 1) · · · 3 · 2 · 1
=
m!
n! (m− n)!
Si ya se han escrito todas las combinaciones de m elementos tomados de
n− 1 en n− 1, escribiendo a la derecha de cada una de ellas, sucesivamente,
cada uno de los elementos que siguen a los que entran en la combinación, se
obtienen todas las combinaciones tomadas de n en n.
La comprobación de la corrección de esta regla se deja como ejercicio.
Nos limitaremos a ilustrarla con un ejemplo.
Ejemplo
Sea A = {a, b, c, d}. Las combinaciones que pueden formarse son:
de 1 en 1 de 2 en 2 de 3 en 3 de 4 en 4
a ab abc abcd
abd
ac acd
ad
b bc bcd
bd
c cd
d
Las combinaciones pueden ser estudiadas también desde otro punto de
vista. Para ello introduzcamos un orden lineal estricto en el conjunto A =
{a1, a2, . . . am} definiendo ai ≺ aj si y sólo si i < j. Entonces podemos es-
tablecer una correspondencia entre las funciones estrictamente crecientes de
Nn en A y los subconjuntos de A con n elementos. En efecto, si f : Nn → A
es estrictamente creciente (es decir que i < j implica f(i) ≺ f(j)) hagámosle
corresponder su imagen Im(f) = {f(1), f(2), . . . , f(n)}. Esta corresponden-
cia es sobreyectiva, ya que dado un subconjunto B de A con n elementos,
ordenémoslos y sean estos b1 ≺ b2 ≺ · · · ≺ bn. La función f : Nn → A
definida como f(i) = bi es estrictamente creciente y se tiene obviamente
Im(f) = B. La correspondencia es también inyectiva pues si f y g son dos
funciones distintas de Nn en A, ambas estrictamente crecientes, sea j el me-
nor número natural (entre 1 y n) tal que f(j) 6= g(j). Supongamos para
Teoŕıa Combinatoria 19
fijar ideas que g(j) ≺ f(j). Entonces si 1 ≤ i < j se tiene f(i) = g(i) ≺ g(j),
mientras que si j < i ≤ n entonces g(j) ≺ f(j) ≺ f(i) . En todo caso g(j)
no pertenece a Im(f) y por lo tanto Im(f) 6= Im(g).
La correspondencia biyectiva que se acaba de establecer nos permite
afirmar que hay tantas funciones estrictamente crecientes de Nn en A como
combinaciones de los elementos de A tomados de n en n. Más en general
podemos substituir Nn por otro conjunto linealmente ordenado cualquie-
ra. Además los razonamientos hechos son válidos también para funciones
estrictamente decrecientes. Por lo tanto podemos afirmar que:
Proposición 2.5.2. El número de funciones estrictamente crecientes o es-
trictamente decrecientes de un conjunto linealmente ordenado B de n ele-
mentos en otro A de m elementos es
(
m
n
)
.
2.6 Combinaciones con repetición
Las combinaciones con repetición de m elementos tomados de n en n son
los grupos de n elementos que pueden formarse con los m dados, sin tomar
en cuenta el orden y admitiendo elementos repetidos. Aśı por ejemplo las
combinaciones con repetición de los elementos a, b y c tomados de dos en
dos son las siguientes:
aa, ab, ac, bb, bc, cc
Una forma interesante de representar las combinaciones con repetición
de m elementos a1, a2, . . . , am es en forma de monomio ai11 a
i2
2 . . . a
im
m donde el
exponente de cada elemento aj indica el número de veces que dicho elemento
aparece en la combinación. Es claro que de este modo se establece una co-
rrespondencia biyectiva entre combinaciones con repetición de m elementos
tomados de n en n y monomios de grado n en m variables, con coeficiente
unidad. Para contar el número de tales monomios hagamos corresponder
a cada uno de ellos una sucesión de ceros y unos, escribiendo para cada
variable una hilera de tantos unos como indique el exponente (ninguno si el
exponente es cero) y usando ceros como elementos de separación entre las
hileras de unos correspondientes a variables distintas. El resultado tendrá el
siguiente aspecto:
1 · · · 1︸ ︷︷ ︸
i1
0 1 · · · 1︸ ︷︷ ︸
i2
0 · · · · · · 0 1 · · · 1︸ ︷︷ ︸
im
20 José H. Nieto
Si algún exponente es nulo la hilera correspondiente de unos será vaćıa,
apareciendo por consiguiente dos o más ceros consecutivos. En cualquier
caso habrá m− 1 ceros y la longitud de la sucesión será i1 + i2 + · · ·+ im +
m− 1 = n+m− 1.
Veamos como ejemplo algunos monomios de sexto grado en cuatro va-
riables a, b, c, d y las sucesiones de ceros y unos asociadas:
a2bc2d 1 1 0 1 0 1 1 0 1
b4d2 0 1 1 1 1 0 0 1 1
d6 0 0 0 1 1 1 1 1 1
a6 1 1 1 1 1 1 0 0 0
Es claro que la correspondencia establecida es biyectiva, y por lo tanto
hay tantos monomios de grado n en m variables con coeficiente unidad como
sucesiones de n+m−1 términos, de los cuales n son unos y m−1 son ceros.
El número de tales sucesiones es obviamente
(
n+m−1
n
)
pues una vez elegidas
las n posiciones donde se van a poner los unos los m − 1 puestos restantes
deben llenarse con ceros. Quedan probadas entonces las dos proposiciones
siguientes:
Proposición 2.6.1. El número de las combinaciones con repetición de m
elementos tomados de n en n es
(
n+m−1
n
)
.
Proposición 2.6.2. El número de monomios de grado n en m variables
con coeficiente unidad es
(
n+m−1
n
)
.
Una forma más moderna de tratar las combinaciones con repetición con-
siste en ordenar el conjunto A = {a1, . . . , am} como lo hicimos antes y
considerar las funciones crecientes (en sentido amplio) de Nn en A. Con
razonamientos análogos a los hechos para las combinaciones simples y las
funciones estrictamente crecientes puede verse que existe una corresponden-
cIa biyectiva natural entre combinaciones con repetición de m elementos
tomados de de n en n y funciones crecientes (en sentido amplio) de un con-
junto linealmente ordenado de n elementos en otro de m elementos. Estos
hechos se resumen en el siguiente enunciado:
Proposición 2.6.3. El número de funciones crecientes (o decrecientes) en
sentido amplio de un conjunto linealmente ordenado de n elementos en otro
de m elementos es
(
n+m−1
n
)
.
Teoŕıa Combinatoria 21
2.7 Algoritmos combinatorios
El problema de generar permutaciones, combinaciones y otros objetos com-
binatorios con el computador ha dado origen a una serie de interesantes
algoritmos. Como ejemplo inclúımos a continuación uno que genera las per-
mutaciones de los números del 1 al n en orden lexicográfico, comenzando
por 1, 2, . . . , n y finalizando con n, n − 1, . . . , 2, 1 . Cada permutación se
representa mediante un arreglo a[1], a[2], . . . , a[n]. Usamos la flecha hacia la
izquierda para denotar la asignación de un valor a una variable.
Algoritmo generador de permutaciones 2.7.1.
Paso 1 (inicializar) Para i = 1 hasta n hacer a[i]← i
Paso 2 Imprimir a[1], a[2], . . . , a[n]
Paso 3 Hallar el mayor i tal que a[i] < a[i+ 1]. Si no se encuentra tal i el
algoritmo finaliza (esto ocurrirá necesariamente luego de imprimir la
permutación n, n− 1, . . . , 3, 2, 1)
Paso 4 Hallar el menor a[j] con j > i y tal que a[j] > a[i]
Paso 5 Intercambiar los valores de a[i] y a[j]
Paso 6 Invertir la sucesión a[i+ 1], . . . , a[n]
Paso 7 Volver al Paso 2.
Para más detalles sobre éste y otros algoritmos combinatorios vea [K1],
[N3] y [R2].
2.8 Ejercicios
1. ¿Cuántas banderas con tres franjas horizontales del mismo ancho y
distintos colores pueden formarse, si se dispone de tela amarilla, azul,
verde, blanca y roja?
2. En el alfabeto Morse, usado en telegraf́ıa, se emplean solamente dos
signos: el punto y la raya. ¿Cuántas palabras distintas pueden formar-
se compuestas de uno, dos, tres, cuatro o cinco signos? Generalice.
3. ¿De cuántas maneras puede formarse una ronda con diez niños?
22 José H. Nieto
4. Con diez cuentas de vidrio de distintoscolores, ¿cuántos collares dife-
rentes se pueden formar?
5. ¿Cuántos números mayores que 3000 y menores que 4000 pueden for-
marse con los d́ıgitos 2, 3, 5 y 7
a) si cada cifra puede usarse sólo una vez?
b) si cada cifra puede emplearse las veces que se desee?
6. ¿Cuántas palabras diferentes pueden formarse con las letras de la pa-
labra POLINOMIO?
7. Si se forman todos los números que resultan de permutar las cifras de
123579 y se ordenan en forma creciente, ¿qué lugar ocupará el número
537192?
8. De un grupo de seis hombres y cuatro mujeres,
a)¿Cuántas comisiones de tres personas se pueden formar?
b)¿Cuántas en las que haya exactamente un hombre?
c)¿Cuántas en las que haya al menos un hombre?
9. ¿Cuántos triángulos se pueden formar que tengan como vértices los
vértices de un decágono regular?
10. Si n puntos distintos situados en una circunferencia se unen de todas
las maneras posibles, ¿cuántos puntos de intersección resultan, como
máximo?
11. En un plano hay n puntos, k de los cuales están alineados. A excepción
de ellos no hay tres en ĺınea recta. ¿Cuántas ĺıneas rectas diferentes
resultan si se unen los n puntos dos a dos?
12. ¿En cuántos puntos se cortan n rectas, k de las cuales son paralelas
entre śı?
13. ¿Cuántas naranjas se necesitan para formar una pirámide de base
triangular con n naranjas en cada lado de la base?
14. ¿De cuántas maneras se pueden comprar diez frutas, si el frutero sólo
dispone de naranjas, mangos y ńısperos?
Teoŕıa Combinatoria 23
15. ¿De cuántas maneras se pueden colocar las figuras blancas (un rey,
una dama, dos alfiles, dos torres y dos caballos) en la primera fila del
tablero de ajedrez?
16. De un total de N art́ıculos de los cuales B son buenos y los restantes,
D = N −B son defectuosos se escoge al azar una muestra de n art́ıcu-
los. ¿Cuál es la probabilidad de que en la muestra haya x art́ıculos
buenos (y n− x defectuosos)?
17. ¿Qué dimensión tiene el espacio vectorial de los polinomios de grado
menor o igual a n en k variables?
18. Para escribir todos los números naturales desde 1 hasta 1000000, ¿cuán-
tos ceros se necesitan?
19. En un acto deben hablar n mujeres y k hombres. ¿De cuántas maneras
se puede ordenar la lista de oradores con la condición de que no hablen
dos hombres consecutivamente?
20. (Kaplansky) Pruebe que el número de subconjuntos de Nn con k ele-
mentos y sin enteros consecutivos es
(
n−k+1
k
)
.
21. (Kaplansky) Pruebe que el número de subconjuntos de Nn con k ele-
mentos y que no contienen enteros consecutivos ni a 1 y n simultánea-
mente es:
n
n− k
(
n− k
k
)
24 José H. Nieto
Caṕıtulo 3
Coeficientes binomiales y
multinomiales
“La cantidad
(
n
k
)
se denomina coeficiente binomial ; estos
números tienen una cantidad extraordinaria de aplicaciones.
Son quizá las cantidades más importantes que aparecen en el
análisis de algoritmos y, por tanto, se recomienda al lector que
se familiarice con ellos.”
D.E. Knuth [K1] vol.1
“The binomial coefficients are virtually ubiquitous in Com-
binatorial Theory and it would be folly to attempt to count
anything without their aid.”
D.I.A. Cohen [C1]
3.1 Los coeficientes binomiales
En el caṕıtulo anterior definimos
(
m
n
)
como el número de subconjuntos de
cardinal n de un conjunto de m elementos. A continuación veremos que
estos números admiten también interpretaciones algebraicas y geométricas
y estableceremos unas cuantas de sus propiedades.
Teorema del binomio 3.1.1.
(x+ y)m =
m∑
n=0
(
m
n
)
xn · ym−n
26 José H. Nieto
Demostración: (x+y)m es el producto dem factores (x+y). Al desarrollar
el producto se obtiene una suma de monomios de gradom en las dos variables
x, y. El monomio xn · ym−n aparece tantas veces como formas haya de
escoger n de los m paréntesis para seleccionar la x en ellos. Este número es
justamente
(
m
n
)
.
Nota: A ráız de este teorema los números
(
m
n
)
se denominan “coeficientes
binomiales”, nombre que se remonta a M. Stifel (1486–1567). Es corriente
demostrar el teorema del binomio por inducción, utilizando la fórmula de
Stifel (3.1.4) para justificar el salto inductivo. Sin embargo creemos que
debe preferirse esta sencilla demostración combinatoria pues además de su
brevedad permite deducir la fórmula para el desarrollo del binomio, mientras
que la demostración por inducción requiere conocer la fórmula de antemano.
Una interpretación geométrica de los coeficientes binomiales
Consideremos las poligonales P0P1 . . . Pm en el plano cartesiano cuyos
vértices cumplen la condición siguiente: “Si Pi tiene coordenadas (x, y) en-
tonces Pi+1 tiene coordenadas (x+ 1, y) o (x, y+ 1)”. En otras palabras, se
trata de poligonales cada uno de cuyos segmentos PiPi+1 es paralelo a uno de
los ejes coordenados, tiene longitud unidad y está orientado igual que el eje
al cual es paralelo. Llamaremos a estas poligonales “caminos ascendentes”
o simplemente caminos.
Proposición 3.1.2. El número de caminos ascendentes de longitud m que
parten del origen es 2m. El número de caminos que parten del origen y
finalizan en el punto de coordenadas (n, k) es
(
n+k
n
)
.
Demostración. Para construir un camino de longitud m partiendo del ori-
gen debemos elegir primeramente P1, que solamente puede ser (0, 1) o (1, 0).
Tenemos pues dos posibilidades. Una vez elegido P1 hay dos posibilidades
para escoger P2, y aśı sucesivamente. Por el principio del producto resulta
entonces que pueden constrúırse 2m caminos de longitud m. Para contar los
caminos P0P1 . . . Pm con P0 = (0, 0) y Pm = (n, k) observemos en primer
lugar que debe ser m = n+ k, pues cada vértice Pi (1 ≤ i ≤ m) tiene o bien
su abscisa o bien su ordenada una unidad mayor que la del vértice anterior
Pi−1. Por lo tanto, para ir desde (0, 0) hasta (n, k) un camino debe tener n
segmentos paralelos al eje Ox y k segmentos paralelos al eje Oy, siendo su
longitud m = n+k. Ahora bien, el camino queda determinado si conocemos
Teoŕıa Combinatoria 27
cuáles de sus n + k segmentos son paralelos a Ox, pues los restantes serán
necesariamente paralelos a Oy. El problema se reduce entonces a escoger n
elementos de un total de n+k, lo cual puede hacerse de
(
n+k
n
)
maneras.
A continuación estudiaremos una serie de proposiciones relativas a los
coeficientes binomiales. Para cada una de ellas se pueden seguir al menos
cuatro estrategias de demostración :
1. Estrategia combinatoria pura: consiste en interpretar
(
m
n
)
como el
número de subconjuntos de n elementos de un conjunto de m ele-
mentos, y usar técnicas de conteo.
2. Estrategia aritmética: consiste en calcular aritméticamente a partir de
la fórmula
(
m
n
)
= m!n! (m−n)!
3. Estrategia algebraica: consiste en interpretar
(
m
n
)
como el coeficiente
de xnym−n en el desarrollo de (x+y)m y realizar cálculos y operaciones
algebraicas con polinomios.
4. Estrategia geométrica: consiste en interpretar
(
m
n
)
como el número
de caminos ascendentes desde (0, 0) hasta (m− n, n) y efectuar luego
razonamientos “geométrico-combinatorios”.
Para algunas de las proposiciones siguientes daremos cuatro demostracio-
nes, correspondientes a las cuatro estrategias mencionadas. En otros casos
proporcionaremos sólo una demostración (generalmente la que considera-
mos más elegante) pero sugerimos al lector que construya demostraciones
alternativas siguiendo las estrategias restantes.
Simetŕıa de los coeficientes binomiales 3.1.3.(
m
n
)
=
(
m
m− n
)
Demostración combinatoria: Sea A un conjunto de m elementos. Lla-
memos Fk a la familia de todos los subconjuntos de A con k elementos y
definamos f : Fn → Fm−n haciendo corresponder a cada miembro X de Fn
su complemento en A, que tendrá m− n elementos y estará por lo tanto en
Fm−n. En śımbolos, f(X) = A\X. Es inmediato verificar que f es biyec-
tiva: f(X) = f(Y ) ⇒ A\X = A\Y ⇒ X = Y , y si Y ∈ Fm−n entonces
X = A\Y ∈ Fn y f(X) = A\X = A\(A\Y ) = Y . Entonces por el principio
de correspondencia tenemos que|Fn| = |Fm−n|, es decir:
(
m
n
)
=
(
m
m−n
)
28 José H. Nieto
Demostración aritmética:(
m
m− n
)
=
m!
(m− n)! (m− (m− n))!
=
m!
(m− n)!n!
=
(
m
n
)
Demostración algebraica: Basta comparar el coeficiente de xnym−n en
el desarrollo de (x + y)m con el de ym−nxn en el desarrollo de (y + x)m.
Puesto que (x+ y)m = (y+x)m, estos coeficientes deben ser iguales, lo cual
demuestra la proposición.
Demostración geométrica: La simetŕıa respecto a la bisectriz del primer
cuadrante (es decir la recta y = x) establece una correspondencia biyectiva
entre los caminos ascendentes que parten del origen y llegan a (m− n, n) y
aquellos otros que partiendo del origen alcanzan el punto simétrico (n,m−n).
Pero el número de estos últimos es según (3.1.2):(
n+ (m− n)
m− n
)
=
(
m
m− n
)
Fórmula de Stifel 3.1.4.(
m
n
)
=
(
m− 1
n
)
+
(
m− 1
n− 1
)
Demostración combinatoria: Sea A = {a1, a2, . . . , am}. Los subconjun-
tos de n elementos de A pueden dividirse en dos clases: la de aquellos que
no contienen al elemento am y la de los que śı lo contienen. La primera
clase está constitúıda simplemente por los subconjuntos de n elementos de
{a1, a2, . . . , am−1} y su número es
(
m−1
n
)
. En cuanto a los subconjuntos
que contienen al am observemos que quitándoles este elemento resulta un
subconjunto de n− 1 elementos de {a1, . . . , am−1}. Por lo tanto su número
es
(
m−1
n−1
)
. Aplicando el principio de la suma queda entonces demostrada la
proposición.
Teoŕıa Combinatoria 29
Demostración aritmética:(
m− 1
n
)
+
(
m− 1
n− 1
)
=
(m− 1)!
n! (m− 1− n)!
+
(m− 1)!
(n− 1)![(m− 1)− (n− 1)]!
=
(m− 1)! (m− n) + (m− 1)!n
n! (m− n)!
=
(m− 1)!(m− n+ n)!
n! (m− n)!
=
(
m
n
)
Demostración algebraica:
(x+ y)m = (x+ y)m−1 · (x+ y) =
(
m−1∑
n=0
(
m− 1
n
)
xnym−n−1
)
(x+ y)
Calculando ahora el coeficiente de xnym−n en esta última expresión resulta
ser justamente
(
m−1
n−1
)
+
(
m−1
n
)
Demostración geométrica:
(
m
n
)
es el número de caminos ascendentes
que partiendo del origen alcanzan el punto de coordenadas (m − n, n).
El penúltimo vértice de cualquiera de estos caminos debe ser necesaria-
mente (m − n − 1, n) o (m − n, n − 1). Esto nos permite clasificar los
caminos en cuestión en dos clases disjuntas. Los caminos con penúlti-
mo vértice en (m − n − 1, n) son
((m−n−1)+n
n
)
=
(
m−1
n
)
, mientras que los
que tienen el penúltimo vértice en el punto (m − n, n − 1) son a su vez:((m−n)+(n−1)
n−1
)
=
(
m−1
n−1
)
El triángulo aritmético
La fórmula (3.1.4) permite calcular los coeficientes binomiales recursivamen-
te: conocidos los coeficientes con ı́ndice superior m − 1 se pueden calcular
los de ı́ndice superior m mediante simples sumas. Si disponemos los coefi-
cientes binomiales en una tabla triangular, como se indica a continuación,
entonces cada uno de ellos es igual a la suma de los dos que están en la fila
inmediata superior, a su izquierda y a su derecha. Esta tabla se conoce con
el nombre de “triángulo aritmético” o “triángulo de Pascal” y posee muchas
propiedades interesantes. Una monograf́ıa de carácter elemental sobre este
triángulo es la de Uspensky [U1].
Obsérvese que los lados del triángulo sólo contienen unos, puesto que(
m
0
)
=
(
m
m
)
= 1, para todo m ≥ 0.
30 José H. Nieto
(0
0
)
(1
0
) (1
1
)
(2
0
) (2
1
) (2
2
)
(3
0
) (3
1
) (3
2
) (3
3
)
(4
0
) (4
1
) (4
2
) (4
3
) (4
4
)
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
En el siguiente triángulo hemos calculado efectivamente todos los coefi-
cientes binomiales con ı́ndice superior menor o igual a diez.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
Proposición 3.1.5. (
n
0
)
+
(
n
1
)
+ · · ·+
(
n
n
)
= 2n
Demostración aritmética: Por el teorema del binomio (3.1.1) el miembro
izquierdo de (3.1.5) es igual a (1 + 1)n = 2n.
Demostración combinatoria: Sea A un conjunto de n elementos. Puesto
que
(
n
k
)
es el número de subconjuntos de A con k elementos, es claro que el
miembro izquierdo de la igualdad a demostrar representa la cantidad total
de subconjuntos de A, que ya sabemos que es 2n por (1.3.4).
Teoŕıa Combinatoria 31
Demostración geométrica: El número de caminos ascendentes de longi-
tud n que parten del origen es 2n (3.1.2). Estos caminos se pueden cla-
sificar según el punto de llegada, que debe ser de la forma (h, k) con h, k
enteros no negativos y h + k = n. Estos puntos están alineados, y son
(0, n), (1, n − 1), (2, n − 2), . . . , (n, 0). Según (3.1.2) el número de caminos
que llegan a (h, n−h) es
(
n
h
)
, por lo tanto una aplicación del principio de la
suma completa la demostración.
Proposición 3.1.6. Para todo n > 0 se tiene:(
n
0
)
−
(
n
1
)
+
(
n
2
)
− · · ·+ (−1)n ·
(
n
n
)
= 0
Demostración aritmética: El miembro izquierdo es el desarrollo de
(1− 1)n y por lo tanto debe ser 0.
Demostración combinatoria: Escribiendo (3.1.6) en la forma siguiente:(
n
0
)
+
(
n
2
)
+
(
n
4
)
+ · · · =
(
n
1
)
+
(
n
3
)
+ . . .
vemos que podemos darle la siguiente interpretación combinatoria: para
todo conjunto finito no vaćıo, el número de sus subconjuntos con cardinal
par es igual al número de sus subconjuntos con cardinal impar. Para probar
esto sea A = {a1, a2, . . . , an} y consideremos la función f : 2A → 2A definida
aśı: si X ⊂ A entonces f(X) = X4{a1}. En otras palabras, a X le hacemos
corresponder el subconjunto de A que resulta de agregarle a1, si no lo teńıa,
o de quitárselo, si lo teńıa. Esta función es biyectiva, ya que obviamente es
su propia inversa, y transforma conjuntos de cardinal par en conjuntos de
cardinal impar y viceversa. Por lo tanto hay tantos de una clase como de la
otra.
Proposición 3.1.7.(
n+ 1
k + 1
)
=
(
n
k
)
+
(
n− 1
k
)
+ · · ·+
(
k
k
)
32 José H. Nieto
Demostración: Sea A = {a1, a2, . . . , an+1} un conjunto de cardinal n+ 1
y sea Ci la clase formada por los subconjuntos de k+ 1 elementos de A cuyo
elemento con mayor sub́ındice sea el ai. Tendremos aśı clases Ck+1, . . . , Cn.
Es fácil ver que |Ci| =
(
i−1
k
)
y entonces (3.1.7) se sigue del principio de la
suma.
(Otra demostración de 3.1.7 puede obtenerse aplicando la fórmula de Stifel
(3.1.4) en forma sucesiva.)
Identidad de Vandermonde 3.1.8.(
n+m
r
)
=
(
n
0
)(
m
r
)
+
(
n
1
)(
m
r − 1
)
+
(
n
2
)(
m
r − 2
)
+ · · ·+
(
n
r
)(
m
0
)
Demostración algebraica:
(
n+m
r
)
es el coeficiente de xr en el desarrollo
de (x+ y)n+m. Pero como (x+ y)n+m = (x+ y)n(x+ y)m, si desarrollamos
por separado (x+ y)n y (x+ y)m y luego hacemos el producto, el coeficiente
de xr resulta ser justamente el miembro derecho de (3.1.8).
Demostración combinatoria: Sean A = {a1, . . . , an} y B = {b1, . . . , bm}
dos conjuntos de cardinales n y m respectivamente. Entonces podemos
interpretar el miembro izquierdo de (3.1.8) como la cantidad de subconjuntos
de r elementos de la unión A ∪ B. Pero cada uno de esos subconjuntos
estará formado por un cierto número j de elementos de A y r− j elementos
de B. Por el principio del producto el número de conjuntos que pueden
formarse con j elementos de A y r−j elementos de B es
(
n
j
)(
m
r−j
)
y sumando
estas cantidades para j entre 0 y r resulta (3.1.8).
3.2 Coeficientes multinomiales
Dados un número natural m y enteros n1, n2, . . . , nk (k ≥ 2) sean X =
{x1, x2, . . . , xm} e Y = {y1, y2, . . . , yk} dos conjuntos de m y k elementos
respectivamente. Denotaremos mediante el śımbolo(
m
n1 n2 . . . nk
)
Teoŕıa Combinatoria 33
al número de funciones f : X → Y tales que |f−1(yi)| = ni para i =
1, 2, . . . , k. Llamaremos a estos números “coeficientes multinomiales”. Usan-
do un lenguaje más informal podŕıamos definir estos números como la canti-
dad de maneras de distribuirm objetos en k cajas rotuladas y1, . . . , yk de ma-
nera tal que la caja yi contenga exactamenteni objetos, para i = 1, 2, . . . , k.
Observemos que según nuestra definición si no se cumplen las condiciones
ni ≥ 0 para i = 1, 2, . . . , k y m = n1 + n2 + · · ·+ nk entonces(
m
n1 n2 . . . nk
)
= 0
Proposición 3.2.1. Si ni ≥ 0 para i = 1, 2, . . . , k y n1 +n2 + · · ·+nk = m
entonces (
m
n1 n2 . . . nk
)
=
m!
n1!n2! . . . nk!
Demostración: Sean X = {x1, x2, . . . , xm} , Y = {y1, y2, . . . , yk}. Para
definir una función f : X → Y tal que |f−1(yi)| = ni para i = 1, 2, . . . , k
seleccionemos primero los n1 elementos cuya imagen será y1. Esta selección
podemos realizarla de
(
m
n1
)
maneras. Luego escojamos entre los m − n1
elementos restantes de X aquellos cuya imagen será y2. El número de formas
de hacer esta segunda selección es
(
m−n1
n2
)
y prosiguiendo de esta manera y
aplicando el principio del producto llegamos entonces a que:(
m
n1 . . . nk
)
=
(
m
n1
)(
m− n1
n2
)(
m− n1 − n2
n3
)
. . .
(
m− n1 − · · · − nk−1
nk
)
=
m!
n1! (m− n1)!
(m− n1)!
n2! (m− n1 − n2)!
· · · (m− n1 − · · · − nk−1)!
nk! (m− n1 − · · · − nk)!
=
m!
n1!n2! . . . nk!
Es posible dar una interpretación algebraica a estos números mediante
la siguiente generalización del Teorema binomial (3.1.1):
Teorema multinomial 3.2.2.
(x1 + x2 + · · ·+ xk)m =
∑
n1+n2+···+nk=m
(
m
n1 . . . nk
)
xn11 x
n2
2 . . . x
nk
k
34 José H. Nieto
(la sumatoria se extiende a todos los conjuntos ordenados de k números
enteros no negativos tales que su suma sea m)
Demostración: Al desarrollar (x1 + · · ·+ xk)m se obtienen km monomios
de grado m en k variables x1, . . . , xk. El número de veces que aparece uno
de estos monomios, digamos xn11 x
n2
2 . . . x
nk
k es igual al número de maneras
de escoger n1 factores (x1 + · · · + xk) para seleccionar x1, n2 factores para
seleccionar x2, . . . , nk factores para seleccionar xk. Pero esto puede hacerse
justamente de (
m
n1 . . . nk
)
maneras, por la forma en que hemos definido estos números.
Nota: El teorema que acabamos de demostrar justifica el nombre de “coe-
ficientes multinomiales” que hemos dado a los números que estamos estu-
diando.
Proposición 3.2.3.
∑
n1+···+nk=m
(
m
n1 . . . nk
)
= km
Demostración: Es una consecuencia inmediata del teorema multinomial
si ponemos x1 = · · · = xk = 1.
La proposición anterior puede probarse también aśı: sean
X = {x1, . . . , xm} e Y = {y1, . . . , yk} conjuntos de m y k elementos respec-
tivamente.
(
m
n1 n2 ... nk
)
es por definición el número de funciones f : X → Y
tales que yi tiene exactamente ni preimágenes, para i = 1, 2, . . . , k. Por
lo tanto, si sumamos estos coeficientes para todos los conjuntos ordenados
posibles de números no negativos n1, . . . , nk que sumen m, tendremos el
número total de funciones de X en Y . El resultado, km, coincide con el que
ya hab́ıamos obtenido en (1.3.12). Ahora bien, si restringimos la sumatoria
imponiendo la condición de que todos los ni sean estrictamente positivos, es
claro que estaremos contando solamente aquellas funciones f : X → Y tales
que cada yi tiene al menos una preimagen, es decir, las funciones sobreyec-
tivas. Queda aśı demostrada la siguiente proposición.
Teoŕıa Combinatoria 35
Proposición 3.2.4. El número de funciones sobreyectivas de un conjunto
de m elementos en otro de k elementos es:∑
n1+···+nk=m
ni>0
(
m
n1 . . . nk
)
Interpretación geométrica de los coeficientes multinomiales
La interpretación geométrica que dimos a los coeficientes binomiales pue-
de generalizarse a los multinomiales. Para ello consideremos las poligonales
en Rk con vértices de coordenadas enteras P0P1 . . . Pr tales que cada vec-
tor −−−−→PiPi+1 coincida con alguno de los versores de la base canónica de Rk
(en otras palabras, las coordenadas de Pi+1 son iguales a las de Pi excepto
una de ellas, que es una unidad superior). Llamemos a estas poligonales
“caminos ascendentes” en Rk. Entonces el coeficiente
(
m
n1 n2 ... nk
)
cuenta el
número de caminos ascendentes que partiendo del origen llegan hasta el
punto (n1, n2, . . . , nk).
Utilizaremos esta interpretación geométrica para demostrar la siguiente
generalización de la fórmula de Stifel:
Proposición 3.2.5.(
m
n1 n2 . . . nk
)
=
(
m− 1
n1 − 1 n2 . . . nk
)
+
(
m− 1
n1 n2 − 1 . . . nk
)
+ · · ·
· · ·+
(
m
n1 n2 . . . nk − 1
)
Demostración: Los caminos ascendentes de longitud m que parten del
origen y llegan al punto (n1, n2, . . . , nk) deben tener como penúltimo vérti-
ce uno de los k puntos: (n1 − 1, n2, . . . , nk), (n1, n2 − 1, n3, . . . , nk), . . . ,
(n1, n2, . . . , nk − 1), y es claro que quedan determinados al conocer sus pri-
meros m− 1 segmentos. El segundo miembro de la igualdad que queremos
probar no es más que la suma de la cantidad de caminos ascendentes de lon-
gitud m− 1 que parten del origen y llegan a cada uno de dichos puntos, por
lo cual una aplicación del principio de la suma concluye la demostración.
3.3 Ejercicios
1. Pruebe las identidades siguientes:
36 José H. Nieto
(a) k
(
n
k
)
= n
(
n−1
k−1
)
(b) (n− k)
(
n
k
)
= n
(
n−1
k
)
(c)
(
m−1
n−1
)
+ 2
(
m
n
)
+
(
m
n+1
)
=
(
m+2
n+1
)
(d)
(
n
1
)
+ 2
(
n
2
)
+ 3
(
n
3
)
+ · · ·+ n
(
n
n
)
= n2n−1
2. Calcule las sumas siguientes :
(a)
(
n
0
)
+
(
n
2
)
+
(
n
4
)
+ · · ·
(b)
(
n
1
)
+
(
n
3
)
+
(
n
5
)
+ · · ·
(c)
(
n
0
)
−
(
n
2
)
+
(
n
4
)
− · · ·
(d)
(
n
1
)
−
(
n
3
)
+
(
n
5
)
− · · ·
(e) 1 · 2 · 3 · 4 · 5 + 2 · 3 · 4 · 5 · 6 + · · ·+ n(n+ 1)(n+ 2)(n+ 3)(n+ 4)
(f)
(
n
1
)
− 2
(
n
2
)
+ 3
(
n
3
)
− · · ·
(g)
∑n
k=1(−1)kk2
(
n
k
)
(h)
∑n
k=1
1
k+1
(
n
k
)
3. ¿Para un valor dado de m, cual es el valor de n que hace máximo el
coeficiente binomial
(
m
n
)
?
4. Demuestre el teorema del binomio por inducción matemática, usando
la fórmula de Stifel.
5. ¿Cuántos caminos ascendentes van desde el punto de coordenadas en-
teras (a, b) hasta el (c, d), en el plano? Generalice el resultado a Rn.
6. (Principio de reflexión) Pruebe que si (a, b) y (c, d) son dos puntos del
plano cartesiano con coordenadas enteras situados a un mismo lado de
la diagonal y = x entonces el número de caminos ascendentes que van
desde (a, b) hasta (c, d) tocando la diagonal y = x es igual al número
total de caminos ascendentes que van desde (b, a) hasta (c, d).
7. (Teorema de la votación) Pruebe que si en una elección entre dos
candidatos el ganador obtiene p votos y el perdedor q entonces la
probabilidad de que al hacer el escrutinio el ganador vaya siempre
adelante de su oponente es p−qp+q . Sugerencia: represente cada escrutinio
posible mediante un camino ascendente que parte del origen y llega
hasta (p, q) y aplique luego el principio de reflexión (Problema 6).
Teoŕıa Combinatoria 37
8. La entrada al teatro cuesta 50 Bs. Al abrir la taquilla la caja está vaćıa.
En una cola esperan turno para comprar su entrada n personas con
un billete de 100 Bs cada una, y k personas con un billete de 50 Bs
cada una. ¿Cuál es la probabilidad de que la cola avance flúıdamente,
sin que la cajera tenga problemas para darle su vuelto a nadie?
9. Sea X = {0, 1}n. La distancia de Hamming entre dos puntos de X,
a = {a1, . . . , an} y b = {b1, . . . , bn}, se define como:
d(a, b) =
n∑
i=1
|ai − bi|
Es claro que d(a, b) es igual al número de coordenadas en las cuales a
y b difieren, o bien (si a y b son interpretados como números binarios
de n d́ıgitos) el número de d́ıgitos binarios (“bits”) que a y b tienen
diferentes. Un subconjunto W de X tal que la distancia de Hamming
entre dos cualesquiera de sus puntos es mayor que 2r (para cierto natu-
ral r) se dice que es un código corrector de orden r. Un tal subconjunto
W tiene la propiedad de que ningún elemento de X \W puede estar
a distancia menor o igual que r de dos elementos diferentes de W . La
utilidad de un código tal consiste en que si una sucesión w ∈ W de
n d́ıgitos binarios es transmitida por un canal con “ruido” y se recibe
una sucesión z ∈ W con r o menos errores, entonceses posible cono-
cer cual fue el código transmitido, a saber el único elemento w ∈ W
tal que d(z, w) ≤ r. Sea M(n, r) el máximo número de palabras que
puede tener un código corrector W ⊂ X de orden r. Pruebe que se
cumple la desigualdad siguiente:
M(n, r) ≤ 2
n(
n
0
)
+
(
n
1
)
+ · · ·+
(
n
r
)
(El miembro derecho es conocido como “cota de Hamming”)
10. ¿De cuántas maneras pueden distribuirse 3n objetos en 3 cajas distin-
tas, de modo que cada caja reciba n objetos?
11. ¿Cuál es el coeficiente de x4yw6 en el desarrollo de (x+ y+ z+w)11 ?
12. (a) ¿Cuántas palabras distintas pueden formarse con las letras de la
palabra MISSISSIPPI ?
38 José H. Nieto
(b) ¿Y con la condición adicional de que no haya dos letras I conse-
cutivas?
13. Pruebe que (n!)n divide a (n2)!
Caṕıtulo 4
Principio de Inclusiones y
Exclusiones y aplicaciones
4.1 El Principio de Inclusiones y Exclusiones
Si A y B son dos conjuntos disjuntos entonces el principio de la suma nos
dice que |A ∪ B| = |A| + |B|. Sin embargo, si A y B no son disjuntos la
fórmula anterior deja de ser válida porque los elementos de la intersección
A ∩ B aparecen “contados dos veces” en la suma |A| + |B|. Esta situación
se corrige fácilmente restando |A∩B|, y se obtiene aśı la fórmula siguiente,
válida en todos los casos: |A∪B| = |A|+ |B|−|A∩B| . Una fórmula similar
puede obtenerse para tres conjuntos , a saber :
|A ∪B ∪ C| = |A|+ |B|+ |C| − |A ∩B| − |A ∩ C| − |B ∩ C|+ |A ∩B ∩ C|
En efecto, en la suma |A|+ |B|+ |C| los elementos de la unión A ∪B ∪ C
que pertenecen a exactamente dos de los tres conjuntos están contados dos
veces. Esto se corrige restando |A ∩ B|, |A ∩ C| y |B ∩ C|. Sin embargo
esto deja fuera de la cuenta a los elementos que están en los tres conjuntos,
puesto que aparecen contados tres veces y luego restados otras tres veces.
Por eso se suma el término |A ∩ B ∩ C| equilibrando la fórmula. Resulta
bastante claro que estos razonamientos pueden generalizarse a uniones de n
conjuntos. Dicha generalización constituye el llamado “principio de inclu-
siones y exclusiones”. Pero antes de enunciarlo y demostrarlo rigurosamente
necesitamos una notación adecuada: dados n conjuntos A1, A2, . . . , An y un
conjunto de ı́ndices F ⊂ Nn no vaćıo denotaremos mediante AF a la inter-
sección de los Ai tales que i ∈ F , en śımbolos:AF =
⋂
i∈F Ai. En particular
A{i} = Ai y A{i,j} = Ai ∩Aj . Si los conjuntos Ai están todos contenidos en
40 José H. Nieto
un “conjunto universal” X y F = ∅ entonces siguiendo la convención usual
A∅ = X.
Lema 4.1.1. Si I es un conjunto finito entonces
a)
∑
F⊂I
(−1)|F | = 0 b)
∑
∅6=F⊂I
(−1)|F | = −1
Demostración: Si |I| = n entonces I tiene
(
n
k
)
subconjuntos de k ele-
mentos. La suma de los términos (−1)|F | correspondientes a estos sub-
conjuntos será entonces (−1)k
(
n
k
)
. Pero si sumamos estas expresiones para
k = 0, 1, . . . , n el resultado es 0, como demostramos en (3.1.6) . Aśı resulta la
primera igualdad. Para obtener la segunda simplemente se pasa al segundo
miembro el término correspondiente al conjunto vaćıo, que es (−1)0 = 1.
Principio de inclusiones y exclusiones 4.1.2.
|
n⋃
i=1
Ai| = −
∑
∅6=F⊂Nn
(−1)|F ||AF |
Demostración: Sea A =
⋃n
i=1Ai. Si x ∈ A definamos I(x) = {i ∈ Nn :
x ∈ Ai}. Entonces se tiene:
−
∑
∅6=F⊂Nn
(−1)|F ||AF | = −
∑
∅6=F⊂Nn
(−1)|F |
∑
x∈AF
1 =
= −
∑
x∈A
∑
∅6=F⊂I(x)
(−1)|F | = −
∑
x∈A
(−1) =
∑
x∈A
1 = |A|
La justificación de las igualdades anteriores es la siguiente: en primer
lugar substitúımos |AF | por una suma de tantos unos como elementos tenga
AF . En la doble sumatoria resultante invertimos el orden de sumación, de
modo que en la primera sumatoria x recorre A y en la segunda sumamos en
aquellos conjuntos de ı́ndices F ⊂ Nn tales que F 6= ∅ y x ∈ AF . Pero esta
última condición es equivalente a decir que F ⊂ I(x). Finalmente aplicamos
la segunda igualdad del Lema (4.1.1).
Teoŕıa Combinatoria 41
Fórmula de Sylvester 4.1.3. Si A1, . . . , An son subconjuntos de un con-
junto X entonces
|
n⋂
i=1
Ai| =
∑
F⊂Nn
(−1)|F ||AF |
Observaciones: Ai es el complemento de Ai respecto a X, es decir X\Ai. En
el miembro derecho de la igualdad F puede ser vaćıo. Según la convención
A∅ = X el término correspondiente en la sumatoria es (−1)|∅||A∅| = |X|.
Demostración:
|
n⋂
i=1
Ai| = |X\
n⋃
i=1
Ai| = |X| − |
n⋃
i=1
Ai| =
= |X|+
∑
∅6=F⊂Nn
(−1)|F ||AF | =
∑
F⊂Nn
(−1)|F ||AF |
4.2 Funciones sobreyectivas
Como aplicación del principio de inclusiones y exclusiones calcularemos el
número de funciones sobreyectivas de un conjunto finito A = {a1, . . . , an}
en otro B = {b1, . . . , bm}. Denotaremos mediante Sobre(A,B) el conjunto
de las funciones de A sobre B.
Proposición 4.2.1. Si |A| = n y |B| = m entonces
|Sobre(A,B)| =
m−1∑
k=0
(−1)k
(
m
k
)
(m− k)n =
m∑
k=1
(−1)k+m
(
m
k
)
kn
Demostración: Sea Gi = {f : A → B\{bi}} el conjunto formado por las
funciones de A en B que no toman el valor bi. Es claro que podemos escribir
Sobre(A,B) = BA\(∪mi=1Gi). Observemos también que si F es un conjunto
de k ı́ndices entre 1 y m entonces ∩i∈FGi son las funciones de A en B que no
toman ningún valor bi con i ∈ F . Es decir que ∩i∈FGi son las funciones de
A en B\{bi : i ∈ F}, y por lo tanto su número es (|B| − |F |)n = (m− k)n.
42 José H. Nieto
Por último, recordemos que para cada k entre 0 y m hay
(
m
k
)
subconjuntos
de Nm con k elementos. Estamos ya en condiciones de aplicar (4.1.3):
|Sobre(A,B)| =
∑
F⊂Nn
(−1)|F ||
⋂
i∈F
Gi| =
m∑
k=0
(−1)k
(
m
k
)
(m− k)n
En esta última sumatoria podemos hacer variar el ı́ndice k desde 0 hasta
m − 1, puesto que el sumando correspondiente a k = m es nulo. Para
obtener la segunda expresión para |Sobre(A,B)| basta efectuar el cambio de
variable h = m − k en la fórmula que acabamos de demostrar, recordando
que
(
m
m−h
)
=
(
m
h
)
4.3 Desarreglos
Un desarreglo de los números del 1 al n es una permutación σ de Nn tal que
σ(i) 6= i , ∀i = 1, . . . , n. En otras palabras los desarreglos son las permuta-
ciones sin puntos fijos. Aplicando el principio de inclusiones y exclusiones
es posible calcular fácilmente el número de desarreglos.
Proposición 4.3.1. El número de desarreglos de los números del 1 al n es
Dn = n!
(
1− 1
1!
+
1
2!
− · · ·+ (−1)
n
n!
)
Demostración: Sea Sn el conjunto de todas las permutaciones de los nú-
meros del 1 al n. Definamos Ai como el conjunto de las permutaciones que
dejan fijo el número i, es decir Ai = {σ ∈ Sn : σ(i) = i}. Es claro que |Ai| =
(n − 1)! , puesto que Ai se puede identificar con las permutaciones de un
conjunto de n− 1 elementos, a saber {j ∈ Nn : j 6= i}. Si F ⊂ Nn entonces
∩i∈FAi son las permutaciones de Nn que dejan fijos todos los elementos de
F . El número de tales permutaciones es (n−|F |)!. Nuevamente estamos en
condiciones de aplicar (4.1.3):
|{σ ∈ Sn : σ(i) 6= i ∀ i = 1, . . . , n}| = |
⋂
i∈F
Ai| =
∑
F⊂Nn
(−1)|F |(n− |F |)! =
n∑
k=0
(−1)k
(
n
k
)
(n− k)! = n!
n∑
k=0
(−1)k
k!
Teoŕıa Combinatoria 43
Observación: De (4.3.1) se deduce que limn→∞(Dn/n!) = e−1. Esto se puede
decir en lenguaje probabiĺıstico aśı: la probabilidad de que una permutación
de los números del 1 al n escogida al azar sea un desarreglo tiende al valor
ĺımite e−1 cuando n tiende a infinito.
4.4 Aplicaciones a la teoŕıa de números
La función µ de Möbius se define para cada número natural n > 1 de la
manera siguiente:
µ(n) =
{
(−1)r si n es producto de r primos diferentes
0 si n es divisible por un cuadrado perfecto mayor que 1
Además por convención µ(1) = 1 . Aśı por ejemplo tenemos que µ(2) =
−1, µ(6) = 1, µ(12) = 0 y µ(30) = −1.
Proposición 4.4.1. Si n > 1 entonces∑
d|n
µ(d) = 0
Demostración: Es claro que los únicos divisores de n que hace falta consi-
derar son el 1 y los que son producto de primos diferentes ya que los demás
(es decir los que sean divisibles por un cuadrado perfecto) no contribuirán
en nada a la suma. Sean p1, . . . , pk los divisores primos de n. Aceptando