# number of ways to distribute different balls among children

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.

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$$.

• why is it not free from multiple counting? Jun 8, 2019 at 7:54
• In the example I gave two (and there are even more) ways (all are counted) that end up with kid $i$ having the balls $i$ and $i+4$. But that is only one outcome, so should be counted once. Jun 8, 2019 at 7:57

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).