number of ways to distribute different balls among children

Question

In how many ways can eight different balls be distributed among 4 kids, s.t each gets at least one.

my approach: so I read a similar question here and figured out I should do this: $$4^8 - \binom{4}{1}3^8 + \binom{4}{2}2^8 - \binom{4}{3}1^8$$

but then I thought about this way : I will make sure first that each child gets one ball , so:
$8$ options for the first one
$7$ for the second
$6$ for the third
$5$ for the fourth
and then I have $4^4$ ways to distribute the left $4$ balls among the $4$ children. total $$(8 \cdot 7 \cdot 6 \cdot 5) \cdot 4^4$$

unfortunately the solution is not the same, so one of those approaches is wrong, but I cannot figure out which one.

Please help

Answer 1

For $i=1,2,3,4$ let $E_i$ be the set of arrangements such that kid $i$ gets no ball.

Here an arrangement is a function $\{1,2,3,4,5,6,7,8\}\to\{1,2,3,4\}$ and to be found is:$$4^8-|E_1\cup E_2\cup E_3\cup E_4|$$

For this we can the principle of inclusion/exclusion and symmetry, and we arrive at the first outcome you mention.

The second approach fails because it is not free from multiple counting.

E.g. number the balls and kids and start by giving kid $i$ ball $i$ as first ball. Then hand over ball $i+4$ to kid $i$. The same outcome shows up if you start by giving kid $i$ ball $i+4$ and then hand over ball $i$ to kid $i$.

Answer 2

Reduce the problem into a simpler one to magnify the mistake. Let's try solving the following problem

There are 4 different balls (A,B,C,D) and 2 different Boxes (B1,B2). In how many ways can you put these balls in these boxes such that no box is empty (or in other words both the box has at least one ball).

By your second approach :

• You can put A and B in B1 and B2 respectively and then distribute C and D in any fashion. Let's remember this one outcome B1={A,C,D} and B2={B}

• Once you're completed with distribution C and D in all possible ways. You start out again and this time you first distribute D and B in B1 and B2 respectively, and then let A and C be distributed randomly in any fashion. While you're doing it, you'll definitely encounter the same result again. B1={D,A,C} and B2={B}

Since the order in which kids receive the balls does not matter approach 2 is overcounting the same outcome and is not correct. Your first approach is correct though.