Just for fun

Some one ask me to count the number of element in the set $\{\sigma\in S_5:|\sigma|=2\}$, after doing that I follow the same idea to count $|\{\sigma\in S_n:|\sigma|=2\}|$, and a step further I count $|\{\sigma\in S_n:|\sigma|=p\}|$, $p\leq n$, and I get $$\sum_{k=1}^{[\frac{n}{p}]}\frac{\big((p-1)!\big)^{k}}{(k)!}\prod_{r=0}^{k-1}\binom{n-pr}{p}.$$

The result is summarized in the following document (I hope the result is true):
http://ihome.ust.hk/~cclee/document/sthgen.pdf

To ``verify" the result, let's count $L(n,3)$ in another way, we count this by considering $a_n$ defined by
$$a_n=\frac{1}{3}\times \underbrace{\binom{n}{2}}_{\text{choose 2 elements}\atop \text{to form permutation}}\underbrace{\binom{2}{1}}_{\text{choose 1 of the first two}\atop\text{ chosen numbers}}\underbrace{\binom{n-2}{1}}_{\text{choose another 1 to form permutation}\atop\text{with the number in 2C1 }}.$$

The factor $\frac{1}{3}$ is left there becasue we observe that every length 3 permutation can be written as product of 2 transpositions in exactly 3 ways.

Then clearly the number of ways to form order $3$ permutation by multiplying $k$ disjoint length 3 cycles is given by $$\frac{\prod_{r=0}^{k-1}a_{n-3r}}{(k)!}=\frac{2^{k}}{(k)!}\prod_{r=0}^{k-1}\binom{n-3r}{3},$$ exactly the same summand appear.