We all know that the order of a permutation is the Least Common Multiples of its disjoint cycles’ lengths. Also, we know that an involution is a permutation whose order is at most 2. The number of involutions of length n can be obtained from this recurrence relation:
F[n] = F[n - 1] + (n - 1) * F[n - 2]
I’m just wondering whether we have any formula to count the number of permutations of length n whose orders are at most k (k >= 2)?