23.3: Aplicaciones
- Page ID
- 118340
Si\(vert A \vert = n\text{,}\) entonces el número de formas de\(A\) dividir en\(m\) subconjuntos disjuntos\(A_1, A_2, \ldots, A_m\text{,}\) con cada subconjunto de tamaño predeterminado\(\vert A_j \vert = i_j\text{,}\) es
\ begin {ecuación*}\ binom {n} {i_1, i_2,\ ldots, i_m}\ texto {.} \ end {ecuación*}
- Idea de Prueba.
-
Hay\(C^n_{i_1}\) posibilidades para\(A_1\text{.}\) Después de elegir\(A_1\text{,}\) hay\(C^{n - i_1}_{i_2}\) posibilidades para\(A_2\text{.}\) Después de elegir\(A_2\text{,}\) hay\(C^{n - i_1 - i_2}_{i_3}\) posibilidades para\(A_2\text{.}\) Continuar de esta manera, todo el camino para\(A_m\text{,}\) luego multiplicar toda la fórmula de combinación expresiones juntas.
- Idea de Prueba Alternativa.
-
Volviendo a los principios básicos de conteo, podemos abordar esto de la misma manera que se nos ocurrió la fórmula factorial para la función de elegir. Elegir una permutación de\(A\) (\(n!\)formas) nos da una instancia de la partición deseada de\(A\) estableciendo\(A_1\) que sea el subconjunto que consiste en los primeros\(i_1\) objetos de la permutación, luego configurando\(A_2\) que sea el subconjunto que consiste en los siguientes\(i_2\) objetos en el permutación, y así sucesivamente. Sin embargo, el orden de los elementos dentro de tal subconjunto\(A_j\) no importa, y obtendríamos la misma partición si tomáramos nuestra permutación de\(A\) y nuevamente permutamos los “clusters” correspondientes a cada subconjunto\(A_j\text{.}\) ya que hay\(i_j!\) formas de permutar subconjunto\(A_j\text{,}\) nosotros deben dividirse\(n!\) por cada una de las factoriales\(i_j!\text{.}\)
En el teorema anterior, ¡\(A_1, A_2, \ldots, A_m\)importa el orden!
Supongamos que\(x_1, x_2, \ldots, x_m\) son letras distintas en\(i_1 + i_2 + \cdots + i_m = n\text{,}\) el alfabeto\(\Sigma\text{.}\) Para el número\(\Sigma ^{\ast}\) de palabras en de longitud\(n\) que consisten exactamente en\(i_1\)\(x_1\)'s,\(i_2\)\(x_2\)'s,\(\ldots\text{,}\) y\(i_m\)\(x_m\)'s es el coeficiente multinomial
\ begin {ecuación*}\ binom {n} {i_1, i_2,\ ldots, i_m}\ texto {.} \ end {ecuación*}
- Idea de Prueba.
-
Si vemos cada letra\(x_i\) como una variable y cada palabra compuesta por las letras\(x_1,\ldots,x_m\) como producto de estas variables, entonces cada una de las palabras que queremos contar nos da una forma de lograr un término de\(x_1^{i_1} \cdots x_m^{i_m}\) en la expansión de\((x_1 + \cdots + x_m)^n\text{.}\) El número de tales formas es el coeficiente multinomial.
¿Cuántos enteros\(9\) de dígitos diferentes podemos formar a partir de tres\(3\) s, cuatro\(6\) s y dos\(9\) s?
Solución
El número de números enteros de la composición de dígitos deseada es el coeficiente multinomial
\ begin {ecuación*}\ binom {9} {3,4,2} =\ dfrac {9!} {3! ¡4! ¡2!} =\ dfrac {9\ cdot 8\ cdot 7\ cdot 6\ cdot 5} {3\ cdot 2\ cdot 2} = 9\ cdot 4\ cdot 7\ cdot 5 = 1,260\ texto {.} \ end {ecuación*}