2
$\begingroup$

How many permutations of $\{1, 2, \dots, n\}$ are there, such that $1$ is in a cycle of even length? I tried to solve it by using canonical cycle decomposition (i.e. we rotate every cycle so that it begins with the smallest number and we write out cycles sorted by the first element) but failed at finding a correspondence.

$\endgroup$
0

1 Answer 1

4
$\begingroup$

The number of such permutations should be $$\sum_{2\leq k\leq n \\\text{$k$ is even}}\binom{n-1}{k-1}(k-1)!(n-k)!= \sum_{2\leq k\leq n \\\text{$k$ is even}}(n-1)!=\lfloor n/2\rfloor (n-1)!$$ where $\binom{n-1}{k-1}(k-1)!$ is the number of cycles of length $k$ containing $1$, and $(n-k)!$ is the number of ways to permute the remaining elements.

$\endgroup$
1
  • 1
    $\begingroup$ Why? (Always state how you arrived at an answer, even if it is obvious) $\endgroup$
    – Moko19
    Jun 28 at 10:12

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.