# Number of item distributions in buckets of different sizes

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.netJul 26 '13 at 16:50

This question came from our site for professional mathematicians.

• 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) – S Huntsman Jul 26 '13 at 15:46
• 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. – S Huntsman Jul 26 '13 at 15:50
• 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. – Vladimir Dotsenko Jul 26 '13 at 16:01
• @VladimirDotsenko: I wish I could have read your comment back in 2001! – S Huntsman Jul 26 '13 at 16:36
• @Steve Huntsman: I merely voiced the knowledge that most introductory books on generating functions contain, but thank you for the kind words! – Vladimir Dotsenko Jul 26 '13 at 18:59

## 1 Answer

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.

• 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)? – Cris Jul 30 '13 at 15:44
• 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. – Vladimir Dotsenko Jul 30 '13 at 18:23
• 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. – Cris Jul 30 '13 at 22:56
• 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... – Vladimir Dotsenko Jul 30 '13 at 23:16