A maior rede de estudos do Brasil

Grátis
179 pág.
Análise combinatória matemática

Pré-visualização | Página 1 de 30

Combinatoria
enumerativa
Eduardo Piza Volio
i
Combinatoria
enumerativa
Eduardo Piza Volio
iii
iv
Créditos de la Editorial
Diagramado:
Levantado de texto:
Revisión:
Ficha catalográfica
v
A mis maestros Bernardo Montero
y Francisco Ramı́rez, quienes con su
empeño, mı́stica y dedicación forjaron
nuestra actual Escuela de Matemática.
Contenido
Prefacio xi
1 Permutaciones 1
1.1 Cardinalidad de conjuntos finitos . . . . . . . 1
1.2 Permutaciones de objetos distintos . . . . . . 2
1.3 Permutaciones con objetos repetidos . . . . . 3
1.4 Permutaciones de n objetos, tomados m de
ellos a la vez . . . . . . . . . . . . . . . . . . 5
1.4.1 Selección con reemplazo . . . . . . . . 5
1.4.2 Selección sin reemplazo . . . . . . . . 6
1.5 Números de Stirling de primera especie . . . . 7
1.6 Ejercicios . . . . . . . . . . . . . . . . . . . . 9
2 Arreglos, distribuciones, combinaciones
y selecciones 15
2.1 Arreglos de objetos en cajas ordenadas . . . . 15
2.2 Palabras en orden creciente . . . . . . . . . . 17
2.3 Número de soluciones de una ecuación . . . . 18
2.4 Combinaciones . . . . . . . . . . . . . . . . . 20
2.5 Combinaciones sin repeticiones . . . . . . . . 21
2.6 Distribución de objetos en varios subconjuntos 23
2.7 Selección simultánea de objetos de varias clases 25
2.8 Combinaciones con repeticiones . . . . . . . . 25
2.9 Selección de objetos no consecutivos . . . . . 26
2.10 Ejercicios . . . . . . . . . . . . . . . . . . . . 29
3 Coeficientes binomiales y multinomiales 35
3.1 El binomio de Newton . . . . . . . . . . . . . 35
vii
viii Contenido
3.2 El triángulo de Pascal . . . . . . . . . . . . . 37
3.3 Generalización de los coeficientes binomiales . 41
3.4 El teorema del multinomio . . . . . . . . . . . 41
3.5 Ejercicios . . . . . . . . . . . . . . . . . . . . 42
4 Particiones de un conjunto 47
4.1 Números de Stirling de segunda especie . . . 47
4.2 Los números de Bell . . . . . . . . . . . . . . 52
4.3 Fórmulas de inversión . . . . . . . . . . . . . 57
4.4 Ejercicios . . . . . . . . . . . . . . . . . . . . 60
5 Principio de inclusión y exclusión 63
5.1 Introducción . . . . . . . . . . . . . . . . . . . 63
5.2 Fórmula fundamental . . . . . . . . . . . . . 65
5.3 Algunas aplicaciones . . . . . . . . . . . . . . 67
5.3.1 Coloreando una casa . . . . . . . . . . 67
5.3.2 Desarreglos y el problema
de los reencuentros . . . . . . . . . . . 69
5.3.3 El problema de los matrimonios . . . . 71
5.4 Ejercicios . . . . . . . . . . . . . . . . . . . . 72
6 Funciones generadoras 77
6.1 Introducción y definiciones . . . . . . . . . . . 77
6.2 Algunas funciones generadoras . . . . . . . . 78
6.3 Funciones generadoras de combinaciones . . . 80
6.4 Funciones generadoras de permutaciones . . . 83
6.5 Ejercicios . . . . . . . . . . . . . . . . . . . . 85
7 Particiones de un entero 89
7.1 Introducción . . . . . . . . . . . . . . . . . . . 89
7.2 Definiciones y relaciones por recurrencia . . . 90
7.3 Diagramas de Ferrars . . . . . . . . . . . . . . 94
7.4 Particiones auto-conjugadas . . . . . . . . . . 95
7.5 Particiones en partes impares . . . . . . . . . 97
7.6 Funciones generadoras de particiones . . . . . 98
7.7 Ejercicios . . . . . . . . . . . . . . . . . . . . 100
Contenido ix
8 Otros tópicos de la teoŕıa de combinatoria 103
8.1 Denumerantes . . . . . . . . . . . . . . . . . . 103
8.2 Composiciones . . . . . . . . . . . . . . . . . 104
8.3 Teoŕıa de Grafos . . . . . . . . . . . . . . . . 106
8.4 Teoŕıa de Ramsey . . . . . . . . . . . . . . . . 106
8.5 Grupos de permutaciones . . . . . . . . . . . 111
8.6 Algunos problemas abiertos en combinatoria . 112
8.6.1 Dos problemas de Paul Erdös . . . . . 112
8.6.2 El “Football Pool Problem” . . . . . . 116
8.7 Ejercicios . . . . . . . . . . . . . . . . . . . . 118
9 Las soluciones de los ejercicios impares 119
9.1 Ejercicios del caṕıtulo 1 . . . . . . . . . . . . 119
9.2 Ejercicios del caṕıtulo 2 . . . . . . . . . . . . 127
9.3 Ejercicios del caṕıtulo 3 . . . . . . . . . . . . 133
9.4 Ejercicios del caṕıtulo 4 . . . . . . . . . . . . 140
9.5 Ejercicios del caṕıtulo 5 . . . . . . . . . . . . 144
9.6 Ejercicios del caṕıtulo 6 . . . . . . . . . . . . 150
9.7 Ejercicios del caṕıtulo 7 . . . . . . . . . . . . 152
9.8 Ejercicios del caṕıtulo 8 . . . . . . . . . . . . 156
Bibliograf́ıa 159
Indice 161
Prefacio
¿De cuántas maneras. . . ? La combinatoria enumerativa
puede definirse en pocas palabras como el arte de contar con-
figuraciones en problemas de naturaleza discreta.
En este trabajo se presenta una introducción elemental a
esta fascinante y dif́ıcil disciplina de la matemática, presen-
tando los resultados básicos de combinatoria que en opinión
del autor todo estudiante de matemáticas o de enseñanza de
las matemáticas debeŕıa conocer y estudiar.
La exposición de la teoŕıa se presenta en forma resumida
y condensada, poniéndose especial atención en aquellas de-
mostraciones de carácter intŕınsecamente combinatorio. En
esta obra se tratan de evitar las versiones de las demostra-
ciones que empleen argumentos no combinatorios, tales como
por ejemplo el principio de inducción matemática. En vez de
ello, se prefieren las demostraciones alternativas que empleen
argumentaciones t́ıpicamente combinatorias. De esta manera
se ilustra acerca de la riqueza de recursos disponibles en el
razonamiento dentro de este campo de la matemática, en
el cual las demostraciones son a veces tan ingeniosas como
informales. Por ejemplo, resultados tan conocidos como el
binomio y el multinomio de Newton, son demostrados aqúı
en muy pocas ĺıneas, utilizando para ello únicamente argu-
mentos elementales de tipo combinatorio.
Debe tenerse en consideración que la teoŕıa de la combi-
natoria enumerativa constituye un campo muy vasto y com-
plejo, sobre el cual se han escrito gran cantidad de obras
de gran profundidad y se realiza mucha investigación en la
actualidad. En esta obra tan solo se pretende introducir al
xi
xii Prefacio
estudiante a la teoŕıa general, presentando los resultados más
importantes e interesantes.
Al lector interesado en profundizar sobre la teoŕıa de la
combinatoria se le puede recomendar, entre otros libros, la
lectura de la bella obra de Claude Berge, Principles of Com-
binatorics (Academic Press, New York, 1971), el cual es un
afamado clásico sobre el tema y de relativamente fácil lectura.
He utilizado algunas versiones preliminares y condensadas
de esta obra como material didáctico en varios de los cur-
sos de las carreras de Matemática Pura y Enseñanza de las
Matemáticas en la Universidad de Costa Rica, entre ellos:
Teoŕıa de Probabilidades (siglas MA-0720 y MA-0817); Ma-
temática Finita (sigla MA-0904), Principios de Estad́ıstica
Matemática (sigla MA-0372) y Seminario de Combinatoria
(sigla MA-600).
Uno de los objetivos de este trabajo es llenar el vaćıo de
material didáctico existente sobre los elementos de la teoŕıa
de la combinatoria. A pesar de que en el campo de la com-
binatoria existen tratados altamente especializados y de re-
conocida calidad, sin embargo éstos son claramente inapropi-
ados e inaccesibles para los estudiantes de los primeros años
de las carreras de matemáticas y de enseñanza de las matemáticas.
Principalmente hacia estos estudiantes está dirigido este li-
bro.
La obra contiene un caṕıtulo final con la solución de los
ejercicios impares. Además contiene una selección de bi-
ograf́ıas de los matemáticos que están asociados con los prin-
cipales resultados y temas aqúı tratados.
Deseo manifestar mi agradecimiento a todas aquellas per-
sonas que colaboraron de una u otra forma en la elaboración
y corrección de este libro de texto, en especial a Gabriel Sosa,
quien leyó el manuscrito original y realizó algunas cŕıticas que
ayudaron a mejorarlo.
Eduardo Piza Volio
San José, noviembre del 2002
Caṕıtulo 1
Permutaciones
1.1 Cardinalidad de conjuntos finitos
La cardinalidad de un conjunto finito X