A company hires $11$ new employees, and they will be assigned to four different departments, A, B, C, D. Each department has at least one new employee. In how many ways can these assignments be done?
I know that for each section (A,B,C,D) I should add a () and as long as every section must get a new employee we should start like this: $$(x+x^2/2!+x^3/3!+...)^4$$ then if we look it's $(e^x-1)^4$. After this step I don't know what to do.
On
Using balls and boxes, we know that there are $11$ distinct objects and $4$ distinct bins.
First, ignoring the restriction that each bin must get at least $1$ object, you get $4^{11}$ ways to arrange since each object have $4$ ways, and there are $11$ objects.
To take care of the restriction, we subtract all cases where only 1 bin is empty, then add the cases where only 2 bins are empty, etc (PIE). Therefore, we have $11$ objects into $3$ bins, and one of the bins is guaranteed empty, and there are $\binom41$ ways to choose that bin. Therefore, the restricted cases for $1$ box being empty are $\binom41 \cdot (4-1)^{11}$.
For the case where $2$ bin are empty, do the same reasoning as above, and get $\binom42\cdot(4-2)^{11}$.
For the case where $3$ bin are empty, you can get $\binom43\cdot(4-3)^{11}$
And for the $4$ bins empty case you can get $\binom44\cdot(4-4)^{11}$
Alternate adding and subtracting: $4^{11}-\binom41 \cdot (4-1)^{11}+\binom42\cdot(4-2)^{11}-\binom43\cdot(4-3)^{11}+\binom44\cdot(4-4)^{11}=3,498,000$
Sorry, since I am only a high schooler taking precalc right now, I need to research how to do generating functions for combinatorics. The answer to that might take a while.
Using $$(a+b)^4 = a^4 + 4a^3b + 6a^2b^2 +4ab^3 + b^4$$
$$(e^x-1)^4 = e^{4x} - 4e^{3x} + 6e^{2x} -4e^x + 1$$
and $$e^{kx} = 1+kx+\dfrac{(kx)^2}{2!}+\ldots+\dfrac{(kx)^{11}}{11!}+\ldots$$
$$\Rightarrow [\frac{x^{11}}{11!}] \, (e^{kx}) = k^{11}$$ Therefore $$[\frac{x^{11}}{11!}] \, (e^x-1)^4 =$$ $$ 4^{11} - 4\cdot 3^{11} + 6\cdot 2^{11} -4\cdot 1^{11}$$