Contenidos
Combinatoria
La combinatoria es una rama de la matemática perteneciente al área de matemáticas discretas que estudia la enumeración, construcción y existencia de propiedades de configuraciones que satisfacen ciertas condiciones establecidas
Además, estudia las ordenaciones o agrupaciones de un determinado número de elementos. Es utilizada en estadística para realizar cálculos probabilísticos
Variaciones
Supongamos que queremos contar el número total de posibles aplicaciones inyectivas que pueden construirse de un conjunto X, de k elementos, en otro conjunto Y, de n elementos (las cuales tendrán que ser k \le n)
Una aplicación f| X \rightarrow Y con f inyectiva, queda completamente determinada si conocemos cada una de las imágenes de los k elementos de X
Si consideramos la aplicación f como una palabra de k letras del alfabeto Y, ésta no tendrá letras repetidas. La aplicación f será f(x_1)f(x_2)\cdots f(x_n) entonces:
f(x_1) \in Y
f(x_2) \in Y \text{\ }\{f(x_1)\} = \{y \in Y | y \not= f(x_1)\}
f(x_3) \in Y \text{\ }\{f(x_1), f(x_2)\} = \{y \in Y | y \not= f(x_1), y \not= f(x_2)\}
\vdots
f(x_n) \in Y \text{\ }\{f(x_1), \cdots, f(x_{k - 1})\} = \{y \in Y | y \not= f(x_1), \cdots, y \not= f(x_{k - 1})\}
Si denotamos por V(n, k) al total de aplicaciones inyectivas de X en Y y lo llamamos variaciones de n elementos tomados de k en k, entonces tenemos por el principio del producto que:
V(n, k) = n \cdot (n - 1) \cdot (n -2)\cdots (n - k + 1) = \frac{n!}{(n-k)!}
Dónde n! = n \cdot (n - 1) \cdot (n -2) \cdot \cdots \cdot 2 \cdot 1 que es el producto de todos los números naturales desde 1 hasta n (a esta cantidad se la llama factorial de n)
Ejemplo de variaciones
¿Cuál es la probabilidad de que en entre un grupo de n personas haya 2 que celebren el cumpleaños el mismo día?
Calcular la probabilidad de los n conjuntos es muy tedioso, tenemos que calcular la probabilidad de que lo cumplieran 0, 1, \cdots, (n -1) el mismo día
Por eso es mejor calcular la probabilidad del suceso contrario. Es decir, la probabilidad de que n personas celebren su cumpleaños en días diferentes, viene a ser lo mismo que dar una lista ordenada de n días distintos de entre los 365 días del año. Por lo tanto tenemos que:
\text{Casos favorables = }V(365, n) = \frac{365!}{(365 - n)!}
Los casos posibles son todas las listas ordenadas de n días, por lo que se permiten repeticiones (son variaciones con repetición). Por lo tanto tenemos que:
\text{Casos posibles = }VR(365, n) = 365^n
Con lo que la solución a nuestro problema vendrá dada por:
p = 1 - \frac{\text{casos favorables}}{\text{casos posibles}} = 1 - \frac{V(365, n)}{VR(365, n)} = 1 - \frac{365!}{365^n \cdot (365 - n)!}
La siguiente tabla muestra la probabilidad p de que en un grupo de n personas haya al menos dos que celebren su cumpleaños el mismo día:
| n | p | n | p |
| 5 | 0.027136 | 35 | 0.814383 |
| 10 | 0.116948 | 40 | 0.891223 |
| 15 | 0.252901 | 45 | 0.940976 |
| 20 | 0.411438 | 50 | 0.970374 |
| 21 | 0.443688 | 55 | 0.986262 |
| 22 | 0.475695 | 60 | 0.994123 |
| 23 | 0.507297 | 65 | 0.997683 |
| 24 | 0.538344 | 70 | 0.999160 |
| 25 | 0.568700 | 75 | 0.999720 |
| 26 | 0.598241 | 80 | 0.999914 |
| 27 | 0.626859 | 85 | 0.999976 |
| 28 | 0.654461 | 90 | 0.999994 |
| 29 | 0.680969 | 95 | 0.99999856 |
| 30 | 0.706316 | 100 | 0.99999969 |
Variaciones con repetición
Supongamos que queremos contar el total de posibles aplicaciones que pueden construirse de un conjunto X, de k elementos, en otro conjunto Y, de n elementos
Una aplicación f| X \rightarrow Y queda completamente determinada si conocemos cada una de las imágenes de los k elementos de X
Es decir, debemos conocer f(x_i) con 1 \le i \le k. Esto equivale a dar una k-tupla (f(x_1), f(x_2), \cdots, f(x_k)) del conjunto Y^k = \overbrace{Y x \cdots x Y}^{k\;\rm veces}
También es equivalente a dar una palabra de k letras del alfabeto Y (f(x_1), f(x_2), \cdots, f(x_k)) o dar una selección ordenada de k elementos entre los de Y (pueden repetirse elementos de Y, es decir, puede ocurrir que f(x_i) = f(x_i)\text{ con }i \not= j)
La única condición es que f(x_i) \in Y. Por tanto, el total de aplicaciones de X en Y, o el total de variaciones con repetición de n elementos tomados de k en k, es igual al cardinal de Y^k que, por el principio del producto, es n^k. Si denotamos a este número por VR(n, k), entonces:
VR(n, k) = n^kEjemplo de variaciones con repetición
¿Cuál es la probabilidad de acertar en una quiniela el pleno al quince?
Rellenar una quiniela equivale a dar una lista de 15 símbolos eligiendo entre 1, X y 2, es decir, una palabra de longitud 15 construida con el alfabeto 1, X y 2
Con lo que tenemos que el número de quinielas posibles será de:
VR(3, 15) = 3^{15}
Sin embargo, esta no es la solución a nuestro problema, la cuál vendrá dada por:
Permutaciones
Llamaremos permutaciones de m elementos al número de variaciones sin repetición de m elementos que se pueden formar
P_m = m!Ejemplo de Permutaciones
Tenemos una estantería en la que caben tres libros y queremos ordenarlos sin que haya ninguno repetido. Cada libro tiene la portada de un color distinto: rojo, azul y verde. Para distinguirlos vamos a usar el conjunto L de libros y sus elementos son la primera letra del color de su portada:
L=\{R, A, V\}| Ordenación | Número de permutación |
| L=\{R, A, V\} | 1 |
| L=\{R, V, A\} | 2 |
| L=\{V, R, A\} | 3 |
| L=\{V, A, R\} | 4 |
| L=\{A, V, R\} | 5 |
| L=\{A, R, V\} | 6 |
Para calcular el número de permutaciones podemos ver que se han ido agrupando en conjuntos hasta obtener todas las variaciones posibles. La primera pasada se han empleado todos los 3 elementos. La segunda se descarta 1 y se usan sólo 2. La tercera y última, se descarta 1 y se usa el único elemento que queda
Por tanto, para calcular las permutaciones tenemos que multiplicar el número de elementos distintos de las 3 pasadas:
3\cdot 2 \cdot 1 = 6
O lo que es lo mismo:
Permutaciones con repetición
Llamaremos permutaciones con repetición de m elementos al número de variaciones de m elementos que se pueden formar cuando algunos elementos se repiten un número finito de veces
PR_{m}^{n_{1}, n_{2}, \cdots, n_k} = \frac{m!}{n_{1}! \times n_{2}! \times \cdots \times n_k!}Ejemplo de permutaciones con repetición
El resultado de un partido de fútbol fue 5-4
¿De cuántas maneras distintas se pudo llegar a dicho resultado?
A cualquier gol marcado por el equipo local lo denotamos por L y a cualquier gol marcado por el equipo visitante con V
El número de L o V total ha de ser de longitud 5 + 4 = 9, con lo que buscamos cualquier lista ordenada que contenga 5 L y 4 V en cualquier orden, con lo que representamos el orden posible de goles en el partido
Con lo que tenemos que el número de maneras distintas de llegar a ese resultado es de:
PR_{9}^{5, 4} = \frac{9!}{5! \cdot 4!} = 126Combinaciones
Llamaremos combinaciones de m elementos tomados de n en n al número de subconjuntos que se pueden formar con n de esos m elementos sin repetir ninguno
C_{m, n} = {m \choose n} = \frac{m!}{n! \cdot (m - n)!}Ejemplo de combinaciones
¿Cuál es la probabilidad de acertar la lotería primitiva?
En la lotería primitiva, hay 49 números posibles para jugar y se pueden elegir 6 de ellos, sin importar el orden en el que aparezcan
Para saber cuántas combinaciones posibles hay en este juego, basta con calcular el número de subconjuntos que se pueden formar con 6 de esos 49 elementos
Con lo que tenemos que el número de boletos de lotería posibles será de:
C_{49, 6} = {49 \choose 6} = \frac{49!}{6! \cdot (49 - 6)!}=\frac{49!}{6! \cdot 43!}
Sin embargo, esta no es la solución a nuestro problema, la cuál vendrá dada por:
Combinaciones con repetición
Llamaremos combinaciones con repetición de m elementos tomados de n en n al número de subconjuntos que se pueden formar con n de esos m elementos pudiendo repetir alguno
CR_{m, n} = {m + n - 1\choose n} = \frac{(m + n - 1)!}{n! \cdot (m - n)!}Ejemplo de combinaciones con repetición
¿Cuántas fichas tiene el dominó?
Una ficha de dominó es un rectángulo dividido en dos pares iguales y que cada parte contiene un número de puntos escogidos dentro del conjunto \{0, 1, 2, 3, 4, 5, 6\}, dónde el 0 es representado con la ausencia de puntos
El número total de fichas de dominó coincide con el número de selecciones no ordenadas de dos elementos, repetidos o no, escogidos del conjunto \{0, 1, 2, 3, 4, 5, 6\}
Con lo que tenemos que el número total de fichas de dominó será de:
CR_{7, 2} = {7 + 2 - 1\choose 2} = \frac{(7 + 2 - 1)!}{2! \cdot (7 + 2 - 1 - 2)!} = \frac{8!}{2! \cdot 6!} =28