# Choosing from multiple bins

I have $n$ bins. All items in a bin are identical, and items from different bins are different. The $i^\textrm{th}$ bin contains $n_i$ items. How many distinct ways can I choose $k$ items from the bins (ignoring order).

For example, suppose I have a bin of three As, a bin of 2 Bs and a bin of 2 Cs. I can choose 4 items in the following ways: AAAB, AAAC, AABB, AABC, AACC, ABBC, ABCC, BBCC. In general, If I want to pick 4 items, I can

1. Pick 4 items from one bin.
2. Pick 3 items from one bin and 1 item from another.
3. Pick 2 items each from 2 different bins.
4. Pick 2 items from one bin, and 1 item each from 2 different bins.
5. Pick 1 item each from 4 different bins.

Clearly the partitions of $k$ is important. I've reasoned out a formula, but I'm hoping there is a simpler expression. I've already simplified it with a bit of notation:

• $p(k)$ is, as usual, the set of all partitions of $k$.
• $s_i$ is a part of the partition, in decreasing order.
• $m_i$ is the multiplicity of $s_i$ in the partition.
• $b_n$ is the number of bins containing at least $n$ items.

For example, in the $4+4+3+3+3+3+1+1$ partition of 22, $s_1 = 4$, $s_2 = 3$, $s_3 = 1$, $m_1 = 2$, $m_2 = 4$ and $m_3 = 2$.

Given bins, a number of items to choose $k$, and a partition of $k = \sum_{i} m_i s_i$, the above example generalizes as:

1. Choose $m_1$ bins containing at least $s_1$ items: $\binom{b_{s_1}}{m_1}$
2. Choose $m_2$ bins containing at least $s_2$ items. Since $s_2 < s_1$, the already chosen bins are included in this. I cannot choose from a bin twice, as that is accounted for with a different partition: $\binom{b_{s_2} - m_1}{m_2}$
3. Choose $m_3$ bins containing at least $s_3$ items, excluding the $m_1 + m_2$ bins I've already chosen: $\binom{b_{s_3} - (m_1 + m_2)}{m_3}$.
4. Etc.

Continuing, there are $\prod_i \binom{b_{s_i} - \sum_{j=1}^{i-1} m_j}{m_i}$ ways to choose with a particular partition. In total, there are

$$\sum_{p\in p(k)} \prod_{i} \binom{b_{s_i} - \sum_{j=1}^{i-1} m_j}{m_i}$$

ways to choose $k$ items from the bins.

I believe my reasoning is sound, and I've tested the formula for several small cases. My questions are then:

1. Is the formula correct?
2. Is there a simpler expression?

The simplest expression for the result is to take the coefficient of $X^k$ in $$\prod_{i=1}^n(1+X+\cdots+X^{n_i}) =\prod_{i=1}^n\frac{1-X^{n_i+1}}{1-X}.$$ While there are methods to find these coefficients relatively easily for concrete values of $(n_1,\ldots,n_n)$, and in any case the product of polynomials can be evaluated easily (certainly with help of a computer), I don't think there is any general closed formula for the mentioned coefficient in terms of those numbers $n_1,\ldots,n_n$ and $k$.