Combinatoria es la rama de las matemáticas que estudia la enumeración, construcción y existencia de propiedades de configuraciones que satisfacen ciertas condiciones establecidas. También estudia las ordenaciones o agrupaciones de un determinado número de elementos. En este artículo se comentarán principios básicos y sencillos de esta disciplina.

Principio de adición

Teorema

Sean $A$ y $B$ dos conjuntos finitos disjuntos ( $A \cap B = \empty$ ). Entonces:

| A \cap B | = |A| + |B|

Si un suceso $A$ puede ocurrir $m$ veces distintas y otro suceso $B$ puede ocurrir de $k$ maneras distintas, y ambos sucesos no pueden ocurrir simultáneamente; entonces, el suceso $A$ o $B$ puede ocurrir de $m+k$ formas.

Por ejemplo: ¿Cuantas formas hay de vestirse con 3 camisetas y 2 polos? Hay $3+2 = 5$ formas.

Principio de la diferencia

Corolario

Sea $U$ el universo de todos los sucesos posibles ( $U = A \cup \overline{A}, \; A \cap \overline{A} = \empty$ ).

|U| = |A| + |\overline{A}| \implies |A| = |U| - |\overline{A}|

Principio de la multiplicación

Teorema

Si una tarea puede dividirse en 2 subtareas consecutivas de manera que hay $m$ formas de realizar la primera, y para cada una de ellas hay $k$ formas de realizar la segunda subtarea, entonces hay $m \times k$ formas distintas de completar la tarea.

|A \times B| = |B \times A| = |A| \\, |B|

Por ejemplo:

El número de contraseñas posibles con 4 dígitos sin que se repitan: $10 \times 9 \times 8 \times 7$ .
El número de formas de vestire con 3 pantalones y 2 camisetas: $3 \times 2 = 6$ .

Principio de biyección

Teorema

Sean $A$ y $B$ dos conjuntos finitos y la siguinte aplicación biyectiva:

f: A \longrightarrow B

Entonces, hay el mismo número de elementos en los dos conjuntos.

|A| = |B|

Principio del palomar / Dirichlet

Teorema

Si tenemos $n$ palomas (objetos) y $k$ nidales (cajas); entonces, al menos algún nidal contendendrá:

\bigg\lceil \frac{n}{k} \bigg\rceil

Selecciones de objetos

Variaciones / permutations: influye el orden.
Combinaciones / combinations: no influye el orden.

Variaciones: Selecciones ordenadas sin repetición

Sea $A = \Set{a_1, \ldots, a_n}$ un conjunto finito de $n$ elementos y $r$ un número natural ( $r \ge 0$ ) con la condición de que $r \le n$ .

Definición

Una variación de orden $r$ de los $n$ elementos es una lista o selección ordenada de $r$ elementos distintos de $A$ .

V(n, r) = \frac{n!}{(n - r)!}

Se lee variaciones de $n$ elementos de orden $r$ .

Caso particular: Permutaciones

Cuando $n = r$ :

V(r, n) = \frac{n!}{(n - r)!} = \frac{n!}{(n - n)!} = \frac{n!}{0!} = n!

Permutaciones con repetición

Las distintas ordenaciones ordenadas son permutaciones con repetición de $n$ objetos con $n_1, n_2, \ldots, n_r$ repeticiones.

Definición

Si disponemos de $r$ tipos de objetos distintos con la condición de que los objetos de un mismo tipo son iguales entre sí y diferentes de los otros tipos:

\begin{cases} n_1 \text{ objetos del tipo 1} \\\\ n_2 \text{ objetos del tipo 2} \\\\ \vdots \\\\ n_r \text{ objetos del tipo r} \\\\ \end{cases}

PR(n; \\; n_1, n2, \ldots, n_r) = \frac{n!}{n_1! \\; n_2! \\; \ldots \\; n_r!}

Donde $n = n_1 + n_2 + \ldots + n_r$ .

Caso particular: solo dos tipos:

PR(n; \\; n_1, \\; n_2) = \frac{n!}{(n - n_1)! \\; n_1!} = \binom{n}{n_1} = \binom{n}{n_2}

Variaciones ordenadas con repetición

Sea $A = \Set{a_1, \ldots, a_n}$ un conjunto finito de $n$ elementos y $r$ un número natural cualquiera.

Definición

VR(n, r) = n^r

Esto representa el número de aplicaciones de un conjunto con $r$ elementos y otro de $n$ elementos. También representa la cantidad de formas de distribuir $r$ objetos diferentes en $n$ cajas diferentes.

Combinaciones: Selecciones no ordenadas sin repetición

Sea $A = \Set{a_0, \ldots, a_n}$ un conjunto finito de $n$ elementos y $r$ un número natural $r \le n$ (no se pueden repetir).

Definición

Una combinación de orden $r$ de los $n$ elementos de $A$ es un subconjunto (no influye el orden) de $r$ elemento de $A$ .

C(n, r) = \frac{V(n, r)}{r!} = \frac{n!}{(n - r)! r!} = \binom{n}{r}

Ejemplo: cadenas de $n$ bits que tengan $r$ 0s o $n - r$ 1s: $C(n, r)$ .

Combinaciones no ordenadas con repetición

Sea $A = \Set{a_0, \ldots, a_n}$ un conjunto finito de $n$ elementos y $r$ un número natural cualquiera.

Definición

Una combinación con repetición de $n$ elementos de $A$ de orden $r$ es una selección no ordenada (conjunto) de $r$ elementos no necesariamente distintos de $A$ .

CR(n, r) = \binom{n + r - 1}{r} = \binom{n + r - 1}{n - 1}

Por ejemplo: Comprar 10 helados de 4 sabores distintos: $\Set{\text{Fresa, Nata, Chocolate, Vainilla}}$ .

Números combinatorios

\binom{n}{r} = \binom{n}{n - r}

$n$ sobre $r$ , número combinatorio, número binomial.

Resumen

Selecciones de $n$ elementos de orden $r$	Ordenadas	No ordenadas
Sin repetición	Variaciones $V(n, r) = \frac{n!}{(n - r)!}$ $r \le n$	Combinaciones $C(n, r) = \binom{n}{r}$ $r \le n$
Con repetición	Variaciones con repetición $VR(n, r) = n^r$	Combinaciones con repetición $CR(n, r) = \binom{n + r - 1}{r}$

El problema de distribución

$r$ objetos y $n$ cajas	Sin repetición	Cajas no vacías (al menos 1 en cada)	Máximo 1 objeto por caja
Objetos diferentes (importa el orden)	Número de aplicaciones $r \longrightarrow n$ $VR(n, r) = n^r$	Número de aplicaciones sobre $r \longrightarrow n$ $\sum_{k = 0}^{n} \binom{n}{k} (n - k)^r$ $r \ge n$	Número de aplicaciones inyecticas $r \longrightarrow n$ $V(n, r) = \frac{n!}{(n - r)!}$ $r \le n$
Objetos iguales (no importa el orden)	$CR(n, r) = \binom{n + r - 1}{r}$	Un elemento en cada caja, el resto sin restricciones $CR(n, r-n) = \binom{r - 1}{r - n}$ $r \ge n$	¿Cuántas cadenas de $n$ bits con $r$ 1s? $C(n, r) = \binom{n}{r}$ $r \le n$

Número de aplicaciones biyectivas: $n!$ .

Objetos iguales en cajas no vacías:

Se reparte 1 elemento a cada caja, y el resto se puede rellenar sin ninguna restricción.

Combinatoria

[date: 11-06-2023] [last modification: 12-06-2023][words: 1556] [reading time: 8min] [size: 71061 bytes]

Principio de adición

Principio de la diferencia

Principio de la multiplicación

Principio de biyección

Principio del palomar / Dirichlet

Selecciones de objetos

Variaciones: Selecciones ordenadas sin repetición

Caso particular: Permutaciones

Permutaciones con repetición

Variaciones ordenadas con repetición

Combinaciones: Selecciones no ordenadas sin repetición

Combinaciones no ordenadas con repetición

Números combinatorios

Resumen

El problema de distribución

[date: 11-06-2023] [last modification: 12-06-2023]
[words: 1556] [reading time: 8min] [size: 71061 bytes]