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?