Collection of Maths Problems

Permutations with given sign

Task number: 2463

• 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\)).