Permutations with given sign

Task number: 2463

How many permutations on \(n\) elements have sign 1, and how many sign \(-1\)?

  • Resolution

    Altogethere there are \(n!\) permutations on \(n\) elements.

    Permutations with the positive sign form a subgroup. For \(n\ge 2\) exist also permutations with the negative sign (odd). These form the factorization class different from the subgroup.

    An alternative elementary argument:

    From a permutation \(p\) on \(n-1\) elements can be formed a permutation on \(n\) elements by putting \(n\) on the first, second, etc., the last \(n\)-th position. In the first case will newly appear \(n-1\) inversion, in the second \(n-2\), etc. in the last case there is no new inversion. hence \(\lceil\frac{n}{2}\rceil\) of the new permutations has the same sign as \(p\) and \(\lfloor\frac{n}{2}\rfloor\) has the opposite sign. This solves the case for an even \(n\) – there are as many odd as even permutations.

    For odd \(n\ge 3\) we must use the assumption on the same number of odd and even permutations on \(n-1\) elements, that is \(\frac{(n-1)!}{2}\).

    Then there are \( \frac{(n-1)!}{2}\lceil\frac{n}{2}\rceil+ \frac{(n-1)!}{2}\lfloor\frac{n}{2}\rfloor= \frac{n!}{2}\) even (and also odd) permutations.

  • Result

    Permutations with the positive sign are as many as those with the negative sign, i.e. \(\frac{n!}{2}\) (for \(n\ge 2\)).

Difficulty level: Easy task (using definitions and simple reasoning)
Proving or derivation task
Cs translation
Send comment on task by email