Let $\sigma$ be a permutation of a set A. We shall say "$\sigma$ moves $a\in A$" if $\sigma(a)\neq a$. If $A$ is a finite set, how many elements are moved by a cycle $\sigma \in S_A$ of length $n$?

I am confused about the meaning of the question. A cycle can move $0-n$ element(s) in $A$. Is this correct?

Define a permutation $\sigma $ such that $\sigma(a)\neq a$ for $\forall a\in A$. Does the question mean how many this kind of permutation exist?

  • 1
    $\begingroup$ A cycle of length $n$ means a permutation of the form $\sigma = (x_1,x_2,...,x_n)$ (i.e. $\sigma(x_1)=x_2$, $\sigma(x_2)=x_3, ... ,\sigma(x_n)=x_1$ and all other elements are fixed) where $x_i$ are different elements of $A$. Now can you tell me what is the answer? $\endgroup$ – Levent Oct 9 '16 at 17:57
  • $\begingroup$ Does the text of the exercise mention "a random permutation"? $\endgroup$ – Did Oct 9 '16 at 18:29
  • $\begingroup$ @Levent So the answer is n? $\endgroup$ – User90 Oct 9 '16 at 18:46
  • $\begingroup$ @Did No. That's the whole problem. $\endgroup$ – User90 Oct 9 '16 at 18:48
  • $\begingroup$ Yes, the answer is $n$. $\endgroup$ – Levent Oct 9 '16 at 18:48

As discussed in the comments, the answer to your question is that a cycle of length $n$ "moves" exactly $n$ elements, i.e. exactly $n$ elements are not left fixed.

In general, we know we can factor a permutation $\sigma$ as a product of disjoint cycles, say of lengths $p_1,p_2,\ldots,p_k$. We can ask the same question: how many elements does $\sigma$ move? The answer is $$p_1+\cdots+p_k$$ It's as simple as that.


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.