¿De cuántas maneras se pueden distribuir 8 profesores entre 4 escuelas?

Question

Hay varias formas en que los maestros pueden ser divididos entre $4$ escuelas, aquí están las posibles opciones que se me ocurrieron:

$1) 1 1 1 5$

$2) 1 1 2 4$

$3) 1 1 3 3$

$4) 1 2 2 3$

$5) 2 2 2 2$

dado el hecho de que por ejemplo $2213$ es lo mismo que $1 2 2 3$ se omitió. Sin repeticiones, creo que son las únicas 5 posibilidades.

1)

${8 \choose 5} \times {3 \choose 1} \times {2 \choose 1} \times {1 \choose 1}$:

$\frac{8!}{5!3!} \times \frac{3!}{1!2!} \times \frac{2!}{1!1!} \times 1$

Lo que resulta en

$56 \times 3 \times 2 \times 1 = 336$

2)

${8 \choose 4} \times {4 \choose 2} \times {2 \choose 1} \times {1 \choose 1}$:

$\frac{8!}{4!4!} \times \frac{4!}{2!2!} \times \frac{2!}{1!1!} \times 1$

Lo que resulta en

$70 \times 6 \times 2 \times 1= 840$

3)

${8 \choose 3} \times {5 \choose 3} \times {2 \choose 1} \times {1 \choose 1}$

$\frac{8!}{3!5!} \times \frac{5!}{3!2!} \times \frac{2!}{1!1!} \times 1$

Lo que resulta en

$56 \times 10 \times 2 = 1,120$

4)

${8 \choose 3} \times {5 \choose 2} \times {3 \choose 2} \times {1 \choose 1}$

$\frac{8!}{3!5!} \times \frac{5!}{2!3!} \times \frac{3!}{2!1!} \times \frac{1!}{1!0!}$

Lo que resulta en:

Si 8 nuevos maestros serán divididos entre 4 nuevas escuelas, ¿cuántas divisiones son posibles?

$56 \times 10 \times 3 \times 1= 1,680$

5)

${8 \choose 2} \times {6 \choose 2} \times {4 \choose 2} \times {2 \choose 2}$

$\frac{8!}{2!6!} \times \frac{6!}{2!4!} \times \frac{4!}{2!2!} \times \frac{2!}{2!0!}$

Lo que resulta en:

$28 \times 15 \times 6 \times 1 = 2,520$

¿Qué me falta?

Answer 1

Con profesores y escuelas distintas y cada escuela debe tener al menos un maestro asignado, abordaría a través de inclusión-exclusión.

Permita que las escuelas estén etiquetadas como $a,b,c,d$. Permita que los maestros estén etiquetados como $1,2,3,\dots,8$.

Permita que el evento $A$ sea el evento de que la escuela $a$ no tiene maestros asignados. Similarmente, $B,C,D$ son los eventos de que las escuelas $b,c,d$ no tienen maestros asignados respectivamente.

Entonces, $|A\cup B\cup C\cup D|$ es el conjunto de formas de distribuir a los maestros que es "malo", resultando en una escuela sin un maestro en ella.

$|A|$ (y similarmente $|B|,|C|,|D|$) se pueden describir como las funciones de $\{1,2,3,\dots,8\}$ a $\{b,c,d\}$. Por el ejemplo anterior, sabemos que hay $3^8$ tales funciones.

$|A\cap B|$ (y similarmente $|A\cap C|,|A\cap D|,\dots$) se pueden describir como las funciones de $\{1,2,\dots,8\}$ a $\{c,d\}$. Por el ejemplo anterior, sabemos que hay $2^8$ tales funciones.

Similarmente, calculamos $|A\cap B\cap C|=1^8$ y $|A\cap B\cap C\cap D|=0^8$

Aplicando inclusión-exclusión entonces, tenemos $|A\cup B\cup C\cup D|=\binom{4}{1}3^8-\binom{4}{2}2^8+\binom{4}{3}1^8-\binom{4}{4}0^8=4\cdot 3^8-6\cdot 2^8+4=24712$

Dado que esos fueron los resultados "malos" de las $4^8$ formas totales de distribuir a los maestros, entonces hay $4^8-24712=40824$ formas buenas de distribuir a los maestros.

---

Una solución más corta utilizando fórmulas más complicadas que llevan un tiempo aprender aparece en la tabla que vinculé en los comentarios anteriores. Podemos describir esto como intentar contar el número de funciones sobreyectivas de $\{1,2,\dots,8\}$ a $\{a,b,c,d\}$.

Podemos lograr esto primero contando cuántas formas hay para dividir $\{1,2,\dots,8\}$ en $4$ subconjuntos no vacíos, y luego elegir cómo etiquetar los subconjuntos.

Podemos lograr el primer paso en $\left\{\begin{array}{}8\\4\end{array}\right\}$ número de formas. (_aquí $\left\{\begin{smallmatrix}n\\r\end{smallmatrix}\right\}$ representa el número de Stirling de segunda clase_). Podemos lograr el segundo paso en $4!$ número de formas, produciendo un total final de $4!\cdot \left\{\begin{array}{}8\\4\end{array}\right\}=40824$ formas. (wolfram)

Answer 2

Asumiendo maestros distintos, escuelas distintas, y habiendo identificado los $5$ patrones, una forma mecánica infalible es sumar el producto de dos coeficientes multinomiales para cada caso, uno para el patrón, y el otro para las frecuencias de solteros, dobles, triples, etc, a saber.

$\binom{8}{1,1,1,5}\binom{4}{3,1} + \binom{8}{1,1,2,4}\binom{4}{2,1,1} + \binom{8}{1,1,3,3}\binom{4}{2,2} + \binom{8}{1,2,2,3}\binom{4}{1,2,1} + \binom{8}{2,2,2,2}\binom44 = 40824$

Y si se prefiere las permutaciones a los coeficientes multinomiales, la expresión equivalente

$\frac{8!}{1!1!1!5!}\cdot\frac{4!}{3!1!} + \frac{8!}{1!1!2!4!}\cdot\frac{4!}{2!1!1!} + \frac{8!}{1!1!3!3!}\cdot\frac{4!}{2!2!}+\frac{8!}{1!2!2!3!}\cdot\frac{4!}{1!2!1!}+ \frac{8!}{2!2!2!2!}\cdot\frac{4!}{4!} = 40824$

Answer 3

El número total de combinaciones para $\color\red{111}\color\green{5}$:

$$\frac{(1+1+1+5)!}{1!\times1!\times1!\times5!}\times\frac{(\color\red3+\color\green1)!}{\color\red3!\times\color\green1!}=1344$$

---

El número total de combinaciones para $\color\red{11}\color\green{2}\color\orange{4}$:

$$\frac{(1+1+2+4)!}{1!\times1!\times2!\times4!}\times\frac{(\color\red2+\color\green1+\color\orange1)!}{\color\red2!\times\color\green1!\times\color\orange1}=10080$$

---

El número total de combinaciones para $\color\red{11}\color\green{33}$:

$$\frac{(1+1+3+3)!}{1!\times1!\times3!\times3!}\times\frac{(\color\red2+\color\green2)!}{\color\red2!\times\color\green2!}=6720$$

---

El número total de combinaciones para $\color\red{1}\color\green{22}\color\orange{3}$:

$$\frac{(1+2+2+3)!}{1!\times2!\times2!\times3!}\times\frac{(\color\red1+\color\green2+\color\orange1)!}{\color\red1!\times\color\green2!\times\color\orange1}=20160$$

---

El número total de combinaciones para $\color\red{2222}$:

$$\frac{(2+2+2+2)!}{2!\times2!\times2!\times2!}\times\frac{\color\red4!}{\color\red4!}=2520$$