3
$\begingroup$

I was reading this question on quora, number of ways to distribute 8 identical balls in 3 different boxes, none being empty, Kavita Chawdhary gave an excellent answer but I was thinking if I remove the condition none being empty then what the answer would be.

★ ★ ★ ★ ★ ★ | ★ | ★

There will be $8$ stars and the $2$ bars can go to any of the $9$ places because there is no restriction now. But it gives $\binom{9}{2}$. But it is not of course what stars bars algorithm says, $\binom{n + k - 1}{n}$. What am I getting wrong?

$\endgroup$
1
  • 1
    $\begingroup$ There will be 8 stars and the 2 bars, so you have ten places and you get $\binom{10}{2}$ possibilities. $\endgroup$
    – Mateo
    Jul 1 at 14:43

1 Answer 1

3
$\begingroup$

You have reduced the problem to counting strings of $n=8$ stars and $k-1=2$ bars. There are actually 10 places that the bars can go, not 9, so $\binom{10}{2}$ options. This is equal to the $\binom{n+k-1}{n}=\binom{10}{8}$ by symmmetry of Pascal's triangle.

$\endgroup$
6
  • $\begingroup$ I just wonder where is the $10th$ option $\endgroup$ Jul 1 at 14:45
  • $\begingroup$ I'm not sure which option you're not seeing, but perhaps you're forgetting that bars could go at both the front or back of the string? $\endgroup$ Jul 1 at 14:48
  • $\begingroup$ $_1 ★_2 ★_3 ★_4 ★_5 ★_6 ★_7 ★_8 ★_9$ $\endgroup$ Jul 1 at 14:51
  • 2
    $\begingroup$ Ah! The other spot you are missing is behind the other bar. In fact, don't think of inserting bars into a string of stars. Just think of choosing which two characters in your final ten-character string will be bars. $\endgroup$ Jul 1 at 14:55
  • $\begingroup$ so it is it $_1 ★_2 ★_3 ★_4 ★_5 ★_6 ★_7 ★_8 \mid_9 ★_{10}$. Thanks $\endgroup$ Jul 1 at 14:58

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.