13
$\begingroup$

Is there a separate formula for calculating distribution of n identical objects into r distinct groups? I read this particular concept in a book but did not understand it. Any help would be thoroughly appreciated.

Also, what exactly do u mean by distinct groups? Does that mean that the groups differ on the basis of no of objects they contain? Or, if u think of groups as boxes, does it mean the boxes itself are different regardless of no of objects in them?

EDIT : How would the answer differ if instead of distinct groups/boxes, we have identical groups/boxes?

$\endgroup$
  • 1
    $\begingroup$ Its something like marbles and people. So suppose you want to give 100 marbles to four people. The dollars are all the same, but the persons are not. So giving 3 marbles to John and 5 to Ben is not the same as giving 5 to John and 3 to Ben. However all marbles are the same, so all that matters is how many marbles each person gets. $\endgroup$ – Jorge Fernández Hidalgo Dec 26 '13 at 6:06
  • $\begingroup$ So sir, this problem should have the same answer as if the groups/boxes are identical, right? $\endgroup$ – user34304 Dec 26 '13 at 6:21
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Twelvefold_way $\endgroup$ – Henry Dec 26 '13 at 7:09
  • $\begingroup$ @user34304 no, you are counting some combinations more than once, giving for dollars to Joe and 3 to Tony and giving 3 to Joe and 4 to Tony where different when the boxes (Joe and Tony) where different. However now the boxes are the same, so Joe and Tony become indistinguishable persons, that is giving 4 to joe and 3 to Tony would be the same as 3 to Joe and 4 to Tony, so you are counting some cases more than once. $\endgroup$ – Jorge Fernández Hidalgo Dec 26 '13 at 15:51
16
$\begingroup$

This is called stars and bars method. suppose the stars are objects and space between bars represents objects corresponding to a certain group. Here is a visual representation:

$\underbrace{*****}_{\text{first group}}|\underbrace{******}_{\text{second group}}|\underbrace{*****}_\text{third group}|\underbrace{**}_\text{fourth group}$

Check each arrangement of bars provides a unique group separation and each group separation corresponds to a unique bar arrangement.Also check to seperate the stars in n groups only (n-1) bars are required.

then all you need to do is see how many bar arrangements are possible. Observe that when you have the $n-1$ bars and $k$ stars (assuming there are k objects to sort into n groups) then there are $n-1+k$ positions the stars and bars can take. So there are $\binom{n+k-1}{n-1}$ ways to chose the positions of the bars.


The problem gets harder when the boxes are identical, because for example: he following arrangements are the same: $*|***|**$ and $**|*|***$ In the problem where the boxes are different the answer would somehow correspond to distributing coins between people. When the boxes are identical however it corresponds to finding the number of partitions of the number into x or less non-zero parts. So if we define $p_k(n)$ to be the number of partitions of n numbers into exactly $k$ non-zero pieces then we get the number of ways to put n identical marbles into k identical boxes is $\sum_{k=0}^np_k$. However there is no pretty formula to calculate $p_k$ or $\sum_{k=0}^np_k$.

$\endgroup$
  • $\begingroup$ What about the case where the groups are identical? $\endgroup$ – user34304 Dec 26 '13 at 6:23
  • $\begingroup$ Does this help you? $\endgroup$ – Jorge Fernández Hidalgo Dec 26 '13 at 17:56
  • $\begingroup$ @JorgeFernández I can't understand one thing that how does the stars and bars method ensure that $n-1$ bars will be placed into the distinct places i.e. the bars don't overlap each other. $\endgroup$ – spectraa Sep 13 '14 at 3:52
  • 1
    $\begingroup$ It foesn't, if two overlap it means that there are no stars between those bars. If you want to ensure at least 1 for each category just take away 1 star for each category and do the same. so the formula would be $\binom{k-1}{n-1}$ $\endgroup$ – Jorge Fernández Hidalgo Sep 13 '14 at 15:17
  • $\begingroup$ @JorgeFernández Thanks for explanation. $\endgroup$ – spectraa Sep 13 '14 at 16:23

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.