Draws from multiple non-disjoint urns

Question

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.

Answer 1

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.

Answer 2

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