How to Distribute Identical Stones Among Buckets with Limits

“Distribute stones into buckets with limits” can mean several different counting problems. The standard interpretation is that the stones are identical, the buckets are distinct, and each bucket has a minimum and maximum number of stones. Under that interpretation, each distribution is an integer solution to a system of bounded equations.

If the stones are distinct, or if swapping buckets does not create a new distribution, the count changes. The methods below state which assumptions they use and explain those alternatives.

Model the distribution

Suppose there are $m$ distinct buckets and $n$ identical stones. Assume the bounds are integers with $0\le L_i\le U_i$. Let $x_i$ be the number of stones placed in bucket $i$. If bucket $i$ must hold at least $L_i$ and at most $U_i$ stones, the problem is to count solutions of

$$x_1+x_2+\cdots+x_m=n, \qquad L_i\le x_i\le U_i.$$

First check feasibility: the total must satisfy $\sum_i L_i\le n\le\sum_i U_i$. If not, there are no valid distributions.

When there are only lower bounds, subtract them: set $y_i=x_i-L_i$. The new variables are nonnegative and sum to $N=n-\sum_i L_i$. With no upper bounds, the stars-and-bars count is $\binom{N+m-1}{m-1}$. Upper bounds require an additional step.

Count with upper limits

After subtracting the minimums, define the capacity $c_i=U_i-L_i$. The remaining variables satisfy $0\le y_i\le c_i$ and sum to $N$. Inclusion-exclusion starts with all nonnegative solutions, then removes solutions that exceed one or more capacities:

$$\sum_{S\subseteq\{1,\ldots,m\}}(-1)^{|S|}\binom{N-\sum_{i\in S}(c_i+1)+m-1}{m-1}.$$

Treat a binomial coefficient as zero if its top argument is less than $m-1$. For each selected bucket in $S$, the formula subtracts $c_i+1$ from its count, representing the amount by which that bucket exceeds its limit. Inclusion-exclusion corrects for solutions that violate multiple limits.

A compact equivalent is the generating-function coefficient

$$[t^N]\prod_{i=1}^{m}(1+t+t^2+\cdots+t^{c_i}).$$

Here $[t^N]$ means “the coefficient of $t^N$.” Choosing a term $t^{y_i}$ from bucket $i$ records putting $y_i$ of the remaining stones there; the product counts every allowed choice whose total exponent is $N$.

Worked example

How many ways can 10 identical stones be placed in 4 distinct buckets if each bucket must contain between 1 and 4 stones?

Subtract one stone from each bucket. That leaves $N=10-4=6$ stones to distribute, and each bucket can receive at most $c_i=3$ additional stones. Without the upper limits, stars and bars gives

$$\binom{6+4-1}{4-1}=\binom{9}{3}=84.$$

Now remove distributions in which some bucket gets at least 4 of the remaining stones. For a specified bucket, subtract 4 from its count; the other counts then sum to 2. There are $\binom{2+4-1}{3}=\binom{5}{3}=10$ such distributions for that bucket, and there are 4 choices of bucket. Two buckets cannot each exceed the cap because that would require at least 8 of the 6 remaining stones. Therefore the answer is

$$84-4\binom{5}{3}=84-40=44.$$

There are 44 valid distributions. For example, the bucket counts $(1,2,3,4)$ are valid; $(1,1,4,4)$ is also valid, while $(1,1,1,7)$ violates a maximum.

A practical procedure

1. Decide whether stones and buckets are distinguishable.
2. Write one variable for each distinct bucket and record its minimum and maximum.
3. Subtract each minimum and calculate the remaining total $N$ and capacities $c_i$.
4. Check that $0\le N\le\sum_i c_i$.
5. Use inclusion-exclusion for a formula, or take the coefficient of $t^N$ in the generating function.

For a small problem, you can also multiply the short polynomials directly or list feasible values of all but one variable. The final variable is then forced by the required total.

Common mistakes

• Treating buckets as interchangeable. With distinct buckets, $(2,3,5)$ and $(3,2,5)$ are different distributions. If buckets are identical and have the same constraints, they are not counted separately, and the problem becomes a count of unordered group sizes.
• Using stars and bars without enforcing caps. The formula $\binom{N+m-1}{m-1}$ allows a bucket to exceed its maximum. Use it alone only when there are no upper bounds, or when no unrestricted solution can exceed any cap.
• Forgetting to shift the total. After placing the required minimums, count $N=n-\sum_i L_i$, not the original $n$.
• Assuming distinct stones follow the same count. If stones are distinct and bucket $i$ must receive $x_i$ stones, that count vector corresponds to $n!/\prod_i x_i!$ assignments. Sum this quantity over all valid count vectors.

If the stones are identical but the buckets are indistinguishable and have the same bounds, a useful starting point is to count nondecreasing or nonincreasing lists of bucket sizes satisfying the bounds. That is a different problem from ordinary stars and bars because permutations of bucket counts no longer represent separate outcomes.