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?