Finding Ways to Execute Concurrent Processes: An Urn Model

  • Context: Graduate 
  • Thread starter Thread starter MartinWDK
  • Start date Start date
  • Tags Tags
    Model
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
Sign up Log in
2 replies · 3K views
MartinWDK
Messages
2
Reaction score
0
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 nk.
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
 

Discussion

Physics news on Phys.org
Let N=n1+n2+...+nk

The answer for your question is
[tex] \frac {N!}{n_1!\dots n_k!}[/tex]
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!
 
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