From: desj@ccr-p.ida.org (David desJardins)
Newsgroups: sci.math
Subject: Re: The Mathematics of Secret Santa
Date: 18 Dec 92 23:21:05 GMT
Organization: IDA Center for Communications Research, Princeton

Eric Blom <blom@husc15.harvard.edu> writes:
>What is the probability that in a Secret Santa arrangement of n people, there
>is at least one pair of participants with each other as Secret Santas?

>No participant may have himself.

As usual, the problem is most easily solved by inclusion-exclusion.

Let D(m) be the number of derangements of m items (permutations with no
fixed points).  As is well known (also by inclusion-exclusion) this is

   D(m) = \sum_{k=0}^m (-1)^k m!/k!

Now fix n.  Let T be a collection of t distinct 2-sets from {1,...,n}.
Let E(T) be the number of derangements of {1,...,n} which contain each
2-set in S as a 2-cycle (and possibly also some other 2-cycles).  Then
clearly

   E(T) = D (n - 2t)

because 2t values of the permutation are fixed and map to themselves as
a set, and the remainder are free to be any derangement of the remaining
points.

Now let S be a similar collection of s distinct 2-sets from {1,...,n}.
Let F(S) be the number of derangements of {1,...,n} which contain each
2-set in S as a 2-cycle, and no other 2-cycles.  Clearly

   E(T) = \sum_{S\supseteq T} F(S)

because if we fix T to be the set of required 2-cycles, then the set of
actual 2-cycles S must contain T.

By the inclusion-exclusion formula:

   F(S) = \sum_{T\supseteq S} (-1)^{|T|-|S|} E(T).

Now, the probability you asked for is 1-F(0)/D(n), where 0 is the
empty set.  The number of sets T of cardinality t which contain 0 is

   n! / (2^t t! (n-2t)!)

Thus the formula for F(0) becomes

   F(0) = \sum_{t=0}^{n/2} (-1)^t n! / (2^t t! (n-2t)!) D(n-2t)
        = \sum_{t=0}^{n/2} \sum_{k=0}^{n-2t} (-1)^{t+k} n! / (2^t t! k!)
        = \sum_{k=0}^n \sum_{t=0}^{(n-k)/2} (-1)^{t+k} n! / (2^t t! k!)

(You can choose whichever of the last two lines you find simpler as the
"answer".)

A quick table:

        n       D(n)    F(0)    Prob
        ----    ----    ----    ------
        2       1       0       1.0000
        3       2       2       0.0000
        4       9       6       0.3333
        5       44      24      0.4545
        6       265     160     0.3962
        7       1854    1140    0.3851
        8       14833   8988    0.3940
        9       133496  80864   0.3943
        10      1334961 809856  0.3933

> For the record, here are the first few values of P(n)*!n, which should be the
> numerator of the fraction:
> 
> !2*P(2) = 1
> !3*P(3) = 0
> !4*P(4) = 3
> !5*P(5) = 20
> !6*P(6) = 105
> !7*P(7) = 504

I think Eric's table was right up to n=6, but wrong for n=7.

Finally it is interesting to note that, from the formula, it is easy to
compute the limit of the probability as n goes to infinity.  It is well
known (and obvious from the formula) that

   \lim_{n\to\infty} D(n)/n! = exp(-1)

But, by placing suitable bounds on the rate of convergence (which
details I omit here), we can show that

   \lim_{n\to\infty} F(0)/n!
     = \lim_{n\to\infty} \sum_{k=0}^n \sum_{t=0}^{(n-k)/2} (-1)^{t+k} / (2^t t! k!)
     = \sum_{k=0}^\infty \sum_{t=0}^infty (-1)^{t+k} / (2^t t! k!)
     = [\sum_{k=0}^\infty (-1)^k / k!] * [\sum_{t=0}^\infty (-1)^t / (2^t t!)]
     = exp(-1) exp(-1/2)

So

   \lim_{n\to\infty} (1 - F(0)/D(n)) = 1 - exp(-1/2) = 0.393469340287

                                        David desJardins
Newsgroups: sci.math,comp.edu,misc.education