# Drawing balls from multiple urns

I'm working on a hobby project and ran in to a statistical / combinatorical problem that I'm having trouble answering. I'm somewhat familiar with urn models, so I've phrased it like that below, but maybe this problem has been solved in another metaphor? I tried to be clear but it's been a while since I've had to write mathematically precise. Hope someone can help! Thanks.

Balls can be one of $m$ colors, $C_1,...C_m$

There are $n$ urns, with the $i$th urn holding $1 \leq U_i \leq m$ balls. The number of balls in each urn may or may not be the same between urns. Each ball in a single urn is a different color than other balls in that urn, but multiple urns may have balls of the same color (so urn $i$ can only have at most one ball of color $C_k$, but both urn $i$ and urn $j$ may each have a ball of that color). The exact distribution of balls in urns is known beforehand.

You draw one ball from each urn, for a total of $n$ balls. Order doesn't matter, so a ball of color $C_k$ drawn from urn $i$ is the same as one drawn from urn $j$. How many different combinations of draws are possible? Is there an efficient algorithm for generating each of the possible combinations?

Edit:

I know that if each urn contains one ball of each color, then I have a stars and bars problem (http://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)). Using Theorem 2 from the Wikipedia page, the cardinality is the number of urns and the set of elements is the colors $C_1,...,C_m$. Can something along these lines be used if the urns do not necessarily contain the same number of balls?

• What is the total number of balls in all urns. Should be between n<=total balls<=m*n. Does the distribution of the balls in all urns a critical piece to work out a solution. If not the no of different combinations could only be a range given the above range of total balls in the urns? Am I mis-reading it? – Satish Ramanathan Jan 12 '14 at 2:01
• @satishramanathan Yes that would be the total number of balls in all urns. I do believe that the distribution of balls in all urns is critical. If one of the urns only has one ball in it of color $C_k$, then every combination of draws would have to include at least one ball of that color. But maybe I'm not sure what you mean by a "range given the above total balls in the urns"? – psyllogism Jan 13 '14 at 0:51