I want to count the number of permutations of the given order $k$ in $S_n\;(\sigma^k=id,\sigma^l\neq id\;for\;l<k)$. I found some works about that problem, but they are more general than necessary. May be somebody knows how the recurrence view will look($k=3$ for example).
1
-
$\begingroup$ The same question was asked in math.stackexchange.com/questions/1006752/… and math.stackexchange.com/questions/1340297/… though they don't have complete answers. $\endgroup$– Ira GesselCommented Nov 2, 2020 at 22:59
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The exponential generating function for permutations of order dividing $k$ is $$\exp\biggl(\sum_{d\mid k} \frac{x^d}{d}\biggr).$$ See, e.g., L. Moser and M. Wyman, On solutions of $x^d = 1$ in symmetric groups, Canad. J. Math., 7 (1955), 159-168. These are permutations in which every cycle length divides $k$. You can find the exponential generating function for permutations of order $k$ from this by Möbius inversion; there won't be a simpler formula.
