home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / math / 17133 < prev    next >
Encoding:
Internet Message Format  |  1992-12-20  |  1.3 KB
  1. Path: sparky!uunet!ogicse!das-news.harvard.edu!husc-news.harvard.edu!blom
  2. From: blom@husc15.harvard.edu
  3. Newsgroups: sci.math
  4. Subject: The Mathematics of Secret Santa
  5. Message-ID: <1992Dec17.220416.18649@husc15.harvard.edu>
  6. Date: 18 Dec 92 03:04:16 GMT
  7. Article-I.D.: husc15.1992Dec17.220416.18649
  8. Organization: Harvard University Science Center
  9. Lines: 36
  10.  
  11. What is the probability that in a Secret Santa arrangement of n people, there
  12. is at least one pair of participants with each other as Secret Santas?
  13.  
  14. No participant may have himself.
  15.  
  16. The total number of Secret Santa arrangements turns out to be the subfactorial
  17. of the number of participants.  Here, the subfactorial of the number n is
  18. defined as
  19.                  k
  20.          n   (-1)
  21. !n = n! sum ------
  22.         k=0   k!
  23.  
  24. For example, !5 = 5! (1/0! - 1/1! + 1/2! - 1/3! + 1/4! - 1/5!)
  25.                 = 120 (1 - 1 + 1/2 - 1/6 + 1/24 - 1/120)
  26.                 = 44.
  27.  
  28. The subfactorial, I think, should be the denominator of the fraction for the
  29. probability with n people, but I can't figure out the numerator.
  30.  
  31.         ??
  32. P(n) = ----
  33.         !n
  34.  
  35. For the record, here are the first few values of P(n)*!n, which should be the
  36. numerator of the fraction:
  37.  
  38. !2*P(2) = 1
  39. !3*P(3) = 0
  40. !4*P(4) = 3
  41. !5*P(5) = 20
  42. !6*P(6) = 105
  43. !7*P(7) = 504
  44.  
  45. Eric Blom
  46. Harvard U
  47.