114 Combinatoria

Combinatoria I

Un candado para empezar

¿Qué es la combinatoria?
La combinatoria o análisis combinatorio, estudia la manera de ordenar objetos, y además estudia las propiedades de esas
ordenaciones. Con frecuencia, el análisis combinatorio pide calcular el número de posibilidades que tenemos para ordenar ciertos
objetos con ciertas reglas prefijadas sin obtener las ordenaciones en sí.

Y paraempezar… líos con un candado
Habrán visto alguna vez uno de esos candados a los cuales se les llama “candado de combinación”, nosotros en principio les
llamaremos “candados de números”, después ustedes mismos dirán porqué.
Bueno, tengo un candado con 3 discos 1, 2 y 3, en cada uno de los cuales aparecen los dígitos 0, 1, 2, hasta el 9.
¿Cuántas números distintos de 3 dígitos puedo formar? A ver,desde el 000 al 999, son 1000 números distintos.
Analicemos un poco:
Son
10 posibilidades en el disco 1
10 posibilidades en el disco 2
10 posibilidades en el disco 3
TOTAL:
10x10x10 = 1000 posibilidades = 103
¿Y cómo podemos interpretar esto con lo que ya sabemos? Por ejemplo, un candado que abre con el número 227.
1
2
3
A

0
1
2
3
4
5
6
7
8
9

B

Bueno, puedo interpretar el número 227 como unafunción de dominio el conjunto A ={1,2,3} y conjunto de llegada B =
{0,1,2,3,4,5,6,7,8,9}. Observa que realmente son 1000 las posibilidades, 10 para la primer flecha, 10 para la segunda, 10 para la
tercera. En total 103 posibilidades. Para practicar un poco, piensen cuantos de estos números son pares.
Sigamos. ¿Qué pasa ahora si digamos el conjunto A tuviera k elementos y el conjunto B tuviera nelementos? Tendríamos nk
posibilidades.

Arreglos con repetición
Definición: Llamamos Arreglos con repetición de n elementos en grupos de k elementos a todas las posibles funciones de
dominio un conjunto A de k elementos y conjunto de llegada B de n elementos, ¿pero, cuántos arreglos con repetición hay?
n

Llamamos número de arreglos a ese número, que es: ARk = n

k

Observa bien que dijimos domino A yno conjunto de partida A, por lo tanto queda claro que de todos los elementos del conjunto
A debe partir exactamente una flecha, o dicho mejor todo elemento de A tiene una imagen en B.

Ejemplo: Formemos todos los arreglos con repetición de 3 elementos tomándolos de a dos. Bueno B = {a, b, c} y
los arreglos serán:

aa ab ac ba bb bc ca cb cc

3

2

Total: AR2 = 3 = 9

Una observación: Usamos lamisma notación para los arreglos y para el número de arreglos. A veces nos basta
con hallar cuantos son. Otras veces hay que escribirlos todos. ¿Qué pasa si sacamos los que tienen letras
repetidas? ¿Cuántos nos quedan?
Ejercicio: Formar todos los arreglos con repetición de 2 elementos tomándolos de a tres si B = {1, 2}

El principio de Dirichlet o principio del palomar
Supongan que estan en unparque dándole de comer a las palomas. En total hay 21 palomas. De repente un bocinazo las asusta y
van a esconderse al palomar. El palomar tiene 20 agujeros. ¿Qué puede concluirse? Muy fácil, en un agujero por lo menos hay más
de una paloma. ¿Cierto? Este sencillo principio que se llama principio de Dirichlet o principio del palomar es muy utilizado en
matemática. Lo usaremos luego.

Nota histórica:Johann Dirichlet, matemático alemán, nacido en 1805, muerto en 1859. Se lo recordaba como alto,
de bigote y barba, de voz ronca pero suave, siempre olvidando la hora, de forma tal que a veces, a
mitad de una frase, miraba su reloj y salía corriendo, sin despedirse ni terminar la idea.

Arreglos simples
¿Qué pasará ahora si en los números del candado eliminamos todos aquellos que tengan dígitosrepetidos? AHORA NO VALE
REPETIR., el 227 NO vale, pero si el 346, el 712, el 079, etc. ¿Cuántos me quedan?
Ahora tenemos:
10 posibilidades en el disco 1
9 posibilidades en el disco 2
8 posibilidades en el disco 3
TOTAL:
10 x 9 x 8 = 720 posibilidades
Ahora, si n y k son números cualesquiera:

n
posibilidades para la flecha 1
n-1
posibilidades para la flecha 2
n-2
posibilidades para la flecha 3...