Distribute stones into buckets with limits

1,093

Solution 1

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.

Solution 2

[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:
1,093

Related videos on Youtube

preshing
Author by

preshing

A programmer.

Updated on May 21, 2020

Comments

  • preshing
    preshing over 3 years

    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?

  • preshing
    preshing over 12 years
    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
    preshing over 12 years
    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}$?
  • Gerry Myerson
    Gerry Myerson over 12 years
    @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$$
  • preshing
    preshing over 12 years
    Thanks, you answered my question. I totally forgot about generating functions (studied this stuff 15 years ago) and that one works.