# What is the number of $(2n)$-permutations whose longest cycle is of length $n$? (verification)

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?

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)$$

• Thanks! Clearly, I overlooked the problem. – thetraveller Oct 27 '18 at 1:22
• Nevertheless, on the whole, you were on the right track. – quasi Oct 27 '18 at 1:23