You roll a k-sided die n times. What is the probability that each of the k faces appeared at least once?

If p(n) represents the probability of having chosen face n at least once, then by the inclusion/exclusion principle the probability of completing all of the faces is given by:

P = p(1)+p(2)+...+p(k) - p(1 or 2) - p(1 or 3) - ... - p((k-1) or k)
   + p(1 or 2 or 3) + ... + p((k-2) or (k-1) or k)
   ...
   +/- p(1 or 2 or ... or k)
  
where the final +/- depends on the mod 2 parity of k.

All single-number probabilities are the same as are all double-number probabilities etc., so that for example, p(1)+p(2)+...+p(k) = k*p(1) = 1 - ((k-1)/k)^n.

The probability of getting at least one occurrence from a set of i faces is 1 minus the probability of getting none of them, or 1 - ((k-i)/k)^n.

The formula is formalized as:

Sigma{i=1 to k}(C(k,i)*(1 - ((k-i)/k)^n)) * (-1)^(i+1))

   \ k:
 n    2       3       4       5       6       7       8       9      10
 2 0.50000 0.00000 0.00000 0.00000-0.00000-0.00000 0.00000-0.00000-0.00000
 3 0.75000 0.22222 0.00000 0.00000-0.00000-0.00000 0.00000-0.00000-0.00000
 4 0.87500 0.44444 0.09375 0.00000-0.00000-0.00000 0.00000-0.00000-0.00000
 5 0.93750 0.61728 0.23438 0.03840-0.00000 0.00000 0.00000 0.00000-0.00000
 6 0.96875 0.74074 0.38086 0.11520 0.01543-0.00000 0.00000-0.00000-0.00000
 7 0.98438 0.82579 0.51270 0.21504 0.05401 0.00612 0.00000-0.00000-0.00000
 8 0.99219 0.88340 0.62292 0.32256 0.11403 0.02448 0.00240 0.00000-0.00000
 9 0.99609 0.92212 0.71136 0.42707 0.18904 0.05770 0.01081 0.00094-0.00000
10 0.99805 0.94803 0.78060 0.52255 0.27181 0.10491 0.02816 0.00468 0.00036
11 0.99902 0.96533 0.83399 0.60636 0.35621 0.16310 0.05576 0.01336 0.00200
12 0.99951 0.97688 0.87476 0.67800 0.43782 0.22845 0.09331 0.02862 0.00619
13 0.99976 0.98459 0.90570 0.73812 0.51386 0.29731 0.13932 0.05132 0.01427
14 0.99988 0.98972 0.92909 0.78791 0.58285 0.36657 0.19172 0.08146 0.02732
15 0.99994 0.99315 0.94673 0.82877 0.64421 0.43392 0.24825 0.11831 0.04595
16 0.99997 0.99543 0.96000 0.86208 0.69800 0.49772 0.30680 0.16074 0.07031
17 0.99998 0.99696 0.96998 0.88910 0.74463 0.55697 0.36556 0.20734 0.10009
18 0.99999 0.99797 0.97747 0.91094 0.78471 0.61115 0.42310 0.25670 0.13467
19 1.00000 0.99865 0.98310 0.92855 0.81892 0.66009 0.47835 0.30748 0.17320
20 1.00000 0.99910 0.98732 0.94272 0.84799 0.70387 0.53056 0.35851 0.21474
21 1.00000 0.99940 0.99049 0.95410 0.87258 0.74273 0.57927 0.40882 0.25832
22 1.00000 0.99960 0.99287 0.96324 0.89332 0.77700 0.62425 0.45765 0.30306
23 1.00000 0.99973 0.99465 0.97056 0.91076 0.80707 0.66542 0.50443 0.34813
24 1.00000 0.99982 0.99599 0.97644 0.92542 0.83335 0.70284 0.54875 0.39283
25 1.00000 0.99988 0.99699 0.98114 0.93770 0.85624 0.73665 0.59036 0.43660
26 1.00000 0.99992 0.99774 0.98491 0.94798 0.87612 0.76704 0.62912 0.47899
27 1.00000 0.99995 0.99831 0.98792 0.95659 0.89334 0.79426 0.66500 0.51963
28 1.00000 0.99996 0.99873 0.99033 0.96378 0.90824 0.81854 0.69803 0.55830
29 1.00000 0.99998 0.99905 0.99227 0.96979 0.92111 0.84013 0.72828 0.59483
30 1.00000 0.99998 0.99929 0.99381 0.97480 0.93221 0.85930 0.75588 0.62914

The above table includes k=2 for including a coin as a 2-sided die and 3 for a 3-sided pencil used as a die, and is from:

    5   for K=2 to 10:print using(8,0),K;:next:print
   10   for N=2 to 30
   15      print using(3,0),N;
   20      for K=2 to 10
   30       Sum=0
   40       for I=1 to K
   50          Sum=Sum+combi(K,I)*(1-((K-I)/K)^N)*(-1)^(I+1)
   60       next I
   70       print using(2,5),Sum;
   80      next:print
  100   next:print

As a check, I'll simulate a 6-faced die rolled 12 times, with a million trials.

DEFDBL A-Z
n = 12: k = 6
FOR tr = 1 TO 1000000
  REDIM used(k)
  FOR roll = 1 TO n
    r = INT(RND(1) * k + 1)
    IF used(r) = 0 THEN used(0) = used(0) + 1
    used(r) = 1
  NEXT roll
  IF used(0) = k THEN success = success + 1
  PRINT USING "######## ##.#####"; tr; success / tr
NEXT tr

with the last line showing the success rate after 1,000,000 trials:

1000000  0.43745

agreeing statistically with the calculated 0.43782.

For the familiar 6-sided die, the probabilities as rational numbers are:

 5       0   =  0
 6       5/324   ~=     0.0154320987654320987
 7       35/648   ~=    0.0540123456790123456
 8       665/5832  ~=   0.1140260631001371742
 9       245/1296   ~=  0.1890432098765432098
 10      38045/139968 ~= 0.2718121284865112025
 11      99715/279936 ~= 0.3562064186099679926
 12      1654565/3779136   ~=   0.4378156806211790208
 13      485485/944784    ~=    0.5138581940422361089
 14      317181865/544195584 ~= 0.5828453488516363998
 15      233718485/362797056 ~= 0.6442127385951003968
 16      2279105465/3265173504    ~=    0.6980043976860593806
 17      4862708305/6530347008    ~=    0.7446324520033836461
 18      553436255195/705277476864  ~=  0.7847071164895857971
 19      1155136002965/1410554953728 ~= 0.8189230769861569511
 20      2691299309615/3173748645888 ~= 0.8479875408854210203
 21      3692455480945/4231664861184 ~= 0.8725774847660946991
 22      30241729508375/33853318889472    ~=    0.8933165344027712589
 23      184994418145075/203119913336832   ~=   0.9107645582651482934
 24      15225590090211325/16452712980283392 ~= 0.9254151645663163902
 25      30855347500002025/32905425960566784 ~= 0.9376978598295146596
 26      1122975934870626655/1184595334580404224   ~=   0.9479827432111204538
 27      83938352963274355/87747802561511424 ~= 0.9565863818006538052
 28      3425060881328615165/3553786003741212672   ~=   0.9637780321389404365
 29      3446410906664072165/3553786003741212672   ~=   0.969785716707730165
 30      1496550513734743428785/1535235553616203874304    ~=    0.9748018864008595101

Posted by Charlie on 2013-07-12 17:54:06