Answer third question in weblog post

[cristoper]

The weblog post is incomplete and doesn't talk about counting permutations with more constraints. I need to get a better handle on counting and generating functions and attempt to answer them! I ran out of time this year.

Some draft that got cut from the article:

=== More constraints

Mere derangements are fine, but what if our friends think secret santa is more fun if two people cannot be assigned to each other (that there should be no fixed points or two-cycles)? or that there should be only one cycle?

There can of course be more elaborate constraints and questions, the sorts of things investigated by https://en.wikipedia.org/wiki/Random_permutation_statistics[statistics of random permutations] and https://en.wikipedia.org/wiki/Generating_function[generating functions].

==== Single n-cycle

The easiest case is if we want to restrict assignments to a single cycle that includes all latexmath:[n] elements. A permutation with one cycle is a derangement by definition.
Choose any person in the set. There are latexmath:[n-1] remaining people to choose from to assign as their secret santa. After making that assignment there are latexmath:[n-2] remaining people to assign as the previous choice's santa. Carried out to the end we see that there are

[latexmath]
++++
\begin{align*}
&(n-1)(n-2)\cdots (n-(n-1))\
&= (n-1)!
\end{align*}
++++

possible n-cycle permutations of latexmath:[n] elements. (For five people that means there are latexmath:[4! = 24] possible single cycle secret santa assignments).

==== Counting k-cycles

• probability of a permutation containing a 2-cycle
• probability of derangement containing a k-cycle
• • black lists

[cristoper]

For help on blacklist derivation, see this math overflow question: https://math.stackexchange.com/questions/588711/secret-santa-combinatorics-with-couples