3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Your approach over counts. You are counting each case in which one person receives three balls three times, once for each way of designating one of those colors as the color that person receives. You are counting each case in which two of the people receive two balls four times, once for each of the two ways you could designate one of the two colors each of those people receive as the color that person receives. $\endgroup$ – N. F. Taussig Jul 16 '20 at 11:10
  • $\begingroup$ I didn't exactly understand your comment but I think it holds insight into fixing my method. Can you please tell what I should multiply and divide by to fix this method(with the reason)? I am not particularly looking for the right answer, just trying to fix my pre-existing method (if that is possible() $\endgroup$ – Buraian Jul 16 '20 at 11:48
  • $\begingroup$ Please read Brian M. Scott's answer to the linked question. $\endgroup$ – N. F. Taussig Jul 16 '20 at 11:51
  • $\begingroup$ @N.F.Taussig The short answer to the question asked here is "you can't", but you won't find an explanation in the linked answers because that question made a completely different mistake. $\endgroup$ – David K Jul 16 '20 at 12:07
  • $\begingroup$ @N.F. Taussig the op doesn't explain how he got his formula and even then Brian's answer doesn't fix the thing. I;m pretty sure there is some way to fix my method, and I think it is a good combinatoric question to ask how to fix this $\endgroup$ – Buraian Jul 16 '20 at 13:35
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think I learned more about combinatorics from this one post than I have ever learned about combinatorics before $\endgroup$ – Buraian Jul 22 '20 at 0:25
  • $\begingroup$ Can you explain why it become C(4,2) , how does stars and bars change upon application of constraints that in between each bar there is at a minimum of one thing? One thing I noticed in your example is that you don't have an aspect of 'choosing people' to give balls too. Should we not care who get's the ball? $\endgroup$ – Buraian Jul 22 '20 at 0:28
  • $\begingroup$ Like it woul be awesome how you have that aspect in your question when you put it like (3,1,1) and then take permutations of that $\endgroup$ – Buraian Jul 22 '20 at 0:29
  • $\begingroup$ and in part 3, why did you do C(5,1) * C(4,2) * C(2,2) ? shouldn't it be C(5,2) * C(4,2) C(3,1) $\endgroup$ – Buraian Jul 22 '20 at 0:32
  • $\begingroup$ @DDD4C4U Imagine the $5$ (identical) balls in a row, to be given to Ann, Bill, Carol so that each gets a least one ball. Place bars in $2$ gaps from the $4$ interior gaps in the row of balls -- balls up to first bar go to Ann, between theirs to Bill, beyond the last bar to Carol. In other words you are counting the number of ways to write $5$ as an ORDERED sum of $3$ positive integers. The $C(4,2)=6$ ways are $3+1+1, 1+3+1, 1+1+3, 2+2+1, 2+1+2, 1+2+2$. $\endgroup$ – Ned Jul 22 '20 at 0:36
5
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Please type your answer rather than posting an image since images cannot be searched. This tutorial explains how to typeset mathematics on this site. $\endgroup$ – N. F. Taussig Jul 21 '20 at 11:32
  • $\begingroup$ yes i will put the code below it,it was not showing the table so i put it like this $\endgroup$ – Ginger bread Jul 21 '20 at 11:49
  • $\begingroup$ @N.F.Taussig if you can kindly make the table appear then I will remove the image $\endgroup$ – Ginger bread Jul 21 '20 at 11:58
  • 1
    $\begingroup$ I used an array environment to reconstruct your tables. Please check that I rendered everything correctly. $\endgroup$ – N. F. Taussig Jul 21 '20 at 14:29
  • $\begingroup$ yes it's perfect now, thanks! $\endgroup$ – Ginger bread Jul 21 '20 at 15:19
2
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The last part was very cool, I was of opinion that you must place dividers then put in the items. It was very eye opening to see it used in reverse way, put in the books and then build the shelfs haha :) $\endgroup$ – Buraian Jul 27 '20 at 18:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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