Show, that for a set of permutations of a set $\{1,\dots,n\}$ $(n>0)$ the following statement is true.

statement: The number of permutations where $1$ is in the same cycle with $k$, and the number of permutations where they are in different cycles, is the same.

First I tried to compute how many there are with both in one cycle.. My idea was to fix $1$ and gather permutations with property that $1$ and $k$ do not belong to one cycle. First, there are $(n−1)!$ permutations such as $1$ doesn't belong to any cycle. Then, there are $(n−2)!(n−2)$ permutations. When we sum all such permutations, we should get $\sum\limits_{k=1}^{n-1} (n-k)!$ $k = \frac{(n-k)!(n-1)n}{k} = \frac{n!}{k}$

Is that correct or am I making a mistake somewhere?

  • $\begingroup$ Think about it. A permutation either has $1$ in the same cycle as $k$ or not. Mutually exclusive, exhaustive possibilities. You have to prove that each occurs the same number of times. Therefore each set must contain exactly half of the group. How many there are supposed to be of each immediately follows. You just have to figure out why. $\endgroup$ – Matt Samuel Dec 14 '15 at 23:43
  • $\begingroup$ This was discussed at the following MSE link. $\endgroup$ – Marko Riedel Dec 15 '15 at 0:15

I'm not sure I follow your argument, but the result is wrong. We don't need to know the correct result (Marko linked to its derivation in a comment) to see that; it's enough to note that the result shouldn't depend on $k$ since all elements are created equal.


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.