1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Interesting! Now I wonder what possible closed form solution or bound could be derived from this. $\endgroup$ – Shen-Fu Tsai Apr 1 '17 at 1:22
  • $\begingroup$ 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). $\endgroup$ – N. Shales Apr 1 '17 at 2:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.