combinatoria

La Universidad del Zulia
Facultad Experimental de Ciencias
Departamento de Matem´tica y Computaci´n
a
o

Teor´ Combinatoria
ıa

Jos´ Heber Nieto Said
e

Maracaibo, 1996

TEORIA COMBINATORIA
ISBN 980-232-573-2
autor: Jos´ H. Nieto
e
Departamento de Matem´tica y Computaci´n
a
o
Facultad Experimental de Ciencias
La Universidad del Zulia - Apartado Postal 526
Maracaibo,Venezuela
Fax: 58 61 515390
direcci´n electr´nica: jhnieto@luz.ve
o
o
c La Universidad del Zulia, 1996.

´
Indice General
1 Conceptos b´sicos
a
1.1 Qu´ es la Combinatoria .
e
1.2 Or´
ıgenes y evoluci´n de la
o
1.3 Los principios b´sicos . .
a
1.4 Ejercicios . . . . . . . . .
2 Las
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8

. . . . . . . .
Combinatoria
. . . . . . . .
. . . . . .. .

configuraciones cl´sicas
a
Arreglos . . . . . . . . . . . .
Arreglos con repetici´n . . . .
o
Permutaciones . . . . . . . .
Permutaciones con repetici´n
o
Combinaciones . . . . . . . .
Combinaciones con repetici´n
o
Algoritmos combinatorios . .
Ejercicios . . . . . . . . . . .

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
..
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
..
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

1
1
2
4
10

.
.
.
.
.
.
.
.

13
13
15
15
16
17
19
21
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
4.1 El Principio de Inclusiones y Exclusiones
4.2 Funciones sobreyectivas . . . . . . . . .
4.3 Desarreglos . . . . . . . . . . . . . . . .
4.4 Aplicaciones a la teor´ de n´meros . . .
ıa
u
4.5 Ejercicios . . . . . . . . . . . . . . . . .
iii

aplicaciones
. . . . . . . . .
. . . .. . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

39
39
41
42
43
45

5 Relaciones de recurrencia y funciones generatrices
5.1 N´meros de Fibonacci . . . . . . . . . . . . . . . . .
u
5.2 Funciones generatrices . . . . . . . . . . . . . . . . .
5.3 Relaciones de recurrencia lineales . . . . . . . . . . .
5.4N´meros de Catalan . . . . . . . . . . . . . . . . . .
u
5.5 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . .
6 Permutaciones y particiones
6.1 Permutaciones . . . . . . . . . . . . . . . . . . .
6.2 N´meros de Stirling de primera clase . . . . . . .
u
6.3 Aplicaci´n al an´lisis de algoritmos . . . . . . . .
o
a
6.4 Particiones, n´meros de Stirling de segunda clase
u
de Bell . . . .. . . . . . . . . . . . . . . . . . . .
6.5 Ejercicios . . . . . . . . . . . . . . . . . . . . . .
7 Teoremas de existencia
7.1 El Teorema de Ramsey . . . . . . . .
7.2 Aplicaciones a la teor´ de grafos . .
ıa
7.3 Una aplicaci´n geom´trica . . . . . .
o
e
7.4 El Teorema de Graham - Rothschild
7.5 Conjuntos parcialmente ordenados .
7.6 Sistemas de representantes distintos
7.7Ejercicios . . . . . . . . . . . . . . .

.
.
.
.
.
.
.

8 Enumeraci´n bajo acci´n de grupos
o
o
8.1 Acci´n de un grupo sobre un conjunto
o
8.2 La Acci´n de Polya . . . . . . . . . . .
o
8.3 Enumeraci´n de grafos no isomorfos .
o
8.4 Ejercicios . . . . . . . . . . . . . . . .
A Soluciones y sugerencias
A.1 Cap´
ıtulo 1 . . . . . . .
A.2 Cap´
ıtulo 2 . . . . . . .
A.3 Cap´
ıtulo...