Why Are Half of the Permutations in Sn Even and the Other Half Odd?

[tgt]

How do we know that half of permutations are odd and half are even?

Why not 1/4, 3/4 or other proportions?

 

[enigmahunter]

First, I assume you are talking about permutations in a symmetric group.

Fact 1. Every permutation in Sn can be written as a product of transpositions.
Fact 2. A permutation in Sn (n>=2) cannot be both even and odd (number of transpositions).
Fact 3. The set of all even permutations of Sn forms a group, which is called an alternating group of degree n.

What you need to show is the above alternating group is the normal subgroup of Sn of index 2, which can be interpreted as "In Sn, one half of elements is the even permutations and the other half is odd permutations".

Define a map $$f:S_n \rightarrow C$$ by $$\sigma \mapsto sgn (\sigma)$$, where C is a multiplicative group {1, -1}.
A "sgn" denotes the http://en.wikipedia.org/wiki/Even_and_odd_permutations" , returns 1 if the permutation is even and -1 if the permutation is odd.

Now, f is surgective by the above definition of sgn and the kernel of f is An, which is normal is Sn.
By the first isomorphism theorem, $$S_n/A_n \cong C$$.
Thus, An is a normal subgroup of Sn of index 2, and it is the only subgroup of Sn of index 2 (this can be proven as well).

 

[joecoz88]

Working in Sn, define a bijection from An to Bn, where Bn is the set of all odd permutations.

f: An -> Bn
f(x)=yx where y is in Bn

You can easily show this map is a bijection, therefore An and Bn have the same cardinality. So exactly half of the permutations in Sn are even ( and the other half are odd).