I have been thinking about the following problem:
How many ways can $50$ different balls be placed into $50$ different sized boxes if exactly $2$ boxes have to remain empty?
My approach was the following:
There are two possible cases which satisfy the conditions:
- There are $2$ boxes with $2$ balls and $46$ boxes with $1$ ball;
- There is $1$ box with $3$ balls and $47$ boxes with $1$ ball.
In the first case, you can choose the $2$ empty boxes first ($\binom{50}{2}$ possibilities), then you can choose the boxes which have $2$ balls in them ($\binom{48}{2}$ possibilities). After that, you can choose $2$ balls which are placed in the bigger box chosen in the previous step ($\binom{50}{2}$ possibilities), then $2$ balls which are placed in the smaller box ($\binom{48}{2}$ possibilities). Finally, there are only $46$ balls left that have to be placed in the $46$ boxes remained, $1$ ball in each of them ($46!$ possibilities). Totally, there are $\binom{50}{2}* \binom{48}{2}* \binom{50}{2}* \binom{48}{2}* 46!$ possibilities.
In the second case, following a similar logic, there are $\binom{50}{2}* 48* \binom{50}{3}* 47!$ possibilities totally. The final answer to the question can be given adding these two numbers.
However, using the classic inclusion-exclusion formula, the following number of possibilities arise: $\binom{50}{2}* \sum_{k=0}^{48} (-1)^k \binom{48}{k} * (48-k)^{50}$.
I am quite sure that the number derived from the inclusion-exclusion formula is correct, however, I haven't got any clue what is wrong with my first solution.
I would appreciate any help or explanation why my first solution is not correct.
What you have done is correct.
You can apply Principle of Inclusion Exclusion and that leads to the same answer.
Using P.I.E, ${50 \choose 2} \times \sum \limits_{i=0}^{48} {(-1)^i} {48 \choose i} (48-i)^{50}$
Another way to do it will be to choose $2$ empty boxes out of $50$ and then use Stirling Number of the second kind to make $48$ non-empty heaps from $50$ balls and then permute the heaps as we have distinct boxes. That again leads to the same answer.
$S2(50,48) \times 48! \times {50 \choose 2}$
Here is the answer when you calculate any of the above $3$ expressions using Mathematica - $10804606609908677549993379050994509131965157167373221888000000000000000$