An N person class?! Now that's really deranged!

If there are $N$ students in the class, where $N$ is some large number, how likely is it that they form a single loop that includes the entire class, in terms of $N$?

In the classic problem, we actually went through the various types of assignments that could work, but even there we showed roughly enough to know that the number of single loop gift exchange assignments is $(N-1)!$. The somewhat trickier piece is for the total number of all acceptable gift exchange assignments. Here, if you were paying attention to the titles of these posts, you might have been alerted to the fact that an acceptable gift exchange assignment, that is a permutation where no number is assigned to itself, is called a derangement. The number of derangements of $N$ elements is sometimes called the sub-factorial, denoted $!N,$ which can be shown to have the formula $$!N = N!\sum_{i=0}^N \frac{(-1)^i}{i!}.$$ Thus, we see that the probability of having a single loop for some large number $N$ students is $$\frac{(N-1)!}{N! \sum_{i=0}^N \frac{(-1)^i}{i!} } \approx \frac{e}{N}$$ as $N \to \infty,$ since $\sum_{i=0}^\infty \frac{(-1)^i}{i!} = e^{-1}.$

You know, it honestly takes a smidgeon of the fun out of knowing the solution, rather than doing much work for it. So, I dunno, maybe let's derive the formula $$!N = N! \sum_{i=0}^N \frac{(-1)^i}{i!}.$$ Let $U$ be the set of all inappropriate gift exchange assignments, that is where someone receives themselves as the giftee. In particular, for each $k = 1, \dots, N,$ let $U_k$ be the set of assignments where $k$ receives herself as the giftee. Using the inclusion/exclusion principle, we have \begin{align*}|U| = |U_1 \cup U_2 \cup \dots \cup U_N| &= \sum_{i=1}^N |U_i| -\sum_{1 \leq i \lt j \leq N} |U_i \cap U_j| \\ &\quad\quad\quad+ \sum_{1 \leq i \lt j \lt k \leq N} |U_i \cap U_j \cap U_k | + \dots \\ &\quad\quad\quad\quad+ (-1)^{N+1} |U_1 \cap U_2 \cap \dots \cap U_N|.\end{align*} Now the $k$ summand in the above formula, e.g., $|U_{i_1} \cap U_{i_1} \cap \dots \cap U_{i_k}|$ counts all permutations where $i_1 \lt i_2 \lt \dots \lt i_k$ receive themselves as giftees leaving the other $N-k$ students free to explore all possible permutations. Therefore, we have $|U_{i_1} \cap \dots \cap U_{i_k}| = (N-k)!$, which is coupled with the fact that there are $\binom{N}{k}$ ways of choosing $i_1, \dots, i_k.$ So we have \begin{align*}|U| &= \binom{N}{1} (N-1)! - \binom{N}{2} (N-2)! + \dots + (-1)^{N+1} 0! \\ &= \sum_{i=1}^N (-1)^{i+1} \binom{N}{i} (N-i)! \\ &= N! \sum_{i=1}^N \frac{(-1)^{i+1}}{i!}.\end{align*} Since the number of total derangements would be the number of all permutations minus the non-derangements, we get $$!N = N! - |U| = N! \left(1 - \sum_{i=1}^N \frac{(-1)^{i+1}}{i!}\right) = N! \left( 1 + \sum_{i=1}^N \frac{(-1)^i}{i!} \right) = N! \sum_{i=0}^N \frac{(-1)^i}{i!}.$$ Pretty neat, if not anticlimactic, I guess.