Say you've got $B$ buckets, each having a particular discreet capacity $c_b, 1\leq b\leq B$. Then you want to distribute all of $I$ of identical items. How many possible combinations do you have.

For example you have $I=3$ items and $B=4$ buckets with capacities $c_1=3, c_2=2, c_3=2, c_4=1$. Is there a (smart) way to determine that there exist only 14 possible valid combinations?


migrated from mathoverflow.net Jul 26 '13 at 16:50

This question came from our site for professional mathematicians.

  • $\begingroup$ The case where $c_b \ge I$ gives $\binom{I+B-1}{I}$, by "stars and bars": en.wikipedia.org/wiki/Stars_and_bars_(combinatorics) $\endgroup$ – S Huntsman Jul 26 '13 at 15:46
  • 1
    $\begingroup$ I would hope that this is not closed: if there is a simple answer, I am not aware of it and would like to know it. I previously wondered about this very question many years ago and based on that experience I do not think it should be migrated. For instance, I could not figure out how to make the straightforward appeal to inclusion-exclusion actually work in practice. $\endgroup$ – S Huntsman Jul 26 '13 at 15:50
  • 3
    $\begingroup$ Voting to close, it definitely belongs on MSE, not MO. The answer is, of course, "the coefficient of $x^I$ in $\frac{(1-x^{c_1+1})\cdots(1-x^{c_B+1})}{(1-x)^B}$", because this fraction is equal to $\prod_{b=1}^B(1+x+\cdots+x^{c_b})$, and hence manifestly enumerates exactly what you want. If you expand the numerator, you will get an inclusion-exclusion Steve Huntsman is asking for. $\endgroup$ – Vladimir Dotsenko Jul 26 '13 at 16:01
  • 1
    $\begingroup$ @VladimirDotsenko: I wish I could have read your comment back in 2001! $\endgroup$ – S Huntsman Jul 26 '13 at 16:36
  • $\begingroup$ @Steve Huntsman: I merely voiced the knowledge that most introductory books on generating functions contain, but thank you for the kind words! $\endgroup$ – Vladimir Dotsenko Jul 26 '13 at 18:59

Here the answer I gave in comments while this question was on Mathoverflow does probably belong as a proper answer, so I may as well reproduce it so that this question can be marked as answered and not float around.

The answer is, of course, "the coefficient of $x^I$ in $\frac{(1−x^{c_1+1})\cdots(1−x^{c_B+1})}{(1−x)^B}$", because this fraction is equal to $\prod_{b=1}^B(1+x+\cdots+x^{c_b})$, and hence manifestly enumerates exactly what you want (the distribution of items between the boxes is read from which power you take from each bracket when forming a term $x^I$).

Remark: If you expand the numerator, you will get an alternating sum which provides an inclusion-exclusion formula Steve Huntsman is asking for in his comment.

  • $\begingroup$ Thanks for your answer, but unfortunately I'm not firm with generating functions. How do I transform the fraction into an equation that I can solve for $x$ (assuming that x is the solution)? $\endgroup$ – Cris Jul 30 '13 at 15:44
  • $\begingroup$ Please try to read my answer carefully once again. You should not solve anything for $x$, you should compute the coefficient of $x^I$ in the power series expansion of the fraction. $\endgroup$ – Vladimir Dotsenko Jul 30 '13 at 18:23
  • $\begingroup$ I'm sorry, I don't get it. When I look up the unfamiliar terms on wikipedia I only end up with more unfamiliar english math terms. I'm not familiar with this type of math. $\endgroup$ – Cris Jul 30 '13 at 22:56
  • $\begingroup$ In your example, you should look at the product $(1+x+x^2+x^3)(1+x+x^2)(1+x+x^2)(1+x)$, and expand it as a polynomial in $x$, which gives $x^8+4x^7+9x^6+14x^5+ 16x^4 +14x^3+9x^2+4x+1$. Now, the coefficients of various powers of $x$ are equal to respective numbers you need. The coefficient of $x^3$ is $14$, so the number for $I=3$ is indeed $14$. The coefficient of $x^4$ is $16$, which means that for $I=4$ in this case the number of way is $16$. And so on... $\endgroup$ – Vladimir Dotsenko Jul 30 '13 at 23:16

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.