Let $a_n$ be the number of those permutation $\sigma $ on $\{1,2,…,n\}$ such that $\sigma $ is a product of exactly two disjoint cycles. Then find $a_4$ and $a_5$.
Calculating $a_4$: Possible cases which can happen are $(12)(34),(13)(24),(14)(23)$, any cycle of the form $(123)$ or $(12)$ i.e. two-cycles and three cycles thus we have in total $3+\frac{1}{3}4P_3+\frac{1}{2}4P_2=3+8+6=17$ but the correct answer is given to be either $11$ or $14$.
Where am I wrong? Please help.
Best Answer
Let $r\in[1\>..\>n-1]$ be the length of the cycle containing the number $n$. Begin the listing of this cycle with $n$. There are $(n-1)(n-2)\cdots(n-r+1)$ ways to choose the remaining entries of this cycle. Now there will be $n-r\geq1$ numbers left over, one of them the largest. Begin the listing of the second cycle with this largest left-over number, and you will then have $(n-r-1)!$ ways to choose the remaining entries of the second cycle. In all we have ${(n-1)!\over n-r}$ permutations of this kind. It follows that there are $$a_n=(n-1)!\sum_{k=1}^{n-1}{1\over k}\tag{1}$$ elements of $S_n$ having exactly two cycles. In particular this gives $a_4=11$. – Maybe the formula $(1)$ can be brought into a closed form, using some combinatorial identity.
Computing the $a_n$ we obtain the sequence $(1, 3, 11, 50, 274, 1764, 13068, 109584, 1026576,\ldots)$ which OEIS identifies as A000254.