3
$\begingroup$

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?

2 Answers 2

3

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.

  • 0
    Thanks, you answered my question. I totally forgot about generating functions (studied this stuff 15 years ago) and that one works.2011-05-21
3

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

  • 0
    @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$2011-05-21