El árbol de probabilidad que se muestra en la figura 9.5.1. Inicio Paso 1: Escriba las 2-combinaciones de {0, 1, 2, 3}. Paso 2: Ordene las 2-combin...

El árbol de probabilidad que se muestra en la figura 9.5.1. Inicio Paso 1: Escriba las 2-combinaciones de {0, 1, 2, 3}. Paso 2: Ordene las 2-combinaciones para obtener 2-permutaciones {0, 1} {0, 2} {0, 3} {1, 2} {1, 3} {2, 3} 01 10 02 20 03 30 12 21 13 31 23 32 Figura 9.5.1 Relación entre permutaciones y combinaciones 568 Capítulo 9 Conteo y probabilidad El número de formas de realizar el paso 1 es 4 2 , es igual al número de subconjuntos de tamaño 2 que se puede elegir de {0, 1, 2, 3}. El número de formas de realizar el paso 2 es 2!, el número de formas para ordenar los elementos en un subconjunto de tamaño 2. Ya que el número de formas de realizar todo el proceso es el número de 2-permutaciones del conjunto {0, 1, 2, 3}, que es igual a P(4, 2), por lo que se deduce de la regla de la multiplicación que P 4 2 4 2 2 P 4 2 y 4 2 .Esta es una ecuación que relaciona a Resolviendo la ecuación para 4 2 se obtiene ( 4 2 ) = P(4, 2) 2! Recuerde que P 4 2 4 4 ฀ 2) . Por tanto, sustituyendo se obtiene ( 4 2 ) = 4! (4 − 2)! 2! = 4! 2!(4 − 2)! = 6. El razonamiento utilizado en el ejemplo 9.5.3 se aplica también en el caso general. Para formar una r-permutación de un conjunto de n elementos, primero se elige un subconjunto de r elementos de n (hay ( n r ) formas de realizar este paso) y después se elige un ordena- miento para los r elementos (hay r! formas de realizar este paso). Por tanto el número de r-permutaciones es P(n, r) = ( n r ) ·r !. Ahora resuelva para n r para obtener la fórmula n r P n r r Ya que P(n, r) = n! (n−r)! , sustituyendo se obtiene ( n r ) = n! (n − r)! r ! = n! r !(n − r)! . El resultado de este análisis se resume y amplia en el teorema 9.5.1. Teorema 9.5.1 El número de subconjuntos de tamaño r (o r-combinaciones) que se pueden elegir entre un conjunto de n elementos, n r , está dado por la fórmula n r P n r r primera versión o, de forma equivalente, n r n r n ฀ r segunda versión donde n y r son enteros no negativos con r n. Observe que el análisis que se presenta antes del teorema demuestra el teorema en todos los casos donde n y r son positivos. Si r es cero y n es cualquier entero no negativo, 9.5 Conteo de subconjuntos de un conjunto: combinaciones 569 entonces n 0 es el número de subconjuntos de tamaño cero de un conjunto con n elemen- tos. Pero se sabe de la sección 6.2 que sólo hay un conjunto que no tiene elementos. En consecuencia, n 0 1. También n! 0!(n − 0)! = n! 1 ·n! = 1 ya que por definición 0! 1. (Recuerde que dijimos que la definición ¡resultaría conve- niente!) Por tanto, la fórmula ( n 0 ) = n! 0!(n − 0)! vale para todos los enteros n 0 y así el teorema es cierto para todos los enteros no nega- tivos n y r con r n. Ejemplo 9.5.4 Cálculo del número de equipos Considere nuevamente el problema de la elección de cinco miembros de un grupo de doce para trabajar como un equipo en un proyecto especial. ¿Cuántos equipos de cinco personas distintos se pueden elegir? Solución El número de distintos equipos de cinco personas es el mismo que el número de subconjuntos de tamaño 5 (o 5-combinaciones) que se pueden seleccionar del conjunto de los doce. Este número es ( 12 5 ) . Por el teorema 9.5.1, ( 12 5 ) = 12! 5!(12 − 5)! = 12 ·11 ·10 ·9 ·8 ·7! (5 ·4 ·3 ·2 ·1) ·7! = 11 ·9 ·8 = 792. Así hay 792 equipos distintos de cinco personas. La fórmula para el número de r-combinaciones de un conjunto se puede aplicar a una amplia variedad de situaciones. Algunas de estas se ilustran en los siguientes ejemplos. Ejemplo 9.5.5 Equipos que contienen ambos o ninguno Suponga que dos miembros del grupo de los doce insisten en trabajar en pareja: cualquier equipo debe contener a los dos o a ninguno. ¿Cuántos equipos de cinco personas se pueden formar? Solución Llame a los dos miembros del grupo que insisten en trabajar como un par A y B. Entonces cualquier equipo formado debe contener tanto a A como a B o ni A ni B. El con- junto de todos los equipos posibles puede dividirse en dos subconjuntos como se muestra en la figura 9.5.2 de la página siguiente. Ya que un equipo que contiene tanto a A, como B, contiene exactamente otras tres de las restantes diez personas del grupo, hay tantos de esos equipos como subconjuntos de tres personas se pueden elegir de las diez restantes. Por el teorema 9.5.1, este número es ( 10 3 ) = 10! 3! ·7! = 3 4 10 · 9 · 8 ·7! 3 · 2 ·1·7! = 120. Ya que un equipo que no contiene a A ni a B contiene exactamente cinco personas de las diez restantes, hay tantos de esos equipos como subconjuntos de cinco personas que se pueden elegir de las diez restantes. Por el teorema 9.5.1, este número es ( 10 5 ) = 10! 5! ·5! = 2 2 10 ·9 · 8 · 7 · 6 ·5! 5 · 4 ·3 · 2 ·1·5! = 252. ctamente otras cuatro personas de las diez restantes en el grupo, por el teorema 9.5.1 el número de esos equipos es ( 10 4 ) = 10! 4!(10 − 4)! = 3 10 · 9 · 8 ·7 · 6! 4 · 3 · 2 ·1· 6! = 210. Similarmente, hay (10 4 ) = 210 equipos que contienen a D pero no a C. Por último, por el mismo razonamiento como en el ejemplo 9.5.5, hay 252 equipos que no contienen a C ni a D. Así, por la regla de adición, número de equipos que no contienen ni a C ni a D 210 210 252 672 Este razonamiento se resume en la figura 9.5.3. Todos los posibles equipos de cinco personas que no contienen a ambos C y D, equipos que contienen a C pero no a D Hay 10 4( ) = 210 de éstos. equipos que contienen a D pero no a C Hay 10 4( ) = 210 de éstos. equipos que ni contienen a C ni a D Hay 10 5( ) = 252 de éstos. Por lo que el número de equipos que no contienen a ambos C y D es 210 + 210 + 252 = 672. Figura 9.5.3 La solución alternativa por la regla de la diferencia se basa en la siguiente observación: El conjunto de todos los equipos de cinco personas que no contienen a ambos C y D es igual a la diferencia entre el conjunto de todos los equipos de cinco personas y el conjunto de todos los equipos que contienen ambos C y D. Por el ejemplo 9.5.4 el número total de cinco personas es ( 12 5 ) = 792. Así, por la regla de la diferencia, número de equipos que no contienen a ambos C y D número total de equipos de cinco ฀ número de equipos que contienen ambos a C y D 12 5 792฀ 120 672 Este razonamiento se resume en la figura 9.5.4. 792 – 120 = 672 de éstos. Todos los equipos de cinco personas equipos que no contienen ambos a C y D equipos que contienen ambos a C y D Por lo que hay Hay 12 5( ) = 792 de éstos. Hay 10 3( ) = 120 de éstos. Figura 9.5.4 Antes de comenzar el ejemplo siguiente, haremos una observación acerca de las frases al menos y a lo más en este orden: La frase al menos n significa “n o más”. La frase a lo más n significa “n o menos”. Por ejemplo, si un conjunto consta de tres elementos y elige al menos dos, seleccionará dos o tres; Si elige a lo más dos, selecciona ninguno, o uno o dos. 572 Capítulo 9 Conteo y probabilidad Ejemplo 9.5.7 Equipos con miembros de dos tipos Supongamos que el grupo de doce consta de cinco