3
$\begingroup$

The problem I'm trying to solve is: find the number of ways of distributing $r$ identical objects into $n$ distinct boxes such that no box is empty, where $r \geq n$. I've found conflicting answers to this in numerous searches, and I'm hoping someone might be able to point me in the direction of how to arrive at the correct one. Thanks so much!

$\endgroup$
  • 2
    $\begingroup$ I would be surprised at any answer other than $\binom{r-1}{n-1}$ or something equivalent. Where is there something else? It is standard Stars and Bars. Please see Wikipedia. $\endgroup$ – André Nicolas May 14 '15 at 4:32
7
$\begingroup$

stars and bars - represent the r identical object as r stars ****** you can divide them into boxes by placing bars in between stars so **|*|*** represents six objects split into three boxes with 2 in the first box, 1 in the second, and three in the third.

in general there will be $r$ stars , leaving $(r-1)$ positions to place the $(n-1)$ bars.

The total number of ways to position the bars is given by $\binom{r-1}{n-1}$

$\endgroup$
  • $\begingroup$ Is this the star bar method given in Wikipedia? $\endgroup$ – Scáthach Dec 22 '18 at 0:37

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.