1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Brendan McKay Oct 27 '13 at 2:47
  • $\begingroup$ 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. $\endgroup$ – Mathias Oct 27 '13 at 7:51
  • $\begingroup$ I meant to say polynomial in k. $\endgroup$ – Mathias Oct 27 '13 at 7:59
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mathias Oct 27 '13 at 7:49
3
$\begingroup$

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

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