2.3: Combinaciones
- Page ID
- 118303
Para motivar el tema de esta sección, consideramos otra variante sobre el problema de elección de oficiales del Ejemplo 2.7. Supongamos que en lugar de elegir a los estudiantes para cargos específicos, la clase es elegir un consejo ejecutivo de cuatro estudiantes del grupo de 80 estudiantes. Cada posición en el consejo ejecutivo es igual, por lo que no habría diferencia entre que Alice ganara el “primer” escaño en el consejo ejecutivo y que ella ganara el “cuarto” escaño. En otras palabras, solo queremos elegir a cuatro de los 80 alumnos sin tener en cuenta el orden. Volveremos a esta pregunta después de introducir nuestro próximo concepto.
Dejar\(X\) ser un conjunto finito y dejar\(k\) ser un entero con\(0 \leq k \leq |X|\). Entonces un subconjunto\(k\) -elemento de también\(X\) se llama una combinación de tamaño\(k\). Cuando\(|X| = n\), se denota el número de\(X\) subconjuntos\(k\) -elemento de\(\binom{n}{k}\). Los números de la forma\(\binom{n}{k}\) se llaman coeficientes binomiales, y muchos combinatorios leen\(\binom{n}{k}\) como “\(n\)elegir”\(k\). Cuando necesitamos una versión en línea, la notación preferida es\(C(n,k)\). También, la cantidad\(C(n,k)\) se conoce como el número de combinaciones de\(n\) cosas, tomadas\(k\) a la vez.
Bob señala que con esta notación, es el número de formas en que un consejo ejecutivo de cuatro miembros puede ser elegido entre los 80 estudiantes interesados\(C(80,4)\). Sin embargo, está desconcertado acerca de cómo calcular el valor de\(C(80,4)\). Alice señala que debe ser menor que\(P(80,4)\), ya que cada consejo ejecutivo podría convertirse en\(4!\) diferentes pizarras de oficiales. Carlos está de acuerdo y dice que Alice realmente ha dado con la idea clave para encontrar una fórmula para computar\(C(n,k)\) en general.
Si\(n\) y\(k\) son enteros con\(0 \leq k \leq n\), entonces
\(\dbinom{n}{k} = C(n,k) = \frac{P(n,k)}{k!} = \frac{n!}{k!(n-k)!}\)
- Prueba
-
Si\(X\) es un conjunto\(n\) -elemento, entonces\(P(n,k)\) cuenta el número de\(X\) -permutaciones de longitud\(k\). Cada uno de los subconjuntos\(C(n,k)\)\(k\) -elemento de se\(X\) puede convertir en\(k!\) permutaciones, y esto da cuenta de cada permutación exactamente una vez. Por lo tanto,\(k!C(n,k)=P(n,k)\) y dividiendo por\(k!\) da la fórmula para el número de subconjuntos\(k\) -elementos.
Usando la Proposición 2.9, ahora podemos determinar que\(C(80,4)=1581580\) es el número de formas en que un consejo ejecutivo de cuatro miembros podría ser elegido entre los 80 estudiantes interesados.
Nuestro argumento anterior ilustra una estrategia común de conteo combinatorio. Contamos una cosa y determinamos que los objetos que queríamos contar estaban sobrecontados el mismo número de veces cada uno, así que dividimos por ese número (\(k!\)en este caso).
El siguiente resultado equivale a decir que elegir elementos para pertenecer a un conjunto (los ganadores de las elecciones del consejo ejecutivo) es lo mismo que elegir aquellos elementos a los que se va a negar la membresía (los perdedores electorales).
Para todos los enteros\(n\) y\(k\) con\(0 \leq k \leq n\),
\(\dbinom{n}{k} = \dbinom{n}{n-k}\)
Un restaurante sureño enumera 21 artículos en la categoría “vegetal” de su menú. (Como cualquier buen restaurante sureño, los macarrones con queso son una de las opciones de verduras). Venden un plato de verduras que le da al cliente cuatro vegetales diferentes del menú. Dado que no hay importancia en el pedido de las verduras se colocan en el plato, hay\(C(21,4)=5985\) diferentes formas para que un cliente ordene un plato de verduras en el restaurante.
Nuestro siguiente ejemplo introduce una correspondencia importante entre conjuntos y cadenas de bits que explotaremos repetidamente en este texto.
Dejar\(n\) ser un entero positivo y dejar\(X\) ser un conjunto\(n\) -elemento. Luego hay una correspondencia natural uno a uno entre los subconjuntos de\(X\) y las cadenas de bits de longitud\(n\). Para ser precisos, vamos\(X = \{x_1,x_2,...,x_n\}\). Entonces un subconjunto\(A \subseteq X\) corresponde a la cadena\(s\) donde\(s(i) = 1\) si y solo si\(i \in A\). Por ejemplo, si\(X = \{a,b,c,d,e,f,g,h\}\), entonces el subconjunto\(\{b,c,g\}\) corresponde a la cadena de bits\(01100010\). Hay cadenas de\(C(8,3) = 56\) bits de longitud ocho con precisamente tres 1's Pensando en esta correspondencia, ¿cuál es el número total de subconjuntos de un conjunto\(n\) -elemento?