# 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

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$).
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
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