Using Recurrence Relations to Count Certain Elements in Symmetric Groups

We use the fact that certain cosets of the stabilizer of points are pairwise conjugate in a symmetric group Snin order to construct recurrence relations for enumerating certain subsets ofSn . Occasionally one can find ‘closed form’ solutions to such recurrence relations. For example, the probability that a random element of Snhas no cycle of length divisible by q is ∏d = 1⌊n / q⌋(1 − 1dq).