Análisis combinatorio

Algunos resultados útiles del análisis combinatorio

En un diagrama tipo árbol donde el $i$-ésimo nivel tiene $n_i$ ramas, entonces la cantidad de posibles combinaciones en $r$ niveles es:

$$n_1\times n_2\cdots \times n_r$$

Ejemplo

• ¿Cuántas combinaciones posibles hay con cuatro sabores de helados y tres conos distintos?

• ¿Cuántas combinaciones posibles hay con cuatro sabores de helados, tres conos distintos y diez toppings?

Posibles arreglos de un mazo de cartas con 52 cartas

Regla de la multiplicación:

$$\mathbf{\text{52!}}=80658175170943878571660636856403766975289505440883277824000000000000$$

Este número es grande.

---

Combinatoria enumerativa: contar (números grandes)

En muchos análisis de la situación que se estudia, es necesario "contar" todos los resultados elementales posibles de un experimento. Este puede ser un número muy grande.

Los principales tipos son combinaciones, permutaciones, particiones y composiciones.

---

Combinaciones

Definición

Es la selección de $k$ ítemes de una colección de $n$ elementos, donde el orden no importa.

$${}_n{\mathbf{C}}_k\equiv (\genfrac{}{}{0ex}{}{n}{k})\equiv \frac{n!}{k!(n-k)!}$$

Se lee ${}_n{\mathbf{C}}_k$ como “de $n$ escoge $k$” y$(\genfrac{}{}{0ex}{}{n}{k})$ es el coeficiente binomial.

Ejemplo

Para hacer un grupo de cinco personas de una clase de 30 alumnos hay

$${}_{30}{\mathbf{C}}_5\equiv (\genfrac{}{}{0ex}{}{30}{5})\equiv \frac{30!}{5!(30-5)!}=142506$$

combinaciones posibles.

Fuentes: MathWorld (http://mathworld.wolfram.com/Combination.html) y Wikipedia (https://en.wikipedia.org/wiki/Combination)

Permutaciones

Definición

Es el arreglo de $k$ ítemes de una colección de $n$ elementos, donde el orden sí importa.

$${}_n{\mathbf{P}}_k\equiv \frac{n!}{(n-k)!}$$

Se lee ${}_n{\mathbf{P}}_k$ como "de $n$ escoge $k$".

Ejemplo

Para hacer una junta directiva de cinco personas de una clase de 30 alumnos hay

$${}_{30}{\mathbf{P}}_5\equiv \frac{30!}{(30-5)!}=17100720$$

permutaciones posibles.

Fuentes: MathWorld (http://mathworld.wolfram.com/Permutation.html) y Wikipedia (https://en.wikipedia.org/wiki/Permutation)

Particiones

Definición

Sean $r_1,...,r_l$, con $l$ un entero positivo, números tales que $r_1+r_2+\cdots +r_l=n$. Entonces, la cantidad de formas en las que una población de $n$ elementos puede ser particionada en $l$ sub-poblaciones donde la primera contiene $r_1$ elementos, la segunda $r_2$ y así sucesivamente, es:

$$\frac{n!}{r_1!r_2!\cdots r_l!}$$

Este coeficiente es conocido como coeficiente multinominal.

Ejemplo

Un vendedor de autos tiene 6 carros disponibles de distinto modelo cada uno y los quiere acomodar en grupos de 1, 2 y 3 carros respectivamente por un tema de espacio. ¿De cuántas formas distintas los puede acomodar?

$$n_E=\frac{6!}{1!\times 2!\times 3!}=60$$

Fuente: Stark, H., Woods, J. (2012) Probability, Statistics, and Random Processes for Engineers. Nueva Jersey: Pearson.

---

Composiciones

Definición

Una composición en análisis combinatorio es un arreglo ordenado de $k$ elementos no negativos que suman $n$. Es por tanto una partición en la que el orden sí importa.

Por ejemplo, hay ocho composiciones de 4:

$$\begin{array}{rl}4& =4\\ \\ & =3+1\\ \\ & =2+2\\ \\ & =2+1+1\\ \\ & =1+3\\ \\ & =1+2+1\\ \\ & =1+1+2\\ \\ & =1+1+1+1\end{array}$$

Un entero positivo $n$ tiene $2^{(n-1)}$ composiciones.

El número de composiciones de $n$ en $k$ partes (donde 0 no es una parte) está dado por:

$$\begin{array}{rl}{\mathbf{C}}_k(n)& =(\genfrac{}{}{0ex}{}{n-1}{k-1})\\ \\ & =\frac{(n-1)!}{(k-1)!(n-k)!}\end{array}$$

Fuente: Stover, Christopher y Weisstein, Eric W. "Composition". De MathWorld -- A Wolfram Web Resource. http://mathworld.wolfram.com/Composition.html

---

Otros ejemplos

• Una “mano de poker” consiste en cinco cartas escogidas de un mazo de 52 cartas, ¿cuántas posibilidades hay?

$${}_{52}{\mathbf{C}}_5\equiv (\genfrac{}{}{0ex}{}{52}{5})\equiv \frac{52!}{5!(52-5)!}=2598960$$

• Las placas de carros en el país tienen tres consonantes y tres números, ¿cuántas placas son posibles? ¿Se agotarán pronto?

$$21\times 21\times 21\times 10\times 10\times 10=9261000$$

---

Videos y referencias en internet

Cuando sea posible, las presentaciones tendrán referencias a videos o artículos útiles... o al menos entretenidos.

• ▶ How secure is 256 bit security?, 3Blue1Brown: https://youtu.be/S9JGmA5_unY
• ▶ Mathematical Impressions: Change Ringing, SimonsFoundation: https://youtu.be/3lyDCUKsWZs

Muchas veces los videos serán en inglés, quizá con subtítulos. Aunque espero que no sea un inconveniente, ojalá sirva de gentil recordatorio de la importancia de seguir aprendiendo inglés.