•  
  •  
 

Abstract

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.

Author Bio

I am currently a student at Tandem Friends School in Charlottesville,Virginia. I plan on focusing on pure mathematics, especially number theory,once I enter college, although I am also interested in other subjects,including East Asian Studies. This paper has allowed me the opportunity tosolve a challenging problem, and in the process of obtaining my results Ihave learned a lot of mathematics./p>

Download

Share

COinS