1. Use la regla de multiplicación para demostrar
que el número de tales particiones es:Laboratorios Virtuales > Combinatorias > 1 2 3 [4] 5
En esta sección generalizaremos la fórmula contando lo que estudiamos en la última sección. La generalización es útil para dos muy diferentes tipos (pero evidentemente equivalentes) de problemas.
Recordar que el coeficiente binomial C(n, j) es el número de los subconjuntos de tamaño j de un conjunto S de n elementos. Note también que cuando seleccionamos un subconjunto A de tamaño j de S dividimos efectivamente S en dos subconjuntos desacoplados de tamaños j y n - j, llamados A y Ac.
Una generalización natural es dividir S en una unión de k pares distintos de subconjuntos separados
S1, S2, ..., Sk donde #(Si) = ni.
Por supuesto debemos tener n1 + n2 + ··· + nk = n
1. Use la regla de multiplicación para demostrar
que el número de tales particiones es:
C(n, n1)C(n - n1, n2) ··· C(n - n1 - ··· - nk - 1, nk).
2. Demostrar
que el resultado en el Ejercicio 1 se simplifica a:
C(n; n1, n2, ..., nk) = n! / (n1! n2! ··· nk!)
3. De un
argumento algebraico y uno combinacional para la identidad:
C(n; k, n - k) = C(n, k).
4. Una distribución
de bridge consiste en repartir 13 cartas (una mano de bridge) a cada uno
de los 4 jugadores distintos de un mazo normal de 52 cartas. Demostrar que el número de
distribuciones de bridge es:
53,644,737,765,488,792,839,237,440,000 ~ 5.36 × 1028.
5. Suponga que un club con 20 miembros planea formar 3
comités distintos con 6, 5, y 4 miembros, respectivamente. De cuántas maneras puede
hacerse esto. Nota: los miembros sin un comité también forma uno de los
conjuntos en la partición.
Considere ahora el conjunto T = {1, 2, ..., k }n. Los elementos de este conjunto son secuencias de longitud n en el cual cada coordenada es uno de los k valores. Así, estas secuencias generalizan la cadena de bit de longitud n en la última sección. De nuevo, permita a n1, n2, ..., nk ser enteros no-negativos con:
n1 + n2 + ··· + nk = n.
6. Construya
una correspondencia uno-a-uno entre las siguientes colecciones:
Se sigue de los Ejercicios 3 y 4 que el número de secuencia en {1, 2, ..., k }n en el cual i ocurre ni veces por cada i es:
C(n; n1, n2, ..., nk).
7. Suponga
ahora que tenemos n objetos de k diferentes tipos, con ni
elementos de tipo i para cada i. Además, los objetos de un tipo
dado son considerados idénticos. Construya una correspondencia uno-a-uno entre las
siguientes colecciones:
8. Encuentre el número de arreglos distintos de las letras en
cada una de las siguientes palabras:
9. Un chico tiene 12 bloques; 5 rojos, 4 verdes, y 3 azules.
De cuantas maneras pueden los bloques ser arreglados en una línea (los bloques de un
color son considerados idénticos).
10. De una
prueba combinacional del teorema multinomial:
(x1 + ··· + xk)n
= 
C(n;
n1, n2, ..., nk)x1n1
x2n2 ... xknk.
donde la suma está por encima de todos los (n1, ..., nk) tal que ni es un entero no-negativo para cada i y n1 + ··· + nk = n.
Debido al Ejercicio 10, los coeficientes C(n; n1, n2, ..., nk) son llamados coeficientes multinomial.
11.
Demostrar que hay C(n + k - 1, k - 1)
términos en la expansión binomial del Ejercicio 10.
12. Encuentre el coeficiente de x3y7z5
en (x + y + z)15.