Apunte Combinatorias

CAPÍTULO

5

S UMATORIAS Y C OMBINATORIA

5.1. Factoriales
Un número factorial corresponde la multiplicación sucesiva de los números naturales hasta menores o iguales al número en cuestión. Veamos una definición más formal.
Sea n ∈ N se define el factorial de n, que denotaremos por n! como:
n! = 1 · 2 · 3 · ... · (n − 2) · (n − 1) · n

Ejemplos: Calcule los siguientes factoriales.
• 3! = 1 · 2 ·3 = 6
• 4! = 1 · 2 · 3 · 4 = 24
• 5! = 1 · 2 · 3 · 4 · 5 = 120
• 6! = 1 · 2 · 3 · 4 · 5 · 6 = 720
• 7! = 5! · 6 · 7 = 120 · 42 = 5040

Observación: Como convención se define 0! = 1

43

(5.1)

CAPÍTULO 5. SUMATORIAS Y COMBINATORIA

5.2. Nociones Básicas de Combinatoria
A menudo es necesario calcular de cuantas maneras se puede hacer algo. Para ilustrar esto consideremos los siguientes ejemplos.Ejemplo: ¿De cuántas maneras se pueden ordenar 4 cajas de distintos colores?
Tenemos un total de 4 posiciones y 4 cajas, en la primera posición podemos poner
cualquiera de las 4 cajas, en la segunda podemos poner cualquiera de las 3 restantes, en
la tercera podemos poner 2 y finalmente en la cuarta tenemos 1 opción. De esta forma
podemos decir que el número de “ordenes” distintos es:
N o = 4 · 3 ·2 · 1 = 4!

Llamaremos a este número de “ordenes” permutaciones.

Permutaciones
Dado un conjunto cualquiera con n elementos distinguibles diremos que una permutación corresponde a cualquier disposición ordenada de ellos. Además se define:
Permutación con Repetición
Si se tiene un conjunto de n elementos y se quieren elegir j elementos. Entonces el
número de permutaciones posibles es:
Pn = n · n ·· · n · n = nr

(5.2)

r veces

Esto pues para el primer elemento a escoger tendremos n opciones, para el segundo
dado que existe la posiblidad de repetir también tendremos n opciones y así sucesivamente.
Permutación sin Repetición
Considerando un conjunto de n elementos, sabemos que con estos se pueden formar distintas permutaciones. ¿Qué pasa si no se pueden repetir los elementos?
Supongamos quetenemos un conjunto de 10 elementos distinguibles, entonces para el primer elemento de la permutación tenemos 10 opciones posibles. Para el segundo,
dado que ya utilizamos uno quedan 9, para el tercero 8, luego 7 y así sucesivamente.

P 10 = 10 · 9 · 8 · · · 1 = 10!
44

(5.3)

5.2. NOCIONES BÁSICAS DE COMBINATORIA

Pero ¿Qué ocurre si solamente se quieren elegir 4 elementos?
En este casotendremos:
P 10 = 10 · 9 · 8 =

10!
7!

(5.4)

Entonces, de manera general diremos que el número de permutaciones de j elementos que se pueden formar a partir de un conjunto de n elementos es:
j

Pn =

n!
(n − j )!

(5.5)

Ejemplo: Supongamos que tenemos 4 pelotas de distintos colores. Si tenemos 2 cajas
las cuales cada una permite guardar 1 pelota ¿Cuántas combinaciones distintas de cajas
se puedenarmar?
Es claro que en la primera caja podemos poner cualquiera de las 4 pelotas, a continuación, en la segunda caja solamente tenemos 3 pelotas para poner. Luego el número
de combinaciones es:
N o = 4 · 3 = 12
¿Qué ocurre si ahora tenemos 3 cajas?
Vemos que nuevamente en la primera podemos poner 4 pelotas, en la segunda 3 y en
la tercera solo nos quedan dos opciones, así en este caso el número decombinaciones
es:
N o = 4 · 3 · 2 = 24
¿Qué ocurre si pudieramos repetir las pelotas?
En este caso nuevamente para la primera caja tenemos 4 opciones, como podemos
repetir entonces en la segunda caja podremos poner 4 pelotas y en la tercera lo mismo.
Luego tenemos el siguiente número de combinaciones:
N o = 4 · 4 · 4 = 64

En las permutaciones el orden en que se disponen los elementos es relevante,veamos ahora el caso en que no lo es.

Combinaciones
Dado un conjunto cualquiera con n elementos distinguibles definimos:
45

CAPÍTULO 5. SUMATORIAS Y COMBINATORIA

Combinaciones sin Repetición
Se llama combinación sin repetición de k elementos, donde k < n, a cualquier subconjunto de k elementos distintos. El número de combinaciones en este caso de denota
como C nk y se define como:

C nk =

1...