2
$\begingroup$

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: distribution

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!

$\endgroup$

marked as duplicate by N. F. Taussig combinatorics Nov 9 '17 at 9:49

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ You are counting each possibility several times: the configurations where one victim has three balls and the other two one each is being counted three times, while those arrangements with a 2/2/1 split you are counting four times. $\endgroup$ – Lord Shark the Unknown Nov 9 '17 at 6:25
  • $\begingroup$ @LordSharktheUnknown I don't understand how.. $\endgroup$ – YourAverageEuler Nov 9 '17 at 6:27
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I think $3^5$ would be valid only for all identical balls. But the question clearly states that there are $5$ balls of DIFFERENT COLOURS. $\endgroup$ – YourAverageEuler Nov 9 '17 at 6:49
  • $\begingroup$ Since they are different, look at all the balls one by one. The first has 3 choices, either person A, B or C. So does the second, third, fourth and fifth. Hence there are $3^5$ ways to distribute them. $\endgroup$ – user10984851 Nov 9 '17 at 6:52
  • 1
    $\begingroup$ How did you come up with the second equation? Please elaborate your answer for the sake of reference in future. $\endgroup$ – YourAverageEuler Nov 9 '17 at 7:19

Not the answer you're looking for? Browse other questions tagged or ask your own question.