Capı́tulo 2.
Combinatoria
1 Introducción
Por si acaso algún estudiante no estuviera familiarizado con la combinatoria, incluimos esta
lección para repasar los conceptos básicos.
2 Permutaciones
Permutar (del latı́n mutare, que significa cambiar, y el prefijo per-, que indica que algo se
realiza en grado máximo) unos objetos es tanto como reordenarlos. En el lenguaje preciso de
las Matemáticas, una permutación de un conjunto A es una biyección de A en A. Si el cardinal
de A es m, hablamos de una permutación de m elementos. Ası́, una permutación de x1 , . . . , xm
es una reordenación xσ1 , . . . , xσm .
Queremos contar: ¿cuántas permutaciones diferentes se pueden formar con m elementos? La
respuesta la da el producto m · (m − 1) · (m − 2) . . . · 2 · 1, que abreviamos como m! (léase factorial
de m, o m factorial ). Es fácil comprender la razón: para elegir qué elemento colocamos en el
primer lugar tenemos m posibilidades, para el segundo nos quedan m − 1 opciones (lo que da
m · (m − 1) variantes para las dos primeras posiciones), m − 2 para el tercero y ası́ sucesivamente.
Ejemplo
¿De cuántas maneras se pueden repartir las tareas domésticas semanales 7 hermanos (a razón
de uno cada dı́a)?: 7! ¿Cuántas claves de 8 letras se pueden formar reordenando la palabra MER-
LUZAS?: 8! ¿Y con las letras de ABADEJOS? ¿De BACALAOS? ¿Y con las de CASTAÑAS?
(hay que dividir por 2! en el primer caso, por 3! en el segundo y por 3!2! en el tercero) ¿De
cuántas manera se puede ordenar un mazo de cartas de la baraja española?: 40! ¿Y si sólo nos
fijamos en el palo, y no en el valor del naipe? (hay que dividir por 10!4 )
Tres observaciones.- La primera es que 0! = 1, como seguramente conocen. Ası́, es válida
la ley de recurrencia (m + 1)! = (m + 1).m! La segunda es que los valores de m! crecen muy
deprisa al aumentar m. Para hacernos una idea, observemos que 5! = 120, 10! = 3628800, 20! =
2432902008176640000 tiene 19 cifras, 50! ≈ 3 × 1064 , 100! ≈ 10158 , 200! ≈ 79 × 10374 .
√
Cuando m es muy grande, m! ≈ mm .e−m . 2πm
La tercera es que hay una función (la función Γ), que se estudia en Análisis superior, que
interpola el factorial, esto es, vale n! cuando la evaluamos en n + 1, y tiene sentido para valores
positivos no enteros de la variable. Pero eso excede al objetivo de este curso, se cita aquı́
aprovechando la ocasión para aumentar su cultura.
1
3 Variaciones
3.1 Variaciones ordinarias
Dados n elementos a1 , . . . , an , si seleccionamos m de ellos prestando atención al orden en que
los elegimos, decimos que tenemos una variación de esos n elementos tomados de m en m.
Si queremos darle más precisión, podemos decir que una variación es una aplicación inyectiva
(¿recuerdan lo que eso significa?) del conjunto {1, 2, . . . , m} en el conjunto A = {a1 , . . . , an }.
El número de tales variaciones se expresa mediante un producto de m factores, empezando
por n y decreciendo hasta llegar a n − (m − 1): Vn,m = n.(n − 1). . . . .(n − m + 1), que podemos
abreviar como n!/(n − m)! Nótese que si m = n, entonces recaemos en las permutaciones, y si
m > n, entonces Vn,m = 0.
Ejemplo
Elegir junta directiva (presidente, vicepresidente, tesorero y secretario) entre 20 personas.
Formar un equipo de baloncesto (base, alero derecho, alero izquierdo, pı́vot y ala-pı́vot) con 9
jugadores.
3.2 Variaciones con repetición
Si en la definición de variación de n elementos tomados de m en m tachamos la palabra inyectiva,
obtenemos las variaciones con repetición. Estamos hablando ası́ de aplicaciones de un conjunto
de m elementos en uno de n. ¿Cuántas hay? Claramente, el número total es un producto de m
factores, que empieza en n pero ahora no va disminuyendo: n.n. . . . .n = nm .
Ejemplo
¿Cuántas quinielas diferentes se pueden rellenar?: 315 ¿Cuántos números hay de cinco cifras?:
105 −104 (hay que descontar los que empiezan por 0) ¿Cuántas claves de 4 letras se pueden formar
con la palabra CAMINOS?: 74 ¿Y si no se pueden repetir letras?: entonces son variaciones:
7·6·5·4
4 Combinaciones
En un conjunto de n elementos, una combinación es un subconjunto. Hablamos de combina-
ciones de n elementos tomados de m en m para referirnos a subconjuntos de m elementos en un
conjunto de n. Suponen, pues, una selección de m objetos tomados de una muestra de n (como
las variaciones), pero sin que importe el orden: los conjuntos {a, b} y {b, a} son el mismo.
Para contar el número de combinaciones nos fijamos en las variaciones: cada combinación
{a1 , . . . , am } se puede ordenar de m! formas diferentes, de suerte que hay m! variaciones por cada
n!
combinación, y ası́ m!.Cn,m = Vn,m , de donde despejamos y resulta Cn,m = m!(n−m)! Se suele
2
( )
n
emplear la notación para ese cociente. Los números combinatorios se disponen a veces
m
en un triángulo (llamado “de Pascal”o “de Tartaglia”) con numerosas propiedades interesantes
y curiosas.
Ejemplo
( )
40
Cuando jugamos al mus, nos dan 4 cartas de una baraja de 40: . Al elegir 3 nombres
4
( )
50
al azar para un jurado (entre 50), tenemos posibilidades.
3
( ) ( ) ( ) ( ) ( )
n n n+1 n n
Observación.- = = 1; = +
0 n m m m−1
Esas propiedades se pueden demostrar y se pueden entender. No es difı́cil. Háganlo.
Otra observación.- Conocerán seguramente la fórmula del binomio de Newton, que emplea
números combinatorios: n
( ) (x + y) es igual a una suma de n + 1 términos, cada uno de los cuales
n
es de la forma xk y n−k
k
∑n ( )
n n
(x + y) = xk y n−k
k
k=0
