[Math] the number of $(2n)$-permutations whose longest cycle is of length $n$? (verification)

combinatoricspermutation-cyclespermutations

There are ${\large{\binom{2n}{n}}}$ ways to choose $n$ elements for an $n$-cycle, and there are $(n-1)!$ ways to arrange the elements of this cycle. The rest can be arranged in any number of cycles, which is $n!$.

In total there are
$${\small{\binom{2n}{n}}}{\,\cdot\,}(n-1)!{\,\cdot\,}n!=(2n)!/n$$
permutations where the longest cycle is of length $n$.

Is this correct?

Best Answer

No, your answer is not correct.

The goal is to count the number of permutations $p\in S_{2n}$ such that in the disjoint cycle representation of $p$, the maximum cycle length is $n$.

You need to worry about the case where $p$ is a product of two disjoint $n$-cycles.

Thus, consider two cases . . .

Case $(1)$:$\;$The disjoint cycle representation of $p$ has only one cycle of length $n$.

For case $(1)$, the count is $$\binom{2n}{n}{\,\cdot\,}(n-1)!{\,\cdot\,}\bigl(n!-(n-1)!\bigr)$$ Explanation:

  • The factor ${\large{\binom{2n}{n}}}$ counts the $n$-element subsets of $\{1,...,2n\}$ used to form the $n$-cycle.$\\[4pt]$
  • The factor $(n-1)!$ counts the cyclic orderings of the $n$ elements used for the $n$-cycle.$\\[4pt]$
  • The factor $n!-(n-1)!$ counts the $n!$ permutations of the remaining $n$ elements, but excludes the $(n-1)!$ permutations that would form an $n$-cycle.

Case $(2)$:$\;p$ is a product of two disjoint $n$-cycles.

For case $(2)$, the count is $$\binom{2n}{n}{\,\cdot\,}\bigl((n-1)!\bigr)^2{\,\cdot\,}\bigl({\small{\frac{1}{2}}}\bigr)$$ Explanation:

  • The factor ${\large{\binom{2n}{n}}}$ counts the $n$-element subsets of $\{1,...,2n\}$ used to form the first $n$-cycle.$\\[4pt]$
  • The factor $\bigl((n-1)!\bigr)^2$ counts the cyclic orderings of the elements for the two $n$-cycles.$\\[4pt]$
  • The factor ${\large{\frac{1}{2}}}$ corrects for the double-count, since we can freely switch the order of the two $n$-cycles, without affecting the result.

Summing the counts for the two cases, and then simplifying, we get a total count of $$ (2n-1)!{\;\cdot}\left(\frac{2n-1}{n}\right) $$

Related Question