In a Secret Santa game, each of $n$ players puts their name into a hat and then each player picks a name from the hat, who they buy a Christmas present for. Obviously, if someone picks their own name then they put it back and draw again (if they're the only person remaining in the hat then everyone heaves an exasperated sigh, and you start again).


My question: how many loops of present-giving do you expect to see? (e.g. A -> B -> C -> A)


More mathematically: what is the expected number of cycles in a random $n$-permutation which contains no fixed points?


The twelve-fold way doesn't appear to answer this question. Some brief Monte Carlo suggests that the limiting answer as $n\to\infty$ is $c\log n$ for some constant $c\approx 0.95$ (see attached graph, where circles are Monte Carlo approximation, straight line is $\log n$) but I'd like to see an analytical argument for this.


[alt text http://www.freeimagehosting.net/uploads/330281fbea.png](http://www.freeimagehosting.net/uploads/330281fbea.png)



Secret Santa (expected no of cycles in a random permutation)
One way to calculate the expected number of cycles of length $k$ is by the inclusion-exclusion formula. You can get the set of permuations of length $n$ with no fixed points by taking the set of permutations, subtracting the multiset of permutations with a fixed point at $i$ (for all $i$), adding the multiset of permuations with a fixed point at $i$ and $j$ (for all $i$ and $j$), etc. Let $D\_n$ be the set of permutations with no fixed points (derangements). This gives


$\{D\_n\} = \{S\_n\} -n\{S\_{n-1}\} +\frac{1}{2!}n(n-1) \{S\_{n-2}\} -\frac{1}{3!}n(n-1)(n-2)\{S\_{n-3}\} \ldots$


where $\{S\_k\}$ is the set of permutations of length $k$. Now, we can find the number of $k$-cycles on the right-hand side. The expected number of $k$-cycles in $\{S\_{n-i}\}$ is $1/k$ if $k\leq n-i$ and $0$ if $k > n-i$. If we make this replacement, and divide by the number of derangements, we find that the expected number of $k$-cycles in a derangement is


$\frac{1}{k} \cdot \frac{1 -1 +1/2! -1/3! + \ldots \pm 1/(n-k)!}{1 - 1 + 1/2! - 1/3! +\ldots \pm 1/n!}$.


One can check this formula by noting that it gives the expected number of $n-1$ cycles as 0 and the expected number of $n$-cycles as approximately $e/n$ (this is correct, since the probability that a permutation is a derangement is approximately $1/e$).


For large $n$ and $k\leq n-\log{n}$, this is almost exactly $\frac{1}{k}$. For $k > n-\log{n}$, the expected contribution of the number of cycles from long cycles is quite small, so the expected number of cycles is roughly $\sum\_{k=2}^n \frac{1}{k}$.


