Fundamentos en combinatoria

Esta asignatura va de contar, y por tanto: lo primero que hay que controlar es la combinatoria. Como matemático, me parece una falta de respeto andar por aquí buscando una buena tabla de fórmulas de combinatoria. De ser el caso, seguro que en Google Imágenes encuentras lo que buscas.

Para contar de manera genérica, se trabajan dos reglas fundamentales en cualquier contexto:

(Regla de la suma) Siendo $A,B$ conjuntos finitos disjuntos, entonces:

$$\mathrm{card}(A\cup B) = \mathrm{card} (A) + \mathrm{card}(B)$$

Es decir: Si dos procesos independientes se vinculan, el total de formas de llevar a cabo uno u otro es la suma de formas de llevar a cabo cada uno por separado.

(Regla del producto) Para cualesquiera $A,B$ conjuntos finitos:

$$\mathrm{card}(A\times B) = \mathrm{card} (A) \cdot \mathrm{card}(B)$$

Esto es: Dado un proceso que se puede hacer de $n$ formas, y otro distinto que presenta $m$ formas de ejecución; el total de formas para ejecutar ambos procesos simultáneamente es $n\cdot m$.

Teniendo las anteriores reglas claras, podemos empezar a deducir algunas de las conocidas expresiones en combinatoria. Queremos contar el cardinal de un conjunto de posibles resultados en una experiencia o evento. En dicho evento se tienen $n$ elementos en juego y se seleccionan $r$ estados.

Si el evento considera distintos dos resultados por el orden de combinación de los factores (es decir: importa el orden), y se pueden repetir dichos factores, entonces cada estado de los $r$ a decidir tiene $n$ posibilidades distintas. Aplicando la regla del producto, hay un total de $n^r$ elementos en el conjunto. Este numerito se conoce como variaciones con repetición de $n$ elementos tomados de $r$ en $r$.

Si el evento sigue considerando el orden, pero no se permite la repetición, entonces podemos suponer un orden cualquiera de los $r$ estados (¿Por qué?). En ese caso, el primer estado tiene disponible $n$ posibilidades, el segundo tendrá $n-1$, y así hasta llegar al estado $r$ con $n-r+1$ posibilidades. Aplicando la regla del producto, resulta un total de $n(n-1)\dotsb (n-r+1)$ elementos del conjunto. Hemos trabajado variaciones de $n$ elementos tomados de $r$ en $r$.

(*) Formas de ordenar un conjunto de $r$ elementos: hablamos precisamente de variaciones de $r$ elementos tomados de $r$ en $r$ (suponemos que los elementos son todos distintos). Como tal, hay $r\cdot (r-1)\dotsb 2\cdot 1 = r!$ formas.

Supongamos ahora que el evento no considera orden y tampoco se permite la repetición de elementos. En particular, el cardinal del conjunto será el del apartado anterior dividido por la cantidad de elecciones equivalentes (no hay orden) en los estados. O lo que es lo mismo: restar por el número de formas de ordenar los elementos seleccionados: $r!$.

$$\frac{n(n-1) \dotsb (n-r+1)}{r!} = \frac{n!}{r! (n-r)!} =: \binom{n}{r}$$

El anterior coeficiente se conoce como combinaciones de $n$ elementos tomados de $r$ en $r$.

Finalmente, si no hay orden pero sí se permite la repetición en el evento, podemos pensar en el conjunto como soluciones enteras positivas a la ecuación: $$x_1 + \dotsb + x_r = n \quad , x_i \in \mathbb{N}$$ , donde asignar $x_1 = 1, x_2 = 2$ es distinto de $x_1=2, x_2=1$. En particular, lo que se suele hacer aquí es pensar en barritas. Por ejemplo, buscar soluciones a la ecuación: $$x_1 + x_2 + x_3 = 5 \quad , x_i \in \mathbb{N}$$ , es equivalente a, en un tablero horizontal de $5+3-1$ slots, hacer dos cortes y quedarnos con los cachitos que delimitan. Gráficamente:

Por tanto, si tenemos $x_1 +...+ x_r = n$, las soluciones enteras positivas de esta ecuación las contamos ordenando $r-1$ líneas en un conjunto de $n+r-1$ posibles cortes. Ya que dichos cortes se reparten sin importar el orden y sin permitir la repetición de posiciones, hay por tanto: $\binom{n+r-1}{r-1} = \binom{n+r-1}{n}$ combinaciones con repeteción.

EJERCICIOS PROPUESTOS

1. (Permutaciones con repetición) Deducir que el número de formas de permutar (ordenar) los elementos de un conjunto clasificado en $i_1$ del tipo $1$, $i_2$ del tipo $2$,..., $i_n$ del tipo $n$; es: $$PR_{i_1 + \dotsb + i_n} ^{i_1 \dotsb i_n} = \frac{(i_1 + \dotsb + i_n)!}{i_1 ! \dotsb i_n !}$$
2. Tienes una colección de 10 corbatas para usar los próximos 5 días. ¿Cuántos patrones de corbatas distintos pueden tener lugar en esos 5 días? ¿Y si no quieres repetir corbata en los cinco días?. Te flipan dos corbatas que tienes y quieres usarlas sí o sí: ¿Cuántos patrones son viables en este caso?.
3. El alfabeto español tiene 27 letras (al menos Google dice eso, me da pereza contar, pero explico matemática discreta :/). ¿Cuántas palabras, sin considerar acentuación ni existencia, pueden formarse con 6 letras? ¿En cuántas de ellas aparece la palabra "wei"?.
4. ¿Cuántas soluciones tiene la ecuación $$x_1 + x_2 + x_3 = 15$$ , con $x_i$ entero positivo?. ¿Y si exigimos $x_i \geq i, i=1,2,3$?.
5. Demostrar las siguientes propiedades de números combinatorios: $$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \quad ; \quad \binom{n}{k} k = n \binom{n-1}{k-1} \quad ; \quad \binom{n}{k} = \sum_{i=k}^{n} \binom{i-1}{k-1}$$ $, \forall n,k\in \mathbb{N}_{\geq 1}$. Utilizar la última igualdad para derivar el valor de la suma $1+2+\dotsb  +n$. Solución (1). Solución (2).
6. (DE EXAMEN) Una empresa dispone de diez repartidores: 5 hombres y 5 mujeres. La acción de reparto toma lugar en tres zonas distintas: $A,B,C$. Se requieren $2$ repartidores para la zona $A$, $3$ para la zona $B \,$ y $5$ para la $C$. Razonar por qué el número de asignaciones en las que hay al menos una mujer en cada zona no es: $$\binom{5}{3} 3! \cdot \binom{7}{1} \binom{6}{2} \binom{4}{4}$$ Aprenderemos a resolver este ejercicio fácilmente a partir del principio de inclusión-exclusión.
7. (DE EXAMEN) La baraja española clásica consta de 40 cartas distribuidas en cuatro palos a razón de diez cartas cada uno. Las cartas se enumeran: 1 (as),2,3,4,5,6,7, sota, caballo y rey. Se reparten cinco cartas a un jugador.
1. ¿Cuántos grupos de cinco cartas puede recibir el jugador?.
2. ¿Cuántas maneras hay de que las cartas recibidas sean todas del mismo palo?
3. ¿Cuántas maneras hay de obtener 4 ases?
4. ¿Cuántas maneras hay de obtener 4 figuras? (figuras: sotas, caballos y reyes).
5. ¿Cuántas maneras hay de obtener 3 caballos y 2 reyes?
6. ¿Cuántas maneras hay de obtener un trío y una pareja (tres de un mismo número y dos de un mismo número; distintos números)?
7. ¿Cuántas maneras hay de obtener exclusivamente un trío (tres de un mismo número, dos cartas más de distinto número entre sí y respecto al inicial)?
8. ¿Cuántas maneras hay de obtener exclusivamente dos parejas (dos parejas con dos cartas de un mismo número, tres cartas más de distinto número entre sí y respecto al primero)?
8. (DE EXAMEN) Consideramos en $\mathbb{R}^3$ movimientos de magnitud unidad en el sentido positivo. Es decir, un movimiento partiendo el punto $P$ nos llevará a un punto $P' = P + \mathbf{q}$, donde $\mathbf{q} \in \{ (1,0,0), (0,1,0), (0,0,1) \}$.
1. Determinar, para $P(x,y,z), P'(x',y',z')$ tales que $x\leq x', y\leq y', z\leq z'$; la cantidad de caminos (secuencias de movimientos) posibles de $P$ a $P'$.
2. Si es necesario retroceder en la dirección del eje $OX$ dos veces, avanzar una vez en la dirección del eje $OY$ y retroceder una vez en la dirección del eje $OZ$, calcular la cantidad de caminos factibles del punto $P(1,2,3)$ a $P'(2,6,4)$.
3. Consideramos ahora movimientos combinados. Por ejemplo, consideramos la posibilidad de ir del punto $(1,1,1)$ al $(2,2,2)$ a partir de un solo movimiento; y en general, podremos asignar el movimiento en varios ejes a la vez (aunque seguimos sin poder desplazarnos más de una unidad en cada eje por movimiento). Determinar el número de caminos de $P(0,0,0)$ a $P'(2,3,3)$.