(Trabajo de titulación asesorado por la Dra. Diana Avella Alaminos)

Introducción

En la presente nota veremos el concepto de combinaciones, que considera todos los subconjuntos de un tamaño dado de un conjunto finito, esta idea es ampliamente usada en matemáticas, particularmente en probabilidad, y relacionada también íntimamente en cómo elevar un binomio a un exponente natural.

Demos formalmente la definición de combinaciones.

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

$\binom{n}{0}= \binom{n}{n}=1.$

Observación 2

$\binom{n}{1}= \binom{n}{n-1}=n.$

Considera que para obtener todos los subconjuntos de $n-1$ elementos de un conjunto $A$ con $n$ elementos, 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. Por lo tanto existen $n$ subconjuntos de $A$ de $n-1$ elementos.

Teorema

Sean $n,m\in \mathbb N^+$, $m\leq n$, entonces $\binom{n}{m}P_m=O_{m}^{n}$.

Demostración

Sea $\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}$.

Y 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 la suma de $P_m$ $k$ veces, 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 por lo que vimos en las entradas previas tenemos que:

$\binom{n}{m}=\frac{ O_{n}^{m} }{P_m}=\frac{n(n-1)\dotsc(n-m+1)}{m!}$.

Multiplicando arriba y abajo por $(n-m)!$ tenemos que:

$= \frac{n(n-1)\dotsc(n-m+1)(n-m)!}{m!(n-m)!}$

$= \frac{n(n-1)\dotsc(n-m+1)(n-m)\dotsc2\cdot1}{m!(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 Voleyball 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. Encuentra a qué es igual la expresion \[\sum_{k=0}\binom{n}{k}\] e interpreta tu respuesta en términos de subconjuntos.

4. Revisa el siguiente video.

Mas adelante

En la siguiente nota usaremos estos resultados para obtener el triángulo de Pascal, y probar la fórmula del binomio de Newton.

Enlaces relacionados.

Página principal del curso.

Nota anterior. Nota 22. Conteo. Ordenaciones.

Nota siguiente. Nota 24. El triángulo de Pascal y el binomio de Newton.