Result: Using Recurrence Relations to Count Certain Elements in Symmetric Groups: Using recurrence relations to count certain elements in symmetric groups

For the symmetric group \(S_n\), acting on the set \(\{1,\dots,n\}\), and \(k=0,1,\dots,n\), denote by \(G_{n,k}\) the subgroup of \(S_n\) that fixes each of \(1,2,\dots,k\). Set \(C_{n,k-1}=G_{n,k-1}(1,2,\dots,k)\). The author obtains recurrence relations for the number of elements in \(C_{n,k-1}\) which have orders: a multiple of a given number \(q\), dividing \(q\) and equal to \(q\), or which contain a cycle of length: a multiple of \(q\), dividing \(q\) and equal to \(q\), respectively. These relations can be solved in ``closed form''. For example, the probability that a random element of \(S_n\) has no cycle of length divisible by \(q\) is \(\prod_{d=1}^{[n/q]}(1-1/dq)\).