Recurring Recurrences in Counting Permutations

We present a combinatorial proof of a recurrence that occurs in the sequence enumerating square permutations. We then generalize this result to a class of sequences, which we classify with. Finally, we explore the cause of this shared trait by analyzing the expotential genereating functions of these sequences. 1 Square Permutations The permutations on n elements form the symmetric group of order n!, called Sn. One interesting question is, which permutations can be written as the square of other permutations? We would like to characterize the set An = {π: π = σ 2, σ ∈ Sn}. Any permutation can be written as a product of disjoint cycles. Definition 1 (Cycle Type). The list of the lengths of the cycles of a permutation π is called the cycle type. For example, the cycle type of π = (5 4 1)(7)(8 2 6)(9 3) is {3, 3, 2, 1}. We can determine the cycle length of π 2 by composing the squares of all the cycles of π