Secret Santa is a Western Christmas tradition in which members of a group are randomly assigned another member of a group for whom they are to buy a gift. While we were doing the random assignment this year, I began considering the distribution of values for the largest cycle within the gift-giving graph.
Specifically, we can think of the people as $n$ vertices, with a directed edge from $u$ to $v$ if $v$ will receive a gift from $u$. The graph thus has the property that each edge has exactly one incoming and one outgoing edge, and would be separated into a number of connected components, each of which is a cycle. While this is not normally the case in a real-life Secret Santa exchange, we will allow self loops (i.e. a person can give a gift to him/herself)
The total number of different graphs is $n!$; the first person has a choice of $n$ people to give the gift to, the second has $n-1$ and so on.
The total number of different graphs with size $ k \ge \lceil \frac{n}{2} \rceil$ is simply $\frac{n!}{k}$. To understand why this is the case, observe that we can select the $k$ people in the size-$k$ cycle in $\binom{n}{k}$ ways; these people can be arranged in the cycle in $(k-1)!$ ways, while the remaining people can be arranged in $(n-k)!$ ways. Overall, the number of arrangements is $\binom{n}{k} (k-1)! (n-k)! = \frac{n!}{k}$
I have two questions:
- Is it true that the number of different graphs is maximized when $k = \lceil\frac{n}{2}\rceil$? (or perhaps the floor)
- what is the number of graphs with size $k < \lceil \frac{n}{2} \rceil$?
To give an idea of the numerical results, I ran a simulation with a graph with 100 vertices in Mathematica. Here are the results:
