Count the permutations which are products of exactly two disjoint cycles.

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.

Solution 1:

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.

Solution 2:

From the possible answers, it appears that the question intended to ask how many permutations have exactly two cycles in their cycle decomposition, including the $1$-cycles.

If the smaller cycle has $k$ elements, the greater has $n-k$, and $j$ particular elements can form $(j-1)!$ different $j$-cycles. Thus the desired count is

$$ \frac12\sum_{k=1}^{n-1}\binom nk(k-1)!(n-k-1)!=\frac{n!}2\sum_{k=1}^{n-1}\frac1{k(n-k)}\;, $$

where the factor $\frac12$ compensates for the double-counting of all products, including in the case of even $n$ the products of two cycles of length $\frac n2$. So we have

$$ a_4=4!\left(\frac1{1(4-1)}+\frac12\frac1{2(4-2)}\right)=24\left(\frac13+\frac18\right)=11 $$

and

$$ a_5=5!\left(\frac1{1(5-1)}+\frac1{2(5-2)}\right)=120\left(\frac14+\frac16\right)=50\;. $$