Consider an urn with 12 beads, four of each color: red, yellow and blue. Pull these beads out in pairs. What is the probability that among these six pairs, every color combination is represented?

Consider an urn with 30 beads, 10 of each color. Pull these beads out in triplets. What is the probability that every color combination is represented?

If we take the possibilities of the order of all 12 beads, that's 12! ways of ordering them. But within colors, the order does not matter, so we divide by (4!)^3, to give us unique color orderings.  But not only 1 out of this number (12!/(4!)^3 = 34650) satisfies the criteria.  First of all, the order within pairs does not matter, so it is then 2^3 out of 34650 (this is based on only the unequal pairs, as we've already considered reordering among equal-colors).  Then also, it does not matter which order the six pairs themselves appear in, so we multiply the probability by 6!.

Overall, then, the probability is (4!)^3 * 6! * 2^3 / 12! = 64/385 = .1662337662337662... or 1/6.015625.

This is confirmed in a simulation:

'nEach = 10: nComb = 10: gpSize = 3
nEach = 4: nComb = 6: gpSize = 2

DIM drw(3 * nEach)
DIM a(3 * nEach)

'colors numbered 1 to 3
FOR i = 1 TO nEach: drw(i) = 1: NEXT
FOR i = nEach + 1 TO 2 * nEach: drw(i) = 2: NEXT
FOR i = 2 * nEach + 1 TO 3 * nEach: drw(i) = 3: NEXT

DO
 'shuffle
 FOR i = 1 TO 3 * nEach
  a(i) = RND(1)
 NEXT
 DO
  done = 1
  FOR i = 1 TO 3 * nEach - 1
    IF a(i) > a(i + 1) THEN
      SWAP a(i), a(i + 1)
      SWAP drw(i), drw(i + 1)
      done = 0
    END IF
  NEXT
 LOOP UNTIL done

 'test
 good = 1
 hadSize = INT(3 ^ gpSize + .5)
 REDIM had(hadSize)
 FOR s0 = 1 TO 3 * nEach STEP gpSize
  FOR i = 1 TO gpSize
   part(i) = drw(s0 + i - 1)
  NEXT
  DO
   done = 1
   FOR i = 1 TO gpSize - 1
     IF part(i) > part(i + 1) THEN
       SWAP part(i), part(i + 1)
       done = 0
     END IF
   NEXT
  LOOP UNTIL done
  hadSub = part(1) - 1
  FOR i = 2 TO gpSize
   hadSub = gpSize * hadSub + part(i) - 1
  NEXT
  IF had(hadSub) THEN good = 0: EXIT FOR
  had(hadSub) = 1
 NEXT
 IF good THEN goodCt = goodCt + 1
 ct = ct + 1
 IF goodCt > 0 THEN PRINT ct; goodCt, ct / goodCt
LOOP

Similarly, for the second part, where there are 10 color combinations (3 monochrome, 1 panchromatic, 6 with 1 of one color and 2 of another), there are 30! ways of picking individual beads, but divide this by (10!)^3 to get all the possible color arrays to go into the denominator of the probability. But then muliply by 3! for the number of ways that the panchromatic triplet can be selected, by 3^6 for the six bichromatic triplets can be arranged within each of themselves and by 10! for the number of ways the triplets can be rearranged.  That makes the probability (10!)^3 * 3! * 3^6 * 10! / 30! = 12597120/4405553009 ~= .002859373153441949 or 1/349.7270018067622, verified by a similar simulation program (just un-comment the first line and comment out the second).

Posted by Charlie on 2006-12-17 13:00:07