Stars and bars but with distinct objects

Question

The total number of ways which 5 balls of different colors can be distributed among 3 persons so that each person gets at least one ball is..?

My attempt:

So, first we can choose any three balls to allocate to any person, so $\binom{5}{3}$ and, then distribute them then in 3! ways. And, so we have, $\binom{5}{3} \cdot 3! $. Now I have two remaining balls and this I can give randomly to any of the three people. For the first ball I have three choices and so do I for the second ball.

Hence, The net number of cases is

$ \binom{5}{3} \cdot 3! \cdot 3^2$

Now, I know that like the thing can happen in reverse. For example distributing three then distributing two, I could have some overlapping cases where the items which are distributed in the distributing two case is actually distributed in the distributing three step.

How do I account for the overlapping case?

Ans: 150

Stars and bars attempt:

We have five objects and introduce two objects as dividers, subtract cases where one guy gets nothing (3 x 6!) and add cases where two people get nothing and third guy everything (3)

What I am looking for : A fix to this method such that it gives me the correct answer, in the other stack post linked to this one, it has ample amount of methods based on other ways to solve it but my question here is how to fix this method.

Answer 1

How to "fix up" the stars and bars approach.

1. Thee are $C(4,2) = 6$ ways to distribute $5$ identical balls to $3$ people with each person getting at least $1$ ball -- standard stars and bars.

2. $3$ of the $6$ are permutations of the form $(3,1,1)$. Each such permutation corresponds to $C(5,3)*C(2,1)*C(1,1) = 20$ many distributions if the balls are distinct (choose $3$ balls for the person getting $3$, then $1$ ball from the other $2$ for the younger remaining person).

3. $3$ of the $6$ are permutations of $(2,2,1)$. Each such permutations corresponds to $C(5,1)*C(4,2)*C(2,2) = 30$ many distributions if the balls are distinct (choose $1$ ball for the person getting $1$, then $2$ balls fro the other $4$ for the younger remaining person).

So you have a total of $3*20 + 3*30 = 150$ altogether.

Note: The factor by which you multiply is NOT uniform (i.e. $20$ vs. $30$), which is why this is not a good approach to this sort of problem -- for bigger numbers, chasing through the cases would be tedious.

Answer 2

From my experience, when dealing with distinct objects, it is never a good approach to say "let's first distribute some to fulfill the condition, then distribute the rest without limitations" exactly because the overcounting you mentioned.

The correct approach is the inclusion-exclusion principle: $$3^5-3\cdot 2^5+3=150$$ We consider all the distributions possible, removing the one in which only two people can get the object (there are 3 ways to choose these two) and add the ones in which only one person can get the object (there are 3 ways to choose this one).

Answer 3

It's an interesting question and I too stumbled upon the same doubt that you are having right now. I will try to first explain why there is over counting in your method, then I will try to provide the nearest possible correct method which may fix your problem.

So, let the balls be named as $A,B,C,D$ and $E$ while let the people be $P_1 , P_2$ and $P_3$.

Now,stage 1: select $3$ balls out of $5$ suppose $A,B,C$ and give it to $P_1 , P_2$ and $P_3$ respectively.so, the distribution looks like:\

$$ \begin{array}{|l|l|l|} P_1 & P_2 & P_3\\ \hline A & B & C \\ \end{array} $$

Now suppose you give $D$ and $E$ to $P_1$ and $P_3$, respectively, then it will look like:

$$ \begin{array}{|l|l|l|} P_1 & P_2 & P_3 \\ \hline A & B & C \\ D & - &E \\ \end{array} $$

On the other hand, suppose you chose $D,B$ and $E$ and gave it to $P_1 , P_2$ and $P_3$ then the distribution looks like:

$$ \begin{array}{|l|l|l|} P_1 & P_2 & P_3 \\ \hline D & B & E \\ \end{array} $$

and now give $A$ and $C$ to $P_1$ and $P_3$, respectively, so finally we observe

$$ \begin{array}{|l|l|l|} P_1 & P_2 & P_3 \\ \hline D & B & E \\ A & - &C \\ \end{array} $$

which is essentially the same as the previous final distribution.

Now the correct method:

Rather than distributing in three stages, distribute them in one go like make a group of $(3,1,1)$ balls and give it to $P_1 , P_2$ and $P_3$ in $$\frac{5!}{(3!)(1!)^2} \cdot \frac{1}{(2!)} \cdot (3!) =60$$ ways and make a group of $(2,2,1)$ balls and give it to $P_1 , P_2$ and $P_3$ in $$\frac{5!}{(1!)(2!)^2} \cdot \frac{1}{(2!)} \cdot (3!) =90$$ ways and finally $$60+90=150$$ and that's the correct answer.

Answer 4

Perhaps it is instructive to understand why your methods are incorrect.

One way to correctly solve the problem is to use the Inclusion-Exclusion Principle, as shown by YJT's answer.

Another way is to observe that since each child receives at least one ball, either one child receives three balls and each of the others receives one ball each or two children each receive two balls and the other child receives the remaining ball.

One child receives three balls and each of the others receives one ball each: Choose which of the three children receives three balls. Choose which three of the five balls this child receives. Choose which of the remaining two balls the younger of the remaining two children receives, then hand the remaining ball to the remaining child. There are $$\binom{3}{1}\binom{5}{3}\binom{2}{1}$$ such distributions.

Two children each receive two balls and the remaining child receives one ball: Choose which two of the three children receive two balls each. Choose which two of the five balls the younger of those children receives. Choose which two of the remaining three balls the older of those children receives, then then hand the remaining ball to the remaining child. There are $$\binom{3}{2}\binom{5}{2}\binom{3}{2}$$ such distributions.

Total: Since these two cases are mutually exclusive and exhaustive, the number of ways five distinct balls can be distributed to three children so that each child receives at least one is $$\binom{3}{1}\binom{5}{3}\binom{2}{1} + \binom{3}{2}\binom{5}{2}\binom{3}{2} = 60 + 90 = 150.$$

Note that this is just a slight modification of Ned's approach.

Why is your first method incorrect?

By first distributing a ball to each child and then distributing the remaining two balls, you count each distribution multiple times since the order in which each child who receives more than one ball does not matter.

Suppose the children are Anthony (A), Barbara (B), and Charlotte (C) and the ball colors are blue (b), green (g), pink (p), red (r), and yellow (y).

You count each distribution in which a child receives three balls three times, once for each way you could designate one of the balls as the ball that child initially receives. For instance, you count the distribution in which Anthony receives the blue, green, and red balls, Barbara receives the pink ball, and Charlotte receives the yellow ball three times:

$$ \begin{array}{l l} \text{initial distribution} & \text{distribution of additional balls}\\ (A, b), (B, p), (C, y) & (A, g), (A, r)\\ (A, g), (B, p), (C, y) & (A, b), (A, r)\\ (A, r), (B, p), (C, y) & (A, b), (A, g) \end{array} $$ where the first letter in each ordered pair denotes the recipient and the second letter denotes the color of the ball that child receives.

You count each distribution in which two children each receive two balls four times, once for each of the two ways you could designate one of the two balls those children receive as the ball that child initially receives.

Suppose Anthony receives a green ball, Barbara receives a blue ball and a red ball, and Charlotte receives a pink ball and a yellow ball. You count this distribution four times.

$$ \begin{array}{c c} \text{initial distribution} & \text{distribution of additional balls}\\ (A, g), (B, b), (C, p) & (B, r), (C, y)\\ (A, g), (B, b), (C, y) & (B, r), (C, p)\\ (A, g), (B, r), (C, p) & (B, b), (C, y)\\ (A, g), (B, r), (C, y) & (B, b), (C, p) \end{array} $$

Notice that $$\color{red}{3}\binom{3}{1}\binom{5}{3}\binom{2}{1} + \color{red}{4}\binom{3}{2}\binom{5}{2}\binom{3}{2} = \color{red}{\binom{5}{3}3!3^2} = \color{red}{540}$$

Since the factor by which you over count differs for the two cases, your approach cannot be salvaged by using an Inclusion-Exclusion argument.

What you have counted is the number of ways of first distributing five distinct balls, none of which is white, to three children so that each child receives at least one ball, then painting one of the balls each child receives white.

Why is your second approach incorrect?

What matters is which child receives which ball, not the order in which the balls are received or arranged by a given child. Therefore, trying to exclude the bad cases will not work since you are solving a different problem, namely:

In how may ways can five distinct books be arranged on three shelves if at least one book is placed on each shelf?

An easier way to do that problem is to arrange the five books in some order, which can be done in $5!$ ways. To ensure that no shelf is left empty, we must place dividers in two of the four spaces between successive books in the row of five books. $$b_1 \square b_2 \square b_3 \square b_4 \square b_5$$ This can be done in $\binom{4}{2}$ ways. Thus, there are $$5!\binom{4}{2} = 720$$ ways to arrange five distinct books on three shelves so that each shelf receives at least one book.