¿De cuántas maneras se pueden distribuir 8 profesores a 4 escuelas en las que cada una de ellas debe recibir al menos un profesor?

Question

Detalles adicionales: los profesores se consideran distintos entre sí.

Esto es lo que pensé:

1) Elige cuatro profesores para ir a cada uno de los colegios: $\binom{8}{4}\cdot4!$

2) Para cada una de esas situaciones, distribuye a los otros 4 profesores en las 4 escuelas: $4^4$

Así que total: $\binom{8}{4}\cdot4!\cdot4^4$

Sin embargo, estoy casi 100% seguro de que estoy contando de más, pero no puedo precisarlo. Se agradece cualquier ayuda.

Answer 1

Podemos utilizar la inclusión/exclusión. Hay $4^8$ formas de asignar el $8$ profesores, sin restricciones.

Tenemos que eliminar el mala asignaciones, donde algunas escuelas no reciben ningún profesor.

Que las escuelas sean A, B, C, D. Hay $3^8$ formas de asignar a los profesores, evitando que la escuela $A$ . También hay $3^8$ maneras de evitar las escuelas B, C, D, para un total de $\binom{4}{1}3^8$ .

Sin embargo, esto cuenta en exceso las malas asignaciones. Por ejemplo, $\binom{4}{1}3^8$ cuenta dos veces las asignaciones que evitan las escuelas A y B. Lo mismo ocurre con todas las $\binom{4}{2}$ pares de escuelas. Así que para contar las malas asignaciones, debemos restar $\binom{4}{2}2^8$ .

Pero hemos restado demasiado, pues hemos restado una vez más las asignaciones que evitan todas las escuelas menos la A, también las que evitan todas las escuelasola menos la B, o todas menos la C, o todas menos la D. Así que debemos volver a sumar $\binom{4}{3}1^8$ .

Por lo tanto, el número total de asignaciones buenas es $$4^8-\binom{4}{1}3^8+\binom{4}{2}2^8-\binom{4}{3}1^8.$$

Observación: Es de suponer que el recuento no lo hace un Consejo Escolar, ya que es probable que un Consejo considere indistintos a los profesores.

Answer 2

Otra forma es utilizar funciones generadoras exponenciales.

El EGF de este problema es:

$\left(x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+\frac{x^5}{5!}+\frac{x^6}{6!}+ \frac{x^7}{7!}+\frac{x^8}{8!}\right)^4$

para resolver el problema podemos utilizar

$(e^x-1)^4$

para esa expresión. Esto se amplía a

$ 1-4 e^x+6 e^{2 x}-4 e^{3 x}+e^{4 x}$

esto puede ampliarse a mano o llevarse a Wolfram Alpha. Lo conseguimos:

$x^4+2 x^5+\frac{13 x^6}{6}+\frac{5 x^7}{3}+ \frac{81 x^8}{80}+...+$

¡El coeficiente de x^8 es el que queremos y lo multiplicamos por 8!

$\dfrac{81}{80}\cdot 8! = 40824$

Ese es el número de formas.