Elegir a k personas de un grupo de n.
Los problemas de selección de comités son la aplicación por excelencia de las combinaciones en el conteo. El concepto central es elegir un grupo de $k$ objetos (o personas) distintos de un conjunto más grande de $n$ objetos distintos, donde el orden de selección no importa. En un comité, que te elijan primero o al último da igual; lo único que importa es si eres parte del grupo o no. Esto diferencia la selección de comités de los problemas de permutaciones (como elegir un Presidente y un Vicepresidente), donde los roles específicos hacen que el orden de los elementos sí sea importante.
Estos problemas son fundamentales en la combinatoria porque introducen el concepto de "sobreconteo" y cómo corregirlo. Cuando haces una lista de los posibles grupos, si solo multiplicas las opciones (por ejemplo, $n$ opciones para el primer lugar, $n-1$ para el segundo), estás creando una lista ordenada sin querer. Para encontrar el número de comités únicos, tienes que dividir entre el número de formas en que los miembros del comité se pueden acomodar entre ellos. Esta lógica sirve como base para el Teorema del Binomio, el Triángulo de Pascal y para calcular probabilidades en espacios uniformes discretos.
En las matemáticas de olimpiada, los problemas de comités suelen traer restricciones que requieren que analices casos o que uses el conteo por complemento. Algunas variaciones comunes incluyen elegir comités de grupos de hombres y mujeres con restricciones de género, asegurar que ciertas personas específicas estén o no estén, o elegir un comité donde un miembro es nombrado presidente. Si dominas la fórmula básica de selección de comités, podrás manejar estos escenarios más complejos dividiéndolos en elecciones más simples e independientes.
La Fórmula de Combinaciones El número de formas de elegir un comité de $k$ personas de un conjunto de $n$ personas lo escribimos como $\binom{n}{k}$ (lo lees como "$n$ en $k$") o $C(n,k)$. $$ \binom{n}{k} = \frac{n!}{k!(n-k)!} $$ donde $n! = n \times (n-1) \times \dots \times 2 \times 1$.
Identidad de Simetría Elegir a $k$ personas para que estén en un comité es matemáticamente lo mismo que elegir a $n-k$ personas para que se queden fuera del comité. $$ \binom{n}{k} = \binom{n}{n-k} $$
Identidad de Pascal (Lógica de Inclusión/Exclusión) El número de formas de elegir a $k$ personas de un total de $n$ es la suma de los comités que incluyen a una persona específica $X$ y los comités que excluyen a esa persona $X$. $$ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} $$
La Identidad del "Presidente" Elegir un comité de $k$ personas y luego nombrar a una como presidente es lo mismo que elegir primero al presidente y luego a los $k-1$ miembros restantes. $$ k \binom{n}{k} = n \binom{n-1}{k-1} $$
Teorema: El número de formas de elegir un subconjunto de $k$ elementos de un conjunto de $n$ elementos distintos, donde el orden no importa, es $\frac{n!}{k!(n-k)!}$.
Demostración: La idea es obtener esta fórmula usando la Regla de la División, relacionando las combinaciones con las permutaciones.
Cuenta con orden (Permutaciones): Primero, imagina que estás eligiendo a $k$ personas de un total de $n$ y las asignas a $k$ asientos específicos y distintos (posiciones ordenadas).
El número total de arreglos ordenados es: $$ P(n, k) = n \times (n-1) \times \dots \times (n-k+1) = \frac{n!}{(n-k)!} $$
Analiza el sobreconteo: Supón que $C$ es el número de comités únicos (combinaciones) donde el orden no importa. Considera un solo comité único de $k$ personas específicas. ¿De cuántas formas puedes acomodar a estas $k$ personas en los asientos ordenados que calculaste en el Paso 1?
Puedes acomodar a $k$ personas distintas de $k!$ formas (permutaciones del subconjunto).
Relaciona las Combinaciones con las Permutaciones: Como cada comité único lo puedes ordenar de $k!$ formas para formar las permutaciones que contaste en el Paso 1, el número total de permutaciones es el número de comités multiplicado por las formas de acomodar cada comité. $$ P(n, k) = C \times k! $$
Despeja C: Sustituye la fórmula de $P(n, k)$ y despeja $C$: $$ \frac{n!}{(n-k)!} = C \times k! $$
Si divides ambos lados entre $k!$ obtienes: $$ C = \frac{n!}{k!(n-k)!} $$
Así que el número de formas de elegir el comité es $\binom{n}{k} = \frac{n!}{k!(n-k)!}$. $\square$