# Counting ways to distribute identical objects among finite number of bins

Given positive integers $w_1,w_2,\ldots,w_n$ with $m=\sum_{i\in[n]}w_i$. We have $n$ bins numbered $1, 2, \ldots, n$ with capacity $w_1,w_2,\ldots,w_n$. In how many ways could we place $\lceil\frac{m}{2}\rceil$ identical objects in these $n$ bins, such that no bin holds more than its capacity?

I wonder if there's research about this quantity, e.g. upper and lower bounds.

## 1 Answer

In general we can represent the possible fillings of bin $k$ as a polynomial

$$x^1+x^2+x^3+\cdots +x^{w_k}$$

interpreted as "bin $k$ may have $1$ object or $2$ objects or $3$ objects ... or $w_k$ objects".

Each bin can be represented this way, so if we wish to represent combinations of all possibilities of bin fillings then it seems natural to write the product of each of these $n$ polynomials (the multiplication represents the logical "and" operation whereas "$+$" represents "or")

$$\prod_{k=1}^{n}\left(\sum_{r=1}^{w_k}x^r\right)$$

in the expansion of such a polynomial the coefficient of the term $x^{\lceil m/2\rceil}$ will receive a contribution of $1$ for every possible combination of valid bin fillings of our $n$ bins with $\lceil m/2\rceil$ identical objects.

Hence in general the answer is

$$\left[x^{\lceil m/2\rceil}\right]\prod_{k=1}^{n}\left(\sum_{r=1}^{w_k}x^r\right)$$

where $\left[x^{\lceil m/2\rceil}\right]$ is the operator that extracts the $x^{\lceil m/2\rceil}$ term of the expansion.

• Interesting! Now I wonder what possible closed form solution or bound could be derived from this. – Shen-Fu Tsai Apr 1 '17 at 1:22
• Well if each bin has the same capacity $w$ then each polynomial is the same finite geometric series with sum $\frac{x-x^{w+1}}{1-x}$ so the product is just $$\frac{(x-x^{w+1})^n}{(1-x)^n}$$ then by expanding the numerator as a binomial and the denominator as a Taylor series we get a fairly straightforward closed form (an alternating sum). For arbitrary bin capacities you may have to settle for multiplying out using a 2 dimensional recurrence table (think along the lines of how Pascal's identity recurrence produces pascal triangle but with a different recurrence for each row). – N. Shales Apr 1 '17 at 2:04