Finding Ways to Execute Concurrent Processes: An Urn Model

[MartinWDK]

Dear all,

We are trying to compute the number of ways for a computer to execute concurrent processes.
It appears that this problem is equivalent to asking the following:

Assume that an urn is filled with different quantities of differently colored balls. There are k different colors, and the number of balls of a given color is denoted n_k.
Balls are drawn from the urn it is empty, and the color of the drawn ball is noted.

The question is: how many different color sequences can be constructed in this way?

Thank you,

Martin

 

[csopi]

Let N=n1+n2+...+nk

The answer for your question is
<br /> \frac {N!}{n_1!\dots n_k!}<br />
because there would be N! possibilities if the colours were pairwise different, but they are not, so we counted each possibility a lot of times. One can permutate the balls from the jth colour n_j! ways but when doing so we don't see any difference in the colour-sequence, so we have to divide N! by n_1!...n_k!

 

[MartinWDK]

Hi csopi,

Thank you for a quick reply and for a clear and coherent explanation!

The formula matches our calculations, so I think we have our answer :)



Martin