Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

You have $s$ different stones and $b$ different buckets. How many ways $w(s, b)$ can you distribute the stones into the buckets if no bucket is allowed to contain more than $L$ stones?

Clarification: The stones are all different from each other. So, for example, if you have 3 stones, 2 buckets, and at most 2 stones per bucket, there are 6 ways to distribute the stones: (A, BC), (AB, C), (AC, B), (B, AC), (BC, A), (C, AB).

I noticed that you can express the answer for $b$ buckets in terms of the answers for $b - 1$ buckets:

$$ w(s, b) = \sum_{i=0}^{\min(s, L)} {s \choose i} w(s - i, b - 1) $$

Also, $$ w(s, 1) = \left\{ \begin{array}{rl} 1 & \mbox{if }s <= L\\ 0 & \mbox{otherwise} \end{array} \right. $$

Based on those observations I came up with this Python function:

def countWays(numStones, numBuckets, L):
    # Precompute C(n, r) table
    C = [[1]]
    for n in xrange(numStones):
        C.append([1] + [C[-1][r] + C[-1][r+1] for r in xrange(n)] + [1])
    # Loop through number of buckets
    ways = [1] * (L + 1) + [0] * (numStones - L)
    for b in xrange(2, numBuckets + 1):
        ways = [sum([C[s][i] * ways[s - i] for i in xrange(min(s, L) + 1)])
                for s in xrange(numStones + 1)]
    return ways[numStones]

Some sample output:

>>> countWays(1, 2, 1)
2
>>> countWays(3, 2, 2)
6
>>> countWays(3, 3, 2)
24
>>> countWays(10, 10, 5)
9985309740L
>>> countWays(100, 100, 5)
94759885461565034681687026066885761311439165668901259822785622795797870660611943632316455279091491854154551818337317753294675330799396303953809575897498333285450197379975598951694414085442292940800000L

Is there a simpler solution, or closed form? Some basic principle of combinatorics I'm missing?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

Assuming that your stones are indistinguishable and the buckets are distinguishable, we can use generating functions to solve this.

Any given bucket can hold anywhere from 0 to L stones. This is represented by the polynomial $1+x+ x^2+\ldots x^L$. For b buckets, the total number of ways of distributing s stones is the coefficient of the term $x^s$ in the expansion $(1+x+ x^2+\ldots x^L)^b$.

Sanity Check Example: if you have two buckets, 4 stones and each bucket can hold at most 2 stones, there is only one way to do it. The coefficient of $x^4$ in $(1+x+x^2)^2$ is 1. If you have 3 buckets instead of 2, you need the coefficient of $x^4$ in $(1+x+x^2)^3$ which is 6 (you can enumerate the 6 possibilities easily).

EDIT: If the stones are distinguishable, you can still use generating functions to solve the problem. Now, the answer will be the coefficient of $x^s$ in $s!\left(1+x+\frac{x^2}{2!} + \frac{x^3}{3!} + \ldots +\frac{x^L}{L!}\right)^b$. In general, I don't think this expression is easily simplified.

The idea here is that you are partitioning $s$ stones into $b$ bins. What matters is the way you divide the stones among the bins, but not the way stones inside a bin are arranged. So, if you split 4 stones in two bins, the number corresponds to $\frac{4!}{2!2!} = 6$.

In the generating function I just pulled out the factor of $s!$ outside the polynomial term and divide each $x^k$ term by $k!$ to adjust the count. I checked for the case when $s = 4$, $b=3$ and $L=2$ and I get the answer 54.

share|improve this answer
    
Thanks for your answer. I probably should have been more clear; when I wrote that the stones were "different", I meant to say that they are distinguishable. In that case, there are actually 6 ways to distribute 4 stones in 2 buckets, where bucket holds at most 2 stones: (AB, CD), (AC, BD), (AD, BC), (BC, AD), (BD, AC) and (CD, AB). If you have 3 buckets instead of 2, I think the answer is 54, according to the Python script. –  preshing May 20 '11 at 13:04
    
Thanks, you answered my question. I totally forgot about generating functions (studied this stuff 15 years ago) and that one works. –  preshing May 21 '11 at 11:09

[svenkatr posted much the same thing while I was typing this up, but I think I've gone one step farther]

A standard way to do this is to see that it's the same as the number of solutions to $$x_1+x_2+\dots+x_b=s,\qquad 0\le x_i\le L$$ Then note that this is the coefficient of $x^s$ in $$(1+x+x^2+\dots+x^L)^b$$ Rewrite as $$(1-x^{L+1})^b(1-x)^{-b}$$ Use the binomial Theorem to expand both terms, and pick out the coefficient of $x^s$.

share|improve this answer
    
Thanks for your answer too. This seems to assume the stones are indistinguishable. However, as I mentioned to svenkatr, in my question the stones are all different from each other. Sorry if it was unclear -- I have since updated the question. A side question, though: How do you use the Binomial Theorem to expand $(1 - x)^{-b}$? –  preshing May 20 '11 at 15:16
    
@preshing, you define $n$-choose-$r$ to be $${n(n-1)\cdots(n-r+1)\over r!}$$ which works even if $n$ is negative (or fractional), and you show that with this definition $(-n)$-choose-$r$ is $(-1)^r$ times $(n+r-1)$-choose-$r$. Then $$(1-x)^{-b}=\sum_0^{\infty}{-b\choose r}x^r$$ –  Gerry Myerson May 21 '11 at 0:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.