1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! Clearly, I overlooked the problem. $\endgroup$ – thetraveller Oct 27 '18 at 1:22
  • $\begingroup$ Nevertheless, on the whole, you were on the right track. $\endgroup$ – quasi Oct 27 '18 at 1:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.