In this paper, we will investigate the Secret Santa problem, a combinatorics problem involving derangements with at least one two-cycle. We will first consider the probability that a permutation in a set of derangements has at least one two-cycle, and then generalize the result for derangements with at least one cycle of size q or smaller and derangements with at least one q-cycle. We will first solve for the probabilities by using recurrence relations, and will then provide them in non-recursive form. Next, we will reexamine the eight-year-old solution to the Secret Santa problem, demonstrating an error in the original authors approach. We will solve for the error term, and generalize the results. Finally, we will provide secondary results, including an enumeration of the properties of a class of recurrence relations to which derangements and n! belong.
"The Secret Santa Problem,"
Rose-Hulman Undergraduate Mathematics Journal: Vol. 7:
1, Article 5.
Available at: https://scholar.rose-hulman.edu/rhumj/vol7/iss1/5