(Trabajo de titulación asesorado por la Dra. Diana Avella Alaminos)
Introducción
En la presente nota veremos el concepto de combinaciones, para ello consideraremos un conjunto finito y a todos sus subconjuntos con un número determinado de elementos. Este concepto es ampliamente usado en matemáticas, particularmente en probabilidad, y está relacionado también íntimamente en la forma de elevar un binomio a un exponente natural.
Definición
Sean $n,m\in \mathbb N$ con $m\leq n$, $A$ un conjunto con $n$ elementos. Las combinaciones de los elementos de $A$ tomados de $m$ en $m$ son los subconjuntos de $A$ de $m$ elementos. Denotamos por $\binom{n}{m}$ al número de combinaciones de un conjunto de $n$ elementos tomados de $m$ en $m$.
Ejemplo
Considera el conjunto $A=\set{a,b,c,d}$, con $a$, $b$, $c$ y $d$ elementos distintos. Obtengamos todas las combinaciones de $A$.
Sólo hay una combinación de los elementos de $A$ tomados de $0$ en $0$, el conjunto vacío, y sólo una combinación de los elementos de $A$ tomados de $4$ en $4$, el conjunto $A$, entonces
$\binom{4}{0}= \binom{4}{4}=1. $
Las combinaciones de los elementos de $A$ tomados de $1$ en $1$ son: $\set{a}$, $\set{b}$, $\set{c}$, $\set{d}$.
Las combinaciones de los elementos de $A$ tomados de $2$ en $2$ son $\set{a,b}$, $\set{a,c}$, $\set{a,d}$, $\set{b,c}$, $\set{b,d}$, $\set{c,d}$. Así
$\binom{4}{2}=6.$
Las combinaciones de los elementos de $A$ tomados de $3$ en $3$ son $\set{a,b,c}$, $\set{a,b,d}$, $\set{a,c,d}$, $\set{b,c,d}$, por lo que
$\binom{4}{3}=4.$
Observación 1
Para todo natural $n$ se tiene que $\binom{n}{0}= \binom{n}{n}=1.$
Demostración.
Sea $A$ un conjunto finito con $n$ elementos. El único subconjunto de $A$ con cero elementos es el vacío, entonces $\binom{n}{0}=1,$ y el único subconjunto de $A$ con $n$ elementos es $A$, entonces $\binom{n}{n}=1.$
Observación 2
Para todo natural $n\geq 1$ se tiene que $\binom{n}{1}= \binom{n}{n-1}=n.$
Demostración.
Dado $A=\{a_1,\dots ,a_n\}$ un conjunto finito con $n$ elementos los subconjuntos de $A$ con un elemento son $\{a_i\}$ con $i\in\{1,\dots ,n\}$ que son todos distintos entre sí. Entonces $\binom{n}{1}=n.$.
Considera que para obtener subconjuntos de $n-1$ elementos de $A$, debemos tomar todos los elementos de $A$ salvo uno, y como $A$ tiene $n$ elementos entonces eso se puede hacer de $n$ formas distintas, una por cada elemento de $A$ que dejemos fuera del subconjunto. Entonces los subconjuntos de $A$ con $n-1$ elementos son $A\setminus \{a_i\}$ con $i\in\{1,\dots ,n\}$ que son todos distintos entre sí. Así, $\binom{n}{n-1}=n.$.
Teorema
Sean $n,m\in \mathbb N^+$, $m\leq n$, entonces $\binom{n}{m}P_m=O_{m}^{n}$.
Demostración
Sean $A$ un conjunto con $n$ elementos, $\mathscr O$ el conjunto de ordenaciones de $A$ tomados de $m$ en $m$, $\mathscr C$ el conjunto de las combinaciones de los elementos de $A$ tomados de $m$ en $m$.
Definimos $\varphi: \mathscr O\to \mathscr C $ como:
$\varphi(f)=\varphi\bigg(\begin{pmatrix}1 & \dotsi & m\\ f(1) & \dotsi & f(m)\end{pmatrix}\bigg)=\set{f(1),\dotsc,f(m)}$.
Veamos que $\varphi$ es suprayectiva. Si $c\in \mathscr C$, entonces $c$ es un subconjunto de $A$ con $m$ elementos, es decir $c=\set{b_1,\dotsc,b_m}$, con $ b_1,\dotsc,b_m\in A$ distintos. Así:
$f=\begin{pmatrix}1 & \dotsi & m\\ b_1 & \dotsi & b_m\end{pmatrix}\in \mathscr O$.
y entonces:
$\varphi(f)=\varphi\bigg(\begin{pmatrix}1 & \dotsi & m\\ b_1 & \dotsi & b_m\end{pmatrix}\bigg)=\set{b_1,\dotsc,b_m}$.
Por lo tanto $\varphi$ es suprayectiva.
Sean $C_1,\dotsc,C_k$ los distintos subconjuntos de $A$ con $m$ elementos, donde $k=\binom{n}{m}$. Para cada $i\in\set{1,\dotsc,k}$ consideremos:
$O_i=\set{f\in \mathscr O\mid \varphi(f)=C_i}$
$\mathscr O$ es la unión disjunta de $O_1,\dotsc, O_k$ y entonces, por ser disjuntos y por el principio de la suma tenemos que:
$\#\mathscr O=\#(O_1\cup\dotsc,\cup O_k)=\#O_1+\dotsc+\#O_k.$
Pero si $f=\begin{pmatrix}1 & \dotsi & m\\ f(1) & \dotsi & f(m)\end{pmatrix}\in \mathscr O$, es tal que $\varphi(f)=C_1$, entonces las funciones de $O_1$ se obtendrán colocando en el segundo renglón del arreglo que describe la función, las distintas permutaciones de $\set{f(1),\dotsc,f(m)}$ que son $P_m$, y así:
$\#O_1=P_m.$
Y análogamente $\#O_i=P_m\,\,\, \,\,\, \forall i\in\set{1,\dotsc,k}.$
Por lo tanto:
$\#\mathscr O=\#O_1+\dotsc+\#O_k$, es decir, sumar $k$ veces el número $P_m$, en consecuencia:
$\#\mathscr O= k P_m$,
y como $k=\binom{n}{m}$, entonces:
$\#\mathscr O= \binom{n}{m} P_m.$
Observa que $O_{n}^{m}=\#\set{f:\set{1,\dotsc, m}\to \set{a_1,\dotsc ,a_n}\mid \text{$f$ es inyectiva}}=\#\mathscr O.$
Por lo tanto $\binom{n}{m}P_m=O_{m}^{n}$ que es justamente lo que queríamos probar.
$\square$
Corolario
Sean $n,m\in \mathbb N^+$, $m\leq n$, entonces $\binom{n}{m}=\frac{ n! }{m!(n-m)!}$.
Demostración
Por el teorema anterior sabemos que $\binom{n}{m}=\frac{ O_{n}^{m} }{P_m}$, y por lo que vimos en las entradas previas tenemos que:
$\frac{ O_{n}^{m} }{P_m}=\frac{n(n-1)\dotsc(n-m+1)}{m!}$,
entonces $\binom{n}{m}=\frac{n(n-1)\dotsc(n-m+1)}{m!}$
Multiplicando arriba y abajo por $(n-m)!$ tenemos que:
$\binom{n}{m}= \frac{n(n-1)\dotsc(n-m+1)(n-m)!}{m!(n-m)!}$
$\phantom{\binom{n}{m}}= \frac{n(n-1)\dotsc(n-m+1)(n-m)\dotsc2\cdot1}{m!(n-m)!} $
$\phantom{\binom{n}{m}}=\frac{n!}{m!(n-m)!}.$
$\square$
Tarea Moral
1. ¿Cuántas diagonales se pueden trazar en un polígono regular de $n$ lados?
2. Un club de voleibol tiene $12$ jugadoras, una de ellas es la capitana María. ¿Cuántos equipos diferentes de $6$ jugadoras se pueden formar, sabiendo que en todos ellos siempre estará la capitana María.
3. Revisa el siguiente video (puedes poner subtítulos en español).
Más adelante
En la siguiente nota usaremos estos resultados para obtener el triángulo de Pascal y para probar la fórmula del binomio de Newton.
Enlaces relacionados.
Nota anterior. Nota 22. Conteo. Ordenaciones.
Nota siguiente. Nota 24. El triángulo de Pascal y el binomio de Newton.