3.4: Problemas de distribución (Ejercicios)

1. Responda cada una de las siguientes preguntas con\(n^{k}, k^{n}, n!, k!, \binom{n}{k}, \binom{k}{n}, n^{\underline{k}}, k^{\underline{n}}, n^{\bar{k}}, k^{\bar{n}}, \binom{n+k-1}{k}, \binom{n+k-1}{n}, \binom{n-1}{k-1}, \binom{k-1}{n-1}\), o “ninguna de las anteriores”.

1. ¿De cuántas maneras podemos repartir piezas\(k\) idénticas de dulces a\(n\) los niños?
2. ¿De cuántas maneras podemos repartir\(k\) distintas piezas de dulces a\(n\) los niños?
3. ¿De cuántas maneras podemos repartir piezas\(k\) idénticas de dulces a\(n\) los niños para que cada uno obtenga como máximo uno? (Asumir\(k \leq n\).)
4. ¿De cuántas maneras podemos repartir\(k\) distintas piezas de dulces a\(n\) los niños para que cada uno obtenga como máximo uno? (Asumir\(k \leq n\).)
5. ¿De cuántas maneras podemos repartir\(k\) distintas piezas de dulces a\(n\) los niños para que cada uno obtenga al menos uno? (Asumir\(k \geq n\).)
6. ¿De cuántas maneras podemos repartir piezas\(k\) idénticas de dulces a\(n\) los niños para que cada uno obtenga al menos uno? (Asumir\(k \geq n\).)

2. Al comité de mejoramiento vecinal se le han dado\(r\) árboles para que los distribuyan a\(s\) las familias que viven a un lado de una calle. A menos que se especifique lo contrario, no importa donde una familia plante los árboles que obtiene.

1. ¿De cuántas maneras pueden distribuirlos todos si los árboles son distintos, hay más familias que árboles, y cada familia puede obtener como máximo una?
2. ¿De cuántas maneras pueden distribuirlos todos si los árboles son distintos y cualquier familia puede obtener algún número?
3. ¿De cuántas maneras pueden distribuir todos los árboles si los árboles son idénticos, no hay más árboles que familias, y cualquier familia recibe como máximo uno?
4. ¿De cuántas maneras pueden distribuirlos si los árboles son distintos, hay más árboles que familias, y cada familia recibe como máximo uno (entonces podría haber algunos árboles sobrantes)?
5. ¿De cuántas maneras pueden distribuir todos los árboles si son idénticos y cualquiera puede recibir algún número de árboles?
6. ¿De cuántas maneras se pueden distribuir y plantar todos los árboles si los árboles son distintos, cualquier familia puede obtener cualquier número y una familia debe plantar sus árboles en una fila uniformemente espaciada a lo largo de la carretera?
7. Responda la pregunta en la Parte 2f asumiendo que toda familia debe obtener un árbol.
8. Responda la pregunta en la Parte 2e asumiendo que cada familia debe obtener al menos un árbol.

3. ¿De cuántas maneras se pueden\(n\) organizar libros\(r\) idénticos de química, libros\(s\) idénticos de matemáticas, libros\(t\) idénticos de física e idénticos libros de astronomía en tres estanterías? (Supongamos que no hay límite en el número de libros por estante.)

\(\rightarrow\)4. Una fórmula para los números de Lah es

\[L(k,n) = \binom{k}{n}(k-1)^{\underline{k-n}}\]

Encuentra una prueba que explique este producto.

5. ¿Cuál es el número de particiones de\(n\) en dos partes?

6. ¿Cuál es el número de particiones de\(k\) en\(k − 2\) partes?

7. Mostrar que el número de particiones de\(k\) en\(n\) partes de tamaño como máximo\(m\) es igual al número de particiones de\(mn − k\) en no más de\(n\) partes de tamaño como máximo\(m − 1\).

8. Mostrar que el número de particiones de\(k\) en partes de tamaño como máximo\(m\) es igual al número de particiones de\(k + m\) en\(m\) partes.

9. Se puede decir algo bastante específico sobre las particiones autoconjugadas de\(k\) en partes distintas. Averigua qué es y demuéstralo. Con eso, deberías poder encontrar una relación entre estas particiones y las particiones cuyas partes son números enteros consecutivos, empezando por\(1\). ¿Cuál es esa relación?

10. ¿Qué es\(s(k, 1)\)?

11. Demostrar que los números de Stirling del segundo tipo satisfacen la recurrencia

\[S(k,n) = \sum^{k}_{i=1} S(k-i,n-1)\binom{k-1}{i-1}\].

\(\rightarrow\)12. \(c(k, n)\)Sea la cantidad de formas en que\(k\) los niños se toman de la mano para formar\(n\) círculos, donde un niño juntando sus manos y sosteniéndolas para formar un círculo se considera un círculo. (Hacer que Mary sostenga la mano derecha de Sam es diferente a que Mary sostenga la mano izquierda de Sam). Encuentra una recurrencia para\(c(k, n)\). ¿La familia de números está\(c(k, n)\) relacionada con alguna de las otras familias de números que hemos estudiado? Si es así, ¿cómo?

\(\rightarrow\)13. ¿Cuántos árboles etiquetados en\(n\) vértices tienen exactamente cuatro vértices de grado\(1\)?

\(\rightarrow\)14. La secuencia de grados de una gráfica es una lista de los grados de los vértices en orden no creciente. Por ejemplo, la secuencia de grados de la primera gráfica en la Figura 2.3.3 es\((4, 3, 2, 2, 1)\). Para una gráfica con vértices etiquetados\(1\) a través\(n\), la secuencia ordenada de grados de la gráfica es la secuencia\(d_{1}, d_{2}, . . . d_{n}\) en la que\(d_{i}\) se encuentra el grado de vértice\(i\). Por ejemplo, la secuencia ordenada de grados de la primera gráfica en la Figura 2.3.1 es\((1, 2, 3, 3, 1, 1, 2, 1)\).

1. ¿Cuántos árboles etiquetados hay en los\(n\) vértices con secuencia ordenada de grados\(d_{1}, d_{2}, . . . ,d_{n}\)?
2. ¿Cuántos árboles etiquetados hay en los\(n\) vértices con la secuencia de grados en la que\(d\) aparece el grado\(i_{d}\) veces?