0
$\begingroup$

The problem below was presented earlier today and I am wondering why a "stars and bars" approach wouldn't be an appropriate method to solving this problem. The problem reads as follows:

Find the probability that each child gets at least 1 ball when we are distributing 5 DISTINCT balls among 4 children (who are distinct of course).

Here is how I interpreted this problem.

Counting the number of ways we can distribute $n=5$ balls among $k=4$ children in such a way so that each child gets at least one ball is equivalent to counting the number of ways we can express $n=5$ as a sum of $k=4$ positive integers, of which there are nCr($5-1$,$4-1$) ways via stars and bars.

Meanwhile, the number of ways we can distribute the $n=5$ balls among the $k=4$ children in any way we'd like is equivalent to counting the number of ways we can express $n=5$ as a sum of $k=4$ non$-$negative integers, of which there are nCr($5+4-1$,$5$) ways.

Dividing these two numbers gives us a probability of $\frac{1}{14}$ which is incorrect.

Is my problem with this approach that the "star and bars" approach doesn't account for the fact that the balls are distinct?

$\endgroup$
2
  • 2
    $\begingroup$ Yes it doesn't take into account that $\endgroup$
    – Peanut
    Jul 11, 2020 at 23:48
  • $\begingroup$ Is there a way we can modify the stars and bars approach to take into account that the balls are distinct? $\endgroup$
    – Matthew H.
    Jul 11, 2020 at 23:50

1 Answer 1

1
$\begingroup$

Yes, that’s the problem. If the children are $A$, $B$, $C$, and $D$, there are actually $\binom52\cdot 3!=60$ different ways to distribute the balls so that $A$ gets $2$ balls and $B$, $C$, and $D$ get one each: there are $\binom52=10$ different pairs of balls that can be given to $A$, and the remaining $3$ balls can be permuted amongst $B,C$, and $D$ in $3!=6$ distinguishable orders.

$\endgroup$
2
  • $\begingroup$ We would multiply nCr($5,2$)$*3!$ by $4$ to count the number of ways we can distribute the five balls among the four kids in such a way that each kid gets at least one ball, correct? I am learning counting on my own and this is the only place I can really get help, so thank you for your response. Very helpful and clear. $\endgroup$
    – Matthew H.
    Jul 12, 2020 at 0:00
  • $\begingroup$ @MatthewHolder: Yes, that’s correct. And to answer your question in the comments above, no, there really isn’t any way to modify the stars and bars approach to handle this kind of question. If there are $n$ balls and $k$ kids, the general answer is $k!{n\brace k}$, where ${n\brace k}$ is a Stirling number of the second kind. You’re very welcome; I’m glad that it helped. $\endgroup$ Jul 12, 2020 at 0:04

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.