0

Assume, we have a standard urn problem, selecting $k$ items from an urn of size $n$, disregarding the order of elements (a combination). The number of possible combinations is given by $\binom{n}{k}$.

Now we restrict the number of valid combinations in the following way: Instead of one urn of size $n$, we are given $u$ sub-urns of sizes $n_1,\ldots,n_u$ with $n_1 + \ldots + n_u=n$. Once again, we are interested in the number of possible selections of $k$ items. We allow selections from any of the sub-urns, but we do not allow more than one item from each sub-urn (assuming $k \leq u$).

What is the number of possible selections? Any hint will be greatly appreciated.

2 Answers2

0

Hint:

If I understand well then from each sub-urn no item is taken or $1$ item is taken.

So $k$ of $u$ sub-urns must be selected as the sub-urns from which $1$ item is taken.

drhab
  • 151,093
  • Exactly, that makes $\binom{u}{k}$ possible selections of sub-urns. But I still would like to differentiate between different items to select from each of the sub-urns. –  Apr 04 '16 at 09:24
  • I understand, and in that case my hint is not enough. Also I suspect that a closed form of the solution will only be possible under extra conditions. E.g. $n_1=\cdots=n_u$. If urns $i_1,\dots,i_k$ are selected then there are $n_{i_1}\times\cdots\times n_{i_k}$ possibilities for the items to be taken. – drhab Apr 04 '16 at 09:35
  • Thanks! I guess in the general case, we do not have anything better than the following: $\sum_{1 \leq i_1 < \ldots < i_k \leq u}~\prod_{j=1}^k~n_{i_j}$ –  Apr 04 '16 at 14:42
0

You want the sum of the products of all $k$-element subsets of the $n_i$. This is the $k$-th elementary symmetric polynomial in the $n_i$. See these other questions:

Sum of multiplication of all combination of m element from an array of n elements

Formal sum of product of all size k subsets of a set

Sum-of-Product of subsets

Sum of Products of Subsets

Sum of products of all combinations?

Community
  • 1
joriki
  • 238,052