1
$\begingroup$

Given $K$ black boxes amd $M$ white boxes, and a total number of balls $k + m = N,$ can I use some modified "stars and bars" combinatorics to count the number of ways to distribute the balls into the boxes? Within each color, the boxes are indistinguishable.

EDIT: I am interested in the particular case when 1 << m << k if that helps.

$\endgroup$
  • 2
    $\begingroup$ Are these black boxes distinguishable between themselves? Why bother pointing out the color of the boxes at all if so and just call it $K+M$ distinguishable boxes total and just remember in the back of your mind that some of them are black and others are white... Stars and bars in the first place is used for when the boxes are distinguishable and the balls are indistinguishable. You need to clarify what are distinguishable in your problem and what are not. $\endgroup$ – JMoravitz Nov 9 '17 at 0:37
  • 1
    $\begingroup$ I assume from the problem statement that boxes of each color are indistinguishable. In which case you will need to compute some partition numbers, a rather more complicated procedure... $\endgroup$ – user7530 Nov 9 '17 at 0:40
  • $\begingroup$ @user7530 You are right, boxes of the same color are indistinguishable. $\endgroup$ – Ruslan Muhamadiarov Nov 9 '17 at 0:49
  • $\begingroup$ Yeah, stars-and-bars only works when the boxes are all distinguishable. Otherwise, where would you put the bars? $\endgroup$ – darij grinberg Nov 9 '17 at 6:40
3
$\begingroup$

When the boxes are indistinguishable, you cannot use "stars and bars."

Consider first the case of $K$ indistinguishable boxes and $N$ balls. Since only the multiset of ball counts, and not their order, matters, the number of ways of distributing the balls into the boxes is the number of partitions of $N$ into at most $K$ parts. Let's call this number $P_K(N)$; there is no closed-form formula for this number, but it can be computed either recursively (it's a standard "dynamic programming" problem in computer science) or using generating functions.

Now if you have two types of boxes, you need to count the number of ways of first partitioning the balls into those that will go into the white boxes, and those that go in the black boxes, and then, the number of ways of putting those balls into those boxes: $$\sum_{i=0}^N \left[P_K(i)P_{M}(N-i)\right].$$

$\endgroup$
  • $\begingroup$ Thank you for your reply and editing! I do appreciate that. So, the answer is just a product of two multiplicities, right? I did assume that it is just binomial coefficient. Is it correct assumption? $\endgroup$ – Ruslan Muhamadiarov Nov 9 '17 at 4:54
  • $\begingroup$ Why binomial coefficients? I don’t see where they would come in. $\endgroup$ – user7530 Nov 9 '17 at 5:51

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.