Task list filter?

Choose required ranks and required tasks. The table of contents will list only tasks having one of the required ranks in corresponding rankings and at least one of the required tags (overall). If you wish to filter only according to some rankings or tags, leave the other groups empty.

Task rankings

Difficulty level

Task tags

Task type
«
«
«

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 n2 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 n1 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 n1 inversion, in the second n2, 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 n3 we must use the assumption on the same number of odd and even permutations on n1 elements, that is (n1)!2.

    Then there are (n1)!2n2+(n1)!2n2=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 n2).

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