2
$\begingroup$

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

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

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?
$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

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.