# Draws from multiple non-disjoint urns

Let $C = \{1,...,n\}$ be a set of $n$ colors. Let $S_1,...,S_k$ be non-empty subsets of $C$, that is, $S_i \subseteq C$ for all $i \in \{1,...,k\}$. It is helpful to think of the $S_i$ as urns with colored balls.

We now draw one ball from each $S_i$.

Given $b_1,...,b_n$ with $b_1 +...+ b_n = k$. How many ways are there to draw $b_1$ balls with color $1$, $b_2$ balls with color $2$, ..., and $b_n$ balls with color $n$?

Please note that the special case where each $S_i = C$ is well-known. Here, the number of combinations is $$\binom{k}{b_1}\binom{k-b_1}{b_2}...\binom{k-\sum_{j=1}^{n-2} b_j}{b_{n-1}}\binom{k-\sum_{j=1}^{n-1} b_j}{b_n}.$$

I am looking for a closed form expression. I'm afraid this expression is rather complicated and involves some incarnation of the inclusion-exclusion principle. Alternatively, I'd be interested in an algorithm that is more efficient than a trivial enumeration of all possible combinations.

• I think Ira is correct that there won't be a useful formula. To compute actual numbers for small sizes, a recurrence is likely to work for a while. A count for $k$ urns is a sum of $|C_k|$ counts for $k-1$ urns. – Brendan McKay Oct 27 '13 at 2:47
• Thanks. I also think that a closed form expression is hopeless. I'm still hoping that there's an algorithm that runs in time linear in k (an possibly exponential in n). btw: Thanks for Nauty. I've used it quite a bit for my research. – Mathias Oct 27 '13 at 7:51
• I meant to say polynomial in k. – Mathias Oct 27 '13 at 7:59

## 2 Answers

The answer is the coefficient of $x_1^{b_1}\cdots x_n^{b_n}$ in $$\prod_{i=1}^k \biggl(\sum_{j\in C_i} x_j\biggr).$$ It's unlikely that anything more useful can be said in the general case.

• Thanks. I am still hoping that there exists an algorithm whose running time is polynomial in k (I don't care if it is exponential in n). I'm not (yet) convinced that this isn't possible. – Mathias Oct 27 '13 at 7:49

Define a 0-1 matrix $A=(a_{ij})$ of order $n\times k$, where $a_{ij}=1$ iff $i\in S_j$. Then the task is to count the number of ways of choosing a 1 in each column so that the row sums are $b_1,\ldots,b_n$.

For $k=n$ and $b_1=\cdots =b_n=1$, this is the same as computing the permanent of $A$, and so is #P-hard. A polynomial-time algorithm is exceedingly unlikely.

In the special case $n=O(1)$, there are only $O(1)$ different columns possible. Consider Ira's formulation: the answer $N$ is the constant term in $$F(x_1,\ldots,x_n)=\prod_{i=1}^n x_i^{-d_i}~ \prod_{j=1}^k \Bigl( \sum_{i\in S_j} x_i\Bigr).$$ Now choose your favorite prime field $\mathbb F_p$ that has a primitive root $\alpha$ of order $m\gt k$. Sum $m^{-n} F(x_1,\ldots,x_n)$ modulo $p$ over $x_1,\ldots,x_n \in\lbrace \alpha^0,\ldots,\alpha^{m-1}\rbrace$ and you get $N$ modulo $p$. Do this for sufficiently many primes $p$ and apply the Chinese remainder theorem to recover $N$ exactly. Since the number of different columns is $O(1)$, each term in the sum costs only $O(1)$ time (using logarithms to compute the powers). So the cost is $m^n$ per prime. Now one needs to check how many primes are needed, surely not many (Prime Number Theorem needed). The total cost will be something like $k^{n+1}$, which is polynomial in $k$.