Combinación
Una combinación es una selección de elementos de un grupo en la que el orden no importa.
Formula
C(n, r) = \dfrac{n!}{r!(n-r)!}
Definition
Una combinación es una forma de elegir elementos de un grupo cuando el orden no importa; cuenta cuántas selecciones diferentes son posibles. Una combinación de $n$ elementos tomados de $r$ en $r$ es una selección no ordenada: $C(n,r) = n!/(r!(n-r)!)$, también escrita "$n$ escoge $r$"; ya que el orden no importa, $C(n,r) = P(n,r)/r!$, dividiendo entre $r!$ para eliminar los órdenes duplicados de los mismos $r$ elementos. Formalmente, el coeficiente binomial $C(n,r)$ cuenta los subconjuntos de $r$ elementos de un conjunto de $n$ elementos; la identidad de Pascal $C(n,r) = C(n-1,r-1)+C(n-1,r)$ genera el triángulo de Pascal de forma recursiva, y el teorema del binomio establece $(x+y)^n = \sum_{r=0}^{n} C(n,r)x^r y^{n-r}$.
Example
¿De cuántas formas puedes elegir $2$ estudiantes de un grupo de $5$ para formar un comité? $C(5,2) = 10$, ya que elegir a Alice y Bob es lo mismo que elegir a Bob y Alice. Una lotería que requiere $6$ números del $1$ al $49$ tiene $C(49,6) = 13{,}983{,}816$ combinaciones posibles, siendo cada boleto una combinación sin importar el orden de selección. En la distribución binomial $B(n,p)$, la probabilidad de exactamente $r$ éxitos es $C(n,r)p^r(1-p)^{n-r}$, donde $C(n,r)$ cuenta el número de formas de organizar $r$ éxitos y $(n-r)$ fracasos en $n$ ensayos.
Key Insight
Usa combinaciones cuando el orden NO importa: elegir los ingredientes de una pizza es una combinación ya que pepperoni-y-champiñón es lo mismo que champiñón-y-pepperoni, y $C(n,r) = C(n,n-r)$, elegir $r$ elementos para incluir es el mismo conteo que elegir $n-r$ elementos para excluir, una simetría que significa $C(10,3) = C(10,7) = 120$. La identidad de Vandermonde, $C(m+n,r) = \sum_{k=0}^{r} C(m,k)C(n,r-k)$, combina subconjuntos de dos conjuntos disjuntos y tiene aplicaciones en la combinatoria, las funciones generadoras, y las funciones hipergeométricas.