Distributing $5$ different balls to $4$ different persons We have to find the number of ways of distributing $5$ different balls to $4$ different persons.
Clearly, the answer is $4^5$ as each ball can be given to any of the $4$ persons. However, I wanted to calculate it using a different method.
I assumed that $a$ balls are given to first person, $b$ to second , $c$ to third and $d$ to fourth person. So we have that $a+b+c+d=5$ where $0 \leq a,b,c,d \leq 5$.
But counting the solutions to the above equation assumes that balls are identical. So I tried to find the number of distributions each permutation of $(a,b,c,d)$ produces. That will be $\displaystyle \binom{5}{a}\cdot \binom{5-a}{b}\cdot \binom{5-a-b}{c} $ which equals $\dfrac{5!}{a!b!c!d!}$.
So, now we need to sum this value over all $a,b,c,d$ satisfying $a+b+c+d=5$. Now there are $\displaystyle \binom{8}{3}=56$ solutions to the equation. So there will be $56$ terms in that summation. So how do we do that?
 A: Work backwards:
Suppose you already gave out $a$ balls to the first person and $b$ balls to the second.   You now have $\binom{5-a-b}{c}$ ways of giving $c$ balls to the third person and the remaining balls to the fourth person.  Summing this up for all possible value of $c$ gives: $\binom{5-a-b}{0}+\binom{5-a-b}{1}+...+\binom{5-a-b}{5-a-b}=2^{5-a-b}$.
Suppose you gave out $a$ balls to the first person.  You now have $\binom{5-a}{b}$ ways of giving $b$ balls to the second person, and for each of those you are left with $2^{5-a-b}$ ways of giving out balls to the remaining two people.  Summing this up for all values of $b$ gives:
$\binom{5-a}{0}2^{5-a}+\binom{5-a}{1}2^{4-a}+...+\binom{5-a}{5-1}2^{0}=3^{5-a}$.
Lastly, summing for $a$, you have $\binom{5}{0}3^5+\binom{5}{1}3^4+\binom{5}{2}3^3+\binom{5}{3}3^2+\binom{5}{4}3^1+\binom{5}{5}3^0=4^5$.
This uses the identity:
$$\sum_{k=0}^X\binom{X}{k}Y^k=\sum_{k=0}^X\binom{X}{X-k}Y^k=(Y+1)^X$$
This identity comes from the fact that this sum is what you get when you expand the binomial $(1+Y)^X$
A: Answering the question in the comments, about proving that for any $m\geq 1$ and $n\geq 0$:
$$\sum_{x_1+x_2+...+x_m=n}\frac{1}{x_1!x_2!...x_m!}=\frac{m^n}{n!}$$
First, start by recognizing that $\sum_{k=0}^p\binom{p}{k}A^k=(A+1)^p$.
If we expand the binomial expression, we get the sum.
Then prove by induction:
For $m=1$, the formula is trivially true.
For $m=2$:
$$\sum_{x_1+x_2=n}\frac{1}{x_1!x_2!}=\sum_{x_1=0}^n\frac{1}{x_1!(2-x_1)!} = \frac{1}{2!} \sum_{x_1=0}^n\frac{2!}{x_1!(2-x_1)!} = \frac{1}{2!} \sum_{x_1=0}^n\binom{n}{x_1} = \frac{2^n}{n!}$$
Given that it holds true for $1\leq m\leq s$, prove that it also holds true for $m=s+1$:
$$\sum_{x_1+...+x_s+x_{s+1}=n}\frac{1}{x_1!...x_s!x_{s+1}!} = \sum_{x_{s+1}=0}^n\sum_{x_1+...+x_s=n-x_{s+1}=n}\frac{1}{x_1!...x_s!x_{s+1}!} = \sum_{x_{s+1}=0}^n\frac{1}{x_{s+1}!}\sum_{x_1+...+x_s=n-x_{s+1}=n}\frac{1}{x_1!...x_s!} = \sum_{x_{s+1}=0}^n\frac{1}{x_{s+1}!}\frac{s^{n-x_{s+1}}}{(n-x_{s+1})!} = \frac{1}{n!}\sum_{x_{s+1}=0}^n\frac{n!s^{n-x_{s+1}}}{(n-x_{s+1})!x_{s+1}!} =\frac{1}{n!}\sum_{x_{s+1}=0}^n\binom{n}{n-x_{s+1}}s^{n-x_{s+1}} = \frac{(s+1)^n}{n!}$$
A: Consider the partitions $5$ into $4$ parts
\begin{eqnarray*}
(5,0,0,0),(4,1,0,0),(3,2,0,0),(3,1,1,0),(2,2,1,0),(2,1,1,1).
\end{eqnarray*}
These have symmetry factors $4,12,12,12,12,4$ respectively (which adds upto $56$ as you state)
Now the balls can be distributed in each case and multiply in the symmetry factors ...
\begin{eqnarray*}
 4 \times \frac{5!}{5!0!0!0!} + 12 \times \dfrac{5!}{4!1!0!0!} + 12 \times \dfrac{5!}{3!2!0!0!} + 12 \times \dfrac{5!}{3!1!1!0!} + 12 \times \dfrac{5!}{2!2!1!0!} + 4 \times \dfrac{5!}{2!1!1!1!} =1024= 4^5.
\end{eqnarray*}
