How many ways are there to distribute 5 balls of different colours among three persons with additional conditions? [duplicate]

Question

Problem:

The total number of ways in which 5 balls of different colour can be distributed among three persons so that each person gets at least one ball?

Source:

A book on combinatorics. Was asked in an entrance exam.

My try:

To simplify the problem, we can distribute $3$ of the $5$ balls beforehand so we can get rid of the constraint. Let us select 3 balls and permute them within these three persons, so the number of ways of doing so $$ N_1 = C(5,3) + P(3,3) = 60$$

Now that we have done so, we have two balls left. Let them be $B_1$ and $B_2$ These can be distributed as below:

Let both the remaining balls be with one person, so we have $$(B_1 B_2, 0, 0)$$ and there are $3$ ways of doing so.

Let the remaining balls be distributed one by one, so we have $$(B_1, B_2, 0)$$ and there are $3! = 6$ ways of doing so.

We can take the total number ways ($N$) by: $$N = N_1 \times 3 + N_1 \times 6$$ $$N = 60 \times 3 + 60 \times 6$$ $$N = 540$$

This approach seems correct to me but still it gets the wrong answer...

The right answer is $150$ ways

Please guide me and correct me if I'm wrong. All help appreciated!

Answer 1

(Your mistake: By handing ut three selected balls (red, blue, yellow) beforehand you exclude the possibility that, e.g., the same person gets the red and the blue ball.)

We are told to count the number of surjective functions $f:\>[5]\to[3]$. The shortcut answer is the following: Each such function partitions the set $[5]$ into $3$ nonempty blocks. Such set-partitions are counted by the Stirling numbers of the second kind. According to the tables one has ${\cal S}(5,3)=25$. Given such a partition there are $3!=6$ ways to allocate the three blocks to the three persons. It follows that there are $150$ admissible allocations in all.

A second way to count these allocations is to set up an inclusion/exclusio process as in MrPoopybutthole's answer.

A third way is the following: There are exactly $2$ ways of partitioning $5$ unlabeled objects into three nonempty heaps, namely $(3,1,1)$ and $(2,2,1)$. For the first type we can select the three balls going together in ${5\choose3}=10$ ways. For the second type we can select the single ball in $5$ ways, then pair off the remaining $4$ balls in $3$ ways, makes $5\cdot3=15$ possible partitions of the five colors. In both cases we can distribute the three resulting "combos" to the three persons in $6$ ways; makes $6(10+15)=150$ in all.

Answer 2

The total number of ways to distribute the 5 balls among 3 persons is $3^5$.

Now, the number of cases in which at least one person doesn't get a ball is $${3 \choose 1}\times2^5 - {3 \choose 2}\times1^5= 93$$ So, the number of cases where each person gets at least one ball is $$3^5-93=150$$