Task list filter?
Task rankings
Task tags
«
«
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≥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 ⌈n2⌉ of the new permutations has the same sign as p and ⌊n2⌋ has the opposite sign. This solves the case for an even n – there are as many odd as even permutations.
For odd n≥3 we must use the assumption on the same number of odd and even permutations on n−1 elements, that is (n−1)!2.
Then there are (n−1)!2⌈n2⌉+(n−1)!2⌊n2⌋=n!2 even (and also odd) permutations.
Result
Permutations with the positive sign are as many as those with the negative sign, i.e. n!2 (for n≥2).