0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Satish Ramanathan Jan 12 '14 at 2:01
  • $\begingroup$ @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"? $\endgroup$ – psyllogism Jan 13 '14 at 0:51
0
$\begingroup$

Without some symmetry, I don't think you will find a simple answer. You can make complicated interactions between the colors depending on the contents of the bins. You are correct that if each bin has one of every color you have a stars and bars problem. If the colors are distinct between the urns it is again easy-it is just the product of the number of balls in each urn. In between, it is hard......

$\endgroup$
  • $\begingroup$ Thanks for the input. I was afraid of that... $\endgroup$ – psyllogism Jan 13 '14 at 22:50

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.