home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / math / 17189 < prev    next >
Encoding:
Internet Message Format  |  1992-12-21  |  3.5 KB
  1. Path: sparky!uunet!idacrd!desj@ccr-p.ida.org
  2. From: desj@ccr-p.ida.org (David desJardins)
  3. Newsgroups: sci.math
  4. Subject: Re: The Mathematics of Secret Santa
  5. Message-ID: <1818@idacrd.UUCP>
  6. Date: 18 Dec 92 23:21:05 GMT
  7. References: <1992Dec17.220416.18649@husc15.harvard.edu>
  8. Sender: desj@idacrd.UUCP
  9. Organization: IDA Center for Communications Research, Princeton
  10. Lines: 97
  11.  
  12. Eric Blom <blom@husc15.harvard.edu> writes:
  13. >What is the probability that in a Secret Santa arrangement of n people, there
  14. >is at least one pair of participants with each other as Secret Santas?
  15.  
  16. >No participant may have himself.
  17.  
  18. As usual, the problem is most easily solved by inclusion-exclusion.
  19.  
  20. Let D(m) be the number of derangements of m items (permutations with no
  21. fixed points).  As is well known (also by inclusion-exclusion) this is
  22.  
  23.    D(m) = \sum_{k=0}^m (-1)^k m!/k!
  24.  
  25. Now fix n.  Let T be a collection of t distinct 2-sets from {1,...,n}.
  26. Let E(T) be the number of derangements of {1,...,n} which contain each
  27. 2-set in S as a 2-cycle (and possibly also some other 2-cycles).  Then
  28. clearly
  29.  
  30.    E(T) = D (n - 2t)
  31.  
  32. because 2t values of the permutation are fixed and map to themselves as
  33. a set, and the remainder are free to be any derangement of the remaining
  34. points.
  35.  
  36. Now let S be a similar collection of s distinct 2-sets from {1,...,n}.
  37. Let F(S) be the number of derangements of {1,...,n} which contain each
  38. 2-set in S as a 2-cycle, and no other 2-cycles.  Clearly
  39.  
  40.    E(T) = \sum_{S\supseteq T} F(S)
  41.  
  42. because if we fix T to be the set of required 2-cycles, then the set of
  43. actual 2-cycles S must contain T.
  44.  
  45. By the inclusion-exclusion formula:
  46.  
  47.    F(S) = \sum_{T\supseteq S} (-1)^{|T|-|S|} E(T).
  48.  
  49. Now, the probability you asked for is 1-F(0)/D(n), where 0 is the
  50. empty set.  The number of sets T of cardinality t which contain 0 is
  51.  
  52.    n! / (2^t t! (n-2t)!)
  53.  
  54. Thus the formula for F(0) becomes
  55.  
  56.    F(0) = \sum_{t=0}^{n/2} (-1)^t n! / (2^t t! (n-2t)!) D(n-2t)
  57.         = \sum_{t=0}^{n/2} \sum_{k=0}^{n-2t} (-1)^{t+k} n! / (2^t t! k!)
  58.         = \sum_{k=0}^n \sum_{t=0}^{(n-k)/2} (-1)^{t+k} n! / (2^t t! k!)
  59.  
  60. (You can choose whichever of the last two lines you find simpler as the
  61. "answer".)
  62.  
  63. A quick table:
  64.  
  65.         n       D(n)    F(0)    Prob
  66.         ----    ----    ----    ------
  67.         2       1       0       1.0000
  68.         3       2       2       0.0000
  69.         4       9       6       0.3333
  70.         5       44      24      0.4545
  71.         6       265     160     0.3962
  72.         7       1854    1140    0.3851
  73.         8       14833   8988    0.3940
  74.         9       133496  80864   0.3943
  75.         10      1334961 809856  0.3933
  76.  
  77. > For the record, here are the first few values of P(n)*!n, which should be the
  78. > numerator of the fraction:
  79. > 
  80. > !2*P(2) = 1
  81. > !3*P(3) = 0
  82. > !4*P(4) = 3
  83. > !5*P(5) = 20
  84. > !6*P(6) = 105
  85. > !7*P(7) = 504
  86.  
  87. I think Eric's table was right up to n=6, but wrong for n=7.
  88.  
  89. Finally it is interesting to note that, from the formula, it is easy to
  90. compute the limit of the probability as n goes to infinity.  It is well
  91. known (and obvious from the formula) that
  92.  
  93.    \lim_{n\to\infty} D(n)/n! = exp(-1)
  94.  
  95. But, by placing suitable bounds on the rate of convergence (which
  96. details I omit here), we can show that
  97.  
  98.    \lim_{n\to\infty} F(0)/n!
  99.      = \lim_{n\to\infty} \sum_{k=0}^n \sum_{t=0}^{(n-k)/2} (-1)^{t+k} / (2^t t! k!)
  100.      = \sum_{k=0}^\infty \sum_{t=0}^infty (-1)^{t+k} / (2^t t! k!)
  101.      = [\sum_{k=0}^\infty (-1)^k / k!] * [\sum_{t=0}^\infty (-1)^t / (2^t t!)]
  102.      = exp(-1) exp(-1/2)
  103.  
  104. So
  105.  
  106.    \lim_{n\to\infty} (1 - F(0)/D(n)) = 1 - exp(-1/2) = 0.393469340287
  107.  
  108.                                         David desJardins
  109.