Numer of permutations that are product of exactly two disjoint cycles

Question

Let $a_n$ denote the number of those permutations $\sigma$ on $\{1,2,3....,n\}$ such that $\sigma$ is a product of exactly two disjoint cycles. Then

1. $a_5 = 50$

2. $a_4 = 14$

3. $a_5 = 40$

4. $a_4 = 11$

I tried specifically for $a_5$ and $a_4$ with a little bit of calculations. But I want to know about a formula for $a_n$ with less calculations

Answer 1

There's a well-known formula for the number of permutations with $p_i$ cycles of length $i$ for each $i$, namely

$$ {n! \over \prod_i i^{p_i} (p_i)!}$$

(see for example this post by Mark Jason Dominus). In the case where you have one cycle of length $k$ and one of length $n-k$, and $k \not = n-k$, then you have $p_k = p_{n-k} = 1$ and this reduces to $$n! \times {1 \over k(n-k)}.$$ If $k = n-k$, that is, if $k = n/2$, then you have $p_k = 2$ and the number of such permutations is $$n! \times {2 \over n^2}.$$

For example, if $n = 5, k = 2$, the first formula gives you that there are $5!/(2 \times 3) = 20$ permutations of $[5]$ consisting of a 2-cycle and a 3-cycle. If $n = 4, k = 2$, the second formula gives you that there are $4! \times 2/4^2 = 3$ permutations consisting of two 2-cycles.

From this you can derive a general formula for the number of permutations of $n$ which are products of two disjoint cycles by summing over the possible values of $k$. If $n$ is even you'll need to handle the $k = n/2$ case separately from the rest of the sum.

(It's not clear if your definition counts a cycle of length 1 as a cycle. For example, is $(3, 5)(1, 4)(2)(6)$ a product of two distinct cycles in $S_6$? If so your sum will be more complicated but the general idea still holds.)

Answer 2

I would like to present the connection to Stirling numbers since it has not been pointed out. For the first interpretation where the cycles may be singletons we get the species $\mathfrak{P}_{=2}(\mathfrak{C}(\mathcal{Z}))$ which yields per generating function

$$n! [z^n] \frac{1}{2!}\left(\log\frac{1}{1-z}\right)^2 = \left[n\atop 2\right]$$

the sequence

$$0, 1, 3, 11, 50, 274, 1764, 13068, 109584, 1026576,\ldots $$

which is OEIS A000254 which looks to be a match. The second interpretation is when we do not admit singletons as cycles and we get the species $\mathfrak{P}_{=2}(\mathfrak{C}_{\ge 2}(\mathcal{Z}))$ which yields per generating function

$$n! [z^n] \frac{1}{2!}\left(-z + \log\frac{1}{1-z}\right)^2$$

the sequence

$$0, 0, 0, 3, 20, 130, 924, 7308, 64224, 623376,\ldots$$

which is OEIS A000276. For $n\ge 2$ this simplifies to

$$\frac{1}{2} n! [z^n] \left(z^2 - 2z \log\frac{1}{1-z} + \left(\log\frac{1}{1-z}\right)^2\right) \\ = [[n=2]] - n! [z^{n-1}] \log\frac{1}{1-z} + \left[n\atop 2\right] \\ = [[n=2]] - n \times (n-2)! + \left[n\atop 2\right].$$