\documentclass[a4paper,12pt]{article}
\usepackage{pst-all}
\usepackage{bbm,amsmath,amsthm,amssymb}
\linespread{1.3}
\addtolength{\textheight}{15mm}
\addtolength{\textwidth}{12mm}
\addtolength{\topmargin}{-15mm}
\addtolength{\evensidemargin}{6mm}
\addtolength{\oddsidemargin}{6mm}
\parindent 0mm
\title{Some thoughts on the Fake Santa game}
\author{DBW}
%\date{F\"ur \.{I}lker Demirba\c{s}}
\begin{document}
\maketitle
\vskip 5cm
{\tt ABSTRACT}: In this paper we consider the Fake Santa game, in which in a group of persons each person obtains a ballot with the name of another person, for which they have to buy presents. In particular we look at the drawing of the ballots, which is a permutation of the persons of the group subject to the only rule that no person is allowed to draw his own card. In other words, the game amounts to permutations without fixed points. In these notes we give recursive formulas for the number of permutations of $n$ persons without fixed points, we consider some probabilities that naturally arise in the game and we give asymptotic formulas for the number of permutations of $n$ persons without fixed points.
\newpage
\tableofcontents
\section{Introduction: the game}
The Fake Santa game is played in the following way: Consider a group of $n$ persons. Each person writes a little ballot with its own name and falts the ballot. All ballots are collected and shuffled, such that no one can see which ballot belongs to which person. Then each person draws a ballot and has to buy presents secretly for the person whose name was on the ballot. If a person draws himself, another round of drawing ballots is necessry to ensure that nobody buys presents for himself.
We introduce the following notation: $S_n$ is the group of permutations of $n$ persons. $\Sigma_n$ is the subset of $S_n$ consisting of the permutations such that no person has itself; that is, $\Sigma_n$ is the subset of groupelements of $S_n$ without fixed points. The Fake Santa game therefore amounts to a permutation without fixed points. We write $z_n$ for the number of permutations of $n$ persons without fixed points: $z_n=|\Sigma_n|$. In section \ref{sec:formula} we give two recursive formulas to calculate $z_n$. In section \ref{sec:asymptotic} we consider asymptotic formulas for $n\to \infty$. Using these estimates it is rather easy to obtain estimates of the probabilites that nobody draws itself in the drawing of the ballots, which is done in section \ref{sec:prob}.
We call a 2-cycle a permutation of two persons; we call a 3-cycle a cyclic permutation of three persons, that is, person $A$ has drawn person $B$, person $B$ has drawn person $C$ and person $C$ has drawn person $A$. In a similar fashion we define 4-cycles, 5-cycles and so on. A 1-cycle sends a person to himself. Each permutation of $n$ persons can be written as a product of non-intersecting cycles; with non-intersecting we mean that each person only appears in one cycle -- it is easy to see that the group of $n$ persons splits into a disjoint set of cycles of varying length. In this sense the Fake Santa game amounts to a permutation of $n$ persons whose decomposition into a product of cycles contains no 1-cycles.
Looking at the group of persons that play the Fake Santa game, we can make a link with partitions without ones: The group decomposes into disjoints cycles subject to the rule that no cycles of length 1 are allowed. Consider a group of 10 persons, than the Fake Santa game can cause a decomposition into cycles of the following lengths: $10=10$, which is the whole group is one cycle, $10=8+2$, $10=7+3$, $10=6+4$, $10=6+2+2$, $10=5+5$, $10=5+3+2$, $10=4+4+2$, $10=4+3+3$, $10=4+2+2+2$, $10=3+3+2+2$, $10=2+2+2+2+2$. This exemplifies the link with partitions without one's, which will be used in section \ref{sec:parts} to obtain a way to calculate $z_n$.
\section{Recursive formulas}\label{sec:formula}
As above we consider a group of $n$ persons. The group $S_n$ has $n!$ elements. These elements can be partitioned
\begin{equation}
S_n = \biguplus_k T_{n,k}
\end{equation}
into disjoint sets $T_{n,k}$, where $T_{n,k}$ is the set of permutations in $S_n$ that have $k$ fixed points and permute the other $n-k$ points (persons) without fixed points. There are ${n \choose k} = {n \choose n-k}$ ways to choose $k$ fixed points from a set of $n$ points. There are $z_{n-k}$ permutations that leave $k$ points fixed and permute $n-k$ points without fixed points. Hence we have the following formula:
\begin{equation}\label{eq:1}
n! = \sum_{k=0}^{n} {n \choose k} z_{k}\,.
\end{equation}
From this formula we can obtain a recursive formula for the $z_n$. Easy considerations lead to $z_1=0$ (there is no sense in playing Fake Santa with yourself) and $z_2=1$ (the only thing two persons can do is exchange ballots) and from eqn.(\ref{eq:1}) for $n=0$ we get $z_0=1$. Then we can rewrite eqn.(\ref{eq:1}) as
\begin{equation}\label{eq:2}
z_n=n! - \sum_{k=0}^{n-1} {n \choose k} z_{k}\,.
\end{equation}
In this formula the $z_0$-term corresponds to subtracting the identity element, which has $n$ fixed points.
With the aid of formula (\ref{eq:2}) we obtain the following table:
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
$n$ & $z_n$ & $z_n/n!$\\ \hline
1 & 0 &0\\
2 & 1 &0.5\\
3 & 2 &0.333\\
4 & 9 &0.375\\
5 & 44& 0.367\\
6 & 265& 0.368\\
7 & 1854& 0.368 \\
8 & 14833& 0.368\\
9 & 133496& 0.368 \\
10 & 1334961& 0.368\\
\hline
\end{tabular}
\end{center}
We now prove the following formula:
\begin{equation}\label{eq:3}
z_n = nz_{n-1}+ (-1)^n\,.
\end{equation}
From the table above we see that (\ref{eq:3}) is satisfied for $n$ ranging from 1 to 10. We now proceed inductively. Assume formula (\ref{eq:3}) holds up to some positive integer $n-1$. We then show that (\ref{eq:3}) also holds for $n$. This then proves the formula for all $n$.
We calculate
\begin{equation}
\begin{split}
n! &= \sum_{k=0}^{n}{n \choose k} z_k = \sum_{k=1}^{n-1} {n \choose k}z_k ~~+ z_n+1\\
& = \sum_{k=1}^{n-1} {n \choose k}kz_{k-1}+\sum_{k=0}^{n-1} (-1)^k ~~+ z_n \\
&= \sum_{k=1}^{n-1} {n-1 \choose k-1}nz_{k-1} + \sum_{k=0}^{n} (-1)^k ~~+ z_n - (-1)^n\\
&= n \sum_{k=0}^{n-2}{n-1 \choose k} z_k ~~+ z_n - (-1)^n \\
& = n( (n-1)! - z_{n-1}) ~~+ z_n - (-1)^n \\
& = n! + ( z_n - n z_{n-1}- (-1)^{n})\,,
\end{split}
\end{equation}
where we used the identity ${n \choose k} k = {n-1 \choose k-1} n $ to obtain the third line. From the end result of the calculation we see that the final term in parenthesis has to vanish. This proves eqn.(\ref{eq:3}).
Equation (\ref{eq:3}) provides an easy way to calculate $z_n$ inductively. Also, it provides a hint for the asymptotic behavior of $z_n$, as the recursive rule for the $z_n$ resembles that of $n!$, upto the term $(-1)^n$ which will be of less importance for large $n$ and $z_n$. Hence we suspect that $z_n/n!$ tends to a number between $0$ and $1$, which we will prove in the following section.
\section{Asymptotics}\label{sec:asymptotic}
Since $z_n$ is the number of elements of a subset of $S_n$, the fraction $\beta_n = z_n/n!$ is limited by $0\leq \beta_n< 1$. We divide equation (\ref{eq:3}) by $n!$ and obtain:
\begin{equation}
\beta_n = \beta_{n-1} + \frac{(-1)^n}{n!}\,.
\end{equation}
As $\beta_0 = 1$ this equation is solved by
\begin{equation}
\beta_n = \sum_{k=0}^{n} \frac{(-1)^n}{n!}\,.
\end{equation}
Hence in the limit as $n\to \infty$ we obtain
\begin{equation}
\beta_n ~~~\longrightarrow ~~~ \sum_{k=0}^{\infty} \frac{(-1)^n}{n!}=e^{-1}\,.
\end{equation}
The result that $\beta_n \to 1/e$ means that for large $n$ the permutations $\sigma\in S_n$ that have fixed points outnumber the permutations without fixed points by a factor of approximately $e-1$. Or in other words, for large $n$ the permutations that have no fixed points constitute approximately 37\% of all permutations. From the table of the previous section we see that convergence is rather fast and good estimates with error margins of $1/1000$ are obtained for $n\geq 6$.
\section{Probabilities}\label{sec:prob}
In this section we mainly consider groups of $n$ persons with $n$ large enough.
(I) \textit{What is the probability that in a group of $n$ persons, no second round for the drawing of the ballots is needed?} The number of total permutations is $n!$, of which only $z_n$ are good permutations for the Fake Santa game. Hence $z_n/n!$ is the probability no second round is needed. This probability can be read off from the table of section \ref{sec:formula}. For $n\geq 6$ a good estimate is $1/e$ which is approximately 37\%.
(II) \textit{What is the probability that at leat two persons simply exchange ballots in the drawing?} This amounts to finding the subset of all permutations without fixed points with at least a 2-cycle. There are ${n\choose 2}$ ways to choose two persons. Then for the rest there are $z_{n-2}$ ways to permute the ballots. Hence the probability is:
\begin{equation}
{n\choose 2}\frac{z_{n-2}}{z_n} \sim \frac{n!}{(n-2)!2}\frac{(n-2)!}{n!} =\frac{1}{2}\,,
\end{equation}
where we use $z_k \sim k!/e$.
(III) \textit{What is the probability that at least one 3-cycle appears? That is, how probable is it, that there are three persons $A$, $B$ and $C$ in the group, such that $A$ has drawn the ballot of $B$ and $B$ has drawn the ballot of $C$ and $C$ has drawn the ballot of $A$?} Similar reasoning as above, except for taking into account that for three persons there are 2 possible 3-cycles, leads to
\begin{equation}
2{n\choose 3}\frac{z_{n-3}}{z_n} \sim 2\frac{n!}{(n-3)!6}\frac{(n-3)!}{n!} =\frac{1}{3}\,.
\end{equation}
(IV) \textit{More general, what is the probability that at least one k-cycle appears?} Similar reasoning as above, except for taking into account that for $k$ persons there are $(k-1)!$ possible $k$-cycles, leads to
\begin{equation}
(k-1)!{n\choose k}\frac{z_{n-k}}{z_n} \sim (k-1)!\frac{n!}{(n-k)!k!}\frac{(n-k)!}{n!} =\frac{1}{k}\,.
\end{equation}
(V) \textit{What is the probability that in a group of $n$ persons an $n$-cycle occurs?} In a group of $n$ persons there are $(n-1)!$ possible $n$-cycle. Hence the required probability is given by:
\begin{equation}
\frac{(n-1)!}{z_n} \sim \frac{e}{n}\,.
\end{equation}
\section{Partitions without one's}\label{sec:parts}
It is easy to convince oneself that a group of $n$ people playing the Fake Santa game decomposes into disjoint cycles: Every person has another person's ballot; person $A_1$ has the ballot of person $A_2$, who has the ballot of person $A_3$ and so on. As the group is finite, we obtain a finite chain $A_1, A_2,\ldots, A_k $ such that $A_k$ has the ballot of person $A_1$.
Hence we can see the group as a sum $n= n_1+n_2+\ldots + n_p$ for some $p$ and where the $n_i$ are natural numbers larger than 2, as no one has his own ballot. Hence there is a correspondence between the set of permutations without fixed points and the partitions without one's.
As there are $(k-1)!$ possible $k$-cycles for a chosen subset of $k$ persons, we can count $z_n$ in the following way: First we find all partitions of $n$ without one's. Then we find for each partition $n=n_1+\ldots + n_p $ the number of ways we can decompose $n$ into this partition. Then we multiply with $(n_i-1)!$ for all $n_i$ in the partition. We calculate $z_8$ to clarify the method.
We have the following partitions of $8$: $8=8$, $8=6+2$, $8=5+3$, $8=4+4$, $8=4+2+2$, $8=3+3+2$, $8=2+2+2+2$.
There are $7!$ possible $8$-cycles. Hence the partition $8=8$ contributes $7!=5040$ to the number $z_8$.
There are ${8\choose 2}$ possible ways to choose $2$ from $8$. Hence the partition $8=6+2$ contributes $5\cdot ! {8\choose 2} = 3360$ to $z_8$.
In a similar way one finds that the partition $8=5+3$ contributes $4!\cdot 3!\cdot {8\choose 3} = 2688$ to $z_8$.
There are $\tfrac{1}{2}{8\choose 4}$ ways to decompose a group of 8 persons into two groups of $4$ persons. Hence the partition $8=4+4$ contributes $\frac{1}{2}\cdot 3!\cdot 3!\cdot {8 \choose 4} = 1260$ to $z_8$.
There are ${8 \choose 4}$ ways to choose 4 persons from a group of 8 persons. There are 3 ways to split the remaining 4 into two groups of 2. Hence the partition $8=4+2+2$ contributes $ 3! \cdot {8\choose 4}\cdot 3=1260$ to $z_8$.
There are ${8\choose 2}$ ways to choose 2 persons out of 8. There are $\frac{1}{2}\cdot 5\cdot 4$ ways to split the remaining 6 into two groups of 3. This then gives a contribution of $\tfrac{1}{2}\cdot 5\cdot 4\cdot 2\cdot 2\cdot {8\choose 2}=1120$ from the partition $8=3+3+2$ to $z_8$.
Finally, to split a group of 8 into 4 groups of 2, we can first choose one person free, then we have 7 possible persons to add to the first person. Then we choose one person free from the remaining 6 and have 5 possible persons to add to this person. Then we can again choose one person free and have 3 options to add to this person and thereby we have fixed the last pair. Hence the partition $8=2+2+2+2$ contributes $7\cdot 5\cdot 3=105$ to $z_8$.
Adding all contributions we indeed obtain $14833$ possible permutations of the ballots for a group of 8 persons.
\end{document}