22.2: Conceptos básicos
- Page ID
- 118443
un subconjunto finito de un conjunto dado
el número de combinaciones de tamaño\(k\) tomadas de un conjunto de tamaños\(n\)
opciones alternativas de notación para\(C(n, k)\)
la función\((n,k) \mapsto C(n, k)\)
¿Cuáles son el dominio y el codominio de la función choose?
Las permutaciones y combinaciones son diferentes. Una permutación es una bijección de un conjunto a sí mismo. Dado un orden fijo elegido de los elementos del conjunto en una lista (considerados como entradas), una permutación es esencialmente una reordenación de los elementos del conjunto en una segunda lista, para alinear las salidas con entradas. Entonces el orden importa en una permutación. Por otro lado, una combinación es solo un conjunto, y el orden no importa en un conjunto, solo importa la membresía. Es decir, dos listados de algunos de los elementos de un conjunto son la misma combinación si se listan todos los mismos elementos, independientemente del orden de los elementos en las dos listas. Entonces el orden no importa en una combinación.
Tenemos
\ comenzar {ecuación*} C (n, k) =\ dfrac {P (n, k)} {k!} =\ dfrac {n!} {k! (n-k)!} \ texto {.} \ end {ecuación*}
- Comprobante.
-
Supongamos\(\vert A \vert = n\text{.}\) Usando la solución al Ejemplo Trabajado 22.1.1 como modelo para nuestra prueba, observamos que cada lista ordenada de\(k\) elementos tomada de\(A\) define una combinación de\(A\text{,}\) pero diferentes ordenamientos de los mismos\(k\) elementos producen la misma combinación. Definir dos permutaciones para que sean “equivalentes” si son ordenamientos de los mismos elementos, de manera que las permutaciones equivalentes se asocian a la misma combinación. Dado que hay\(k!\) elementos en cada clase de equivalencia de permutaciones, podemos aplicar la Regla de División para obtener
\ begin {alinear*} C (n, k) & =\ #\ {\ text {combinaciones}\}\\ & =\ dfrac {\ #\ {\ text {permutaciones}\}} {\ #\ {\ text {permutaciones equivalentes en cada clase}\}}\\ & =\ dfrac {P (n, k)} {k!} \ texto {.} \ end {align*}
Finalmente, para obtener la fórmula más a la derecha en el enunciado del teorema, solo necesitamos combinar la fórmula anterior relativa\(C(n, k)\) y\(P(n, k)\) con la fórmula para\(P(n, k)\) del Teorema 21.4.1.
También contamos con\(C(n, n-k) = C(n, k)\text{.}\)
- Comprobante.
-
Calcular
\ comenzar {ecuación*} C (n, n-k) =\ dfrac {n!} {(n-k)! (n- (n-k))!} =\ dfrac {n!} {(n-k)! k!} = C (n, k)\ texto {.} \ end {ecuación*}
Interpreta este último corolario de la siguiente manera: a partir de un conjunto de\(n\) objetos, elegir incluir\(k\) elementos en una combinación equivale a elegir\(n-k\) objetos a rechazar.
¿Cuántas combinaciones de helados de doble cucharada son posibles si la heladería local presenta treinta y un sabores diferentes? (Nota: Solo las combinaciones de sabores son relevantes, no qué sabor va primero en el cono).
Solución
De treinta y un sabores, hay
\ comenzar {ecuación*} C (31, 2) =\ dfrac {31!} {2! ¡29!} =\ dfrac {31\ cdot 30} {2} = 31\ cdot 15 = 465\ end {equation*}
posibilidades para conos de doble cucharada con dos sabores distintos. Sin embargo, hay\(31\) posibilidades adicionales para conos de doble pala con dos bolas del mismo sabor. Entonces la respuesta es
\ begin {ecuación*} 465 + 31 = 496\ texto {.} \ end {ecuación*}
¿Cuántos patrones de color diferentes podemos lograr colocando tres botellas rojas y cinco botellas azules en una repisa? (Supongamos que las botellas son indistinguibles excepto por el color.)
Solución
Existen\(8\) posibles posiciones en las que colocar una botella. Para crear un patrón de color arbitrario, podemos elegir\(3\) las posiciones a llenar con botellas rojas, luego colocar el azul en las posiciones restantes. Entonces la respuesta es
\ begin {ecuación*} C (8, 3) =\ dfrac {8!} {3! ¡5!} = 56\ texto {.} \ end {ecuación*}
Compare la solución anterior para Ejemplo Trabajado\(\PageIndex{2}\) con la solución para el problema idéntico en Ejemplo Trabajado 21.3.4.
¿Cuántas formas hay de elegir un equipo de cinco personas de un grupo de seis estudiantes de primer año y cuatro estudiantes de último año si el equipo debe tener tres primeros años y dos adultos mayores?
Solución
Elija los adultos mayores para equipo, luego los primeros años (o viceversa). La aplicación de la Regla de Multiplicación a estas tareas independientes y consecutivas da respuesta
\ begin {ecuación*} C (4, 2)\ cdot C (6, 3) =\ izquierda (\ dfrac {4!} {2! ¡2!} \ derecha)\ izquierda (\ dfrac {6!} {3! ¡3!} \ derecha) = 120\ texto {.} \ end {ecuación*}
¿Cuántas formas hay de elegir tres equipos de cuatro miembros cada uno de un grupo de veinte personas, donde ninguna persona puede estar en más de un equipo?
Solución
Solución. 1
Elige el primer equipo (\(C(20, 4)\)caminos), luego el segundo equipo (\(C(16, 4)\)caminos), luego el tercer equipo (\(C(12, 4)\)caminos). Al aplicar la Regla de Multiplicación se obtiene un total de
\ comenzar {ecuación*} C (20, 4)\ cdot C (16, 4)\ cdot C (12, 4) =\ izquierda (\ dfrac {20!} {4! \,\ cancel {16!}} \ derecha)\ izquierda (\ dfrac {\ cancel {16!}} {4! \,\ bcancelar {12!}} \ derecha)\ izquierda (\ dfrac {\ bcancel {12!}} {4! \, ¡8!} \ derecha) =\ dfrac {20!} {8! \, (¡4!) ^3}. \ end {ecuación*} equipos
posibles. Sin embargo, la forma en que hemos construido nuestros equipos ha impuesto un orden a la colección de equipos (primer, segundo y tercer equipo), cuando no hay razón para asumir tal estructura. Dada una colección de equipos, reordenar a los propios equipos (no a las personas dentro de cada equipo) produce una colección equivalente de equipos por membresía. Como hay\(3!\) formas de reordenar a los tres equipos, aplicar la Regla de División nos da una respuesta final de
\ comenzar {ecuación*}\ dfrac {20!} {3! \, ¡8! \, (¡4!) ^3}\ texto {.} \ end {ecuación*}
Solución. 2
Inicialmente elegir a las doce personas que conformarán los tres equipos, pero sin asignar aún a nadie a un equipo en particular (\(C(20, 12)\)vías). Después, de este reducido grupo de candidatos, elige el primer equipo (\(C(12, 4)\)caminos) y el segundo equipo (\(C(8, 4)\)vías). El tercer equipo consistirá ahora en las cuatro personas restantes de las doce elegidas inicialmente. La Regla de Multiplicación da un total preliminar de
\ comenzar {ecuación*} C (20, 12)\ cdot C (12, 4)\ cdot C (8, 4) =\ izquierda (\ dfrac {20!} {\ cancel {12!} \, ¡8!} \ derecha)\ izquierda (\ dfrac {\ cancel {12!}} {4! \,\ bcancelar {8!}} \ derecha)\ izquierda (\ dfrac {\ bcancel {8!}} {4! \, 4!} \ derecha) =\ dfrac {20!} {8! \, (¡4!) ^3}. \ end {equation*}
Pero como en la primera solución anterior, tenemos que dar cuenta del hecho de que hemos clasificado artificialmente a los equipos como primero, segundo y tercero. Aplicar la Regla de División nos da una respuesta final de
\ comenzar {ecuación*}\ dfrac {20!} {3! \, ¡8! \, (¡4!) ^3}. \ end {ecuación*}