NOTAS DE COMBINATORIA

Apuntes de Combinatoria para la Olimpiada de
´
Matematicas
´
14 de marzo de 2002

´ndice general
I
1. Conteo.

2

´
1.1. Principios basicos de conteo. . . . . . . . . . . . . . . . . . . . . . .

2

1.2. Permutaciones. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.2.1.

-permutaciones de n objetos. . . . . . . . . . . . . . . . . .

5

´
1.2.2.Permutaciones circulares, y con repeticion. . . . . . . . . . .

7

1.3. Combinaciones. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

k

2. Coeficientes binomiales.
´
2.1. Identidades basicas.

10
. . . . . . . . . . . . . . . . . . . . . . . . . . 10

´
2.2. El Triangulo de Pascal
y el Teorema del Binomio. . . . . . . . . . . . . . . . . . . . . . . . . 13
3. Dosprincipios importantes.

16

3.1. Principio de las casillas. . . . . . . . . . . . . . . . . . . . . . . . . . 16
´
´
A. Induccion Matematica.

18

´
´
´
A.1. El metodo de Induccion Matematica. . . . . . . . . . . . . . . . . . . 19
A.2. Problemas y Ejercicios. . . . . . . . . . . . . . . . . . . . . . . . . . 21
B. Soluciones y sugerencias de ejercicios seleccionados.

1

23Cap´tulo 1
ı

Conteo.
1.1.

´
Principios basicos de conteo.

´
Hay dos principios basicos en combinatoria.

´
1.1 (Principio de la adicion) Si se desea escoger un objeto que puede

tener r tipos distintos, y para el primer tipo hay t1 opciones, para
el segundo tipo hay t2 opciones, para el tercer tipo t3 opciones, y
as´ sucesivamente hasta t opciones para el ultimo tipo, entoncesel
ı
´
objeto puede escogerse de t1 + t2 + ¡ ¡ ¡ + t maneras.
r

r

Lo que el principio anterior dice, es que el total de opciones es la suma del
numero de opciones en cada tipo. Como ejemplo, supongamos que hay que
´
´
escoger un libro de entre 3 materias: matematicas, historia y biolog´a. Hay 6 libros
ı
´
de matematicas, 9 de historia y 4 de biolog´a. Entonces tenemos 6 + 9 + 4 =19
ı
opciones.

´
1.2 (Principio de la multiplicacion) Si una tarea se ha de realizar en

etapas, y si la primera etapa tiene k1 maneras de realizarse, la
segunda tiene k2 maneras, y as´ sucesivamente hasta k maneras de
ı
realizar la ultima, entonces el n´mero de formas de realizar la tarea es
´
u
k1 ¢ k2 ¢ ¡ ¡ ¡ ¢ k .
n

n

n

´
Si una persona ha de escoger como vestirse,teniendo 4 camisas, 6 pantalones,
pares de calcetines y 2 pares de zapatos, entonces tiene 4 6 5 2 = 240 formas
´
de vestirse, ya que para cada eleccion de la camisa (4 opciones) tiene 6 opciones
´
´
para el pantalon, lo que da 4 6 = 24 opciones para camisa y pantalon. Para
cada una de esas 24 tiene 5 pares de calcetines, totalizando 120 formas, y para

¡ ¡ ¡

5

¢

2

´Combinatoria (Olimpiada de Matematicas)

3

cada una de esas tiene dos opciones para los zapatos, de modo que se duplica el
´
total y al final tiene 240 formas de vestirse. El principio de la multiplicacion puede
´
visualizarse mediante un diagrama de arbol

¡¡¡

´
pantalon 1

¡¡¡

´
pantalon 6

camisa 1

¡¡¡

Õ
nn
nnn
ÕÕ
nnn
ÕÕ
n
nnn
ÕÕ
ÕÕ camisa 2
´
pantalon 2 ¡ ¡ ¡zapato 1
calcet´n 1 ¡ ¡ ¡
ı
Õ
HTee€€€
HTTe €€
}}
ÕÕ ssss
ppp
HHT ee €€
p
}
ÕÕ ss
ppp
}}
HHTT ee €€€€
ÕÕsss
€
}}
ppp
TT ee
p
Õs
HH
}
e
´
HH TT eee pantalon 3 ¡ ¡ ¡ }}}}
total u
calcet´n x
ı 2
WW u
n
xxx
TT e
}
HH
nn
WWuuu
e
xxx
}} nnnnn
uu
HH TTT eee
}
WW u
xxx
e }}}nnn
x
WW uu
HH TT
n
WW
TT pantalon 4
HH
´
zapato 2
calcet´n 3 ¡ ¡ ¡
ı
Wcamisa 3¡ ¡ ¡
ee€€€
HH TT
WW
ee €€€
TT
WW
HH
ee €€€
WW
€€€
HH TT
ee
ee
HH
ee calcet´n 4 ¡ ¡ ¡
pantalon 5 ¡ ¡ ¡
camisa ¡ ¡ ¡
ı
HH ´
ee
HH
ee
ee
HH
e
calcet´n 5
ı

¡¡¡

Veamos algunas ejercicios que usan estos principios.

´
Ejemplo. ¿Cu´ ntos n´ meros de 5 cifras est´ n formados unicamente de cuatros y doses
a
u
a
(ejemplos: 44242; 24422)?
Nos est´ n pidiendo n´...