# Permutations

Printable View

• September 27th 2011, 08:32 PM
jzellt
Permutations
How can I show that the number of even permutations is equal to the number of odd permutations?
• September 27th 2011, 08:39 PM
Drexel28
Re: Permutations
Quote:

Originally Posted by jzellt
How can I show that the number of even permutations is equal to the number of odd permutations?

You know that $\left[S_n:A_n\right]=2$ and so $S_n=A_n\cup xA_n$ for any $x\notin A_n$, but since all cosets have the same size this implies that $\displaystyle |A_n|=|xA_n|=\frac{n!}{2}$ but you can easily check that $xA_n$ are the odd permutations of $S_n$.

Another, essentially the same, idea is to prove that the map $\sigma\mapsto x\sigma$ is a bijection $A_n\to\{\text{odd permutations}\}$ where $x$ is any odd permutation.
• September 27th 2011, 08:46 PM
jzellt
Re: Permutations
Thanks. Is it true an odd permutation can be expressed as an even permutation and visa versa? Can you give an example of this?
• September 27th 2011, 08:47 PM
Drexel28
Re: Permutations
Quote:

Originally Posted by jzellt
Thanks. Is it true an odd permutation can be expressed as an even permutation and visa versa? Can you give an example of this?

I'm not quite sure what you mean. It's NOT true that there are permutations which are both even and odd.
• September 27th 2011, 08:55 PM
jzellt
Re: Permutations
I thought if you have a product of even transpositions, it can be "messed" with and be expressed as a product of odd transpostions... Maybe I'm way off here though...
• September 27th 2011, 09:02 PM
Drexel28
Re: Permutations
Quote:

Originally Posted by jzellt
I thought if you have a product of even transpositions, it can be "messed" with and be expressed as a product of odd transpostions... Maybe I'm way off here though...

Yeah, that's precisely what CAN'T happen, it is actually phrased the exact way you did, with the appropriate negation insereted, in most textbooks. A different way of looking at this is that there is a natural action of $S_n$ on the set $\left\{\pm \Delta\right\}$ where $\displaystyle \Delta(x)=\prod_{i and the action is $\displaystyle \sigma(\Delta)=\prod_{i. We can then think of the set of even actions as the stabilizer of $\Delta$ from where everything I've told you follows.

If you haven't done group actions yet, just ignore that.
• September 27th 2011, 09:14 PM
jzellt
Re: Permutations
A finite set with two or more elements has equal numbers of even and odd permutations.

Proof. For each even permutation, we can obtain a unique odd permutation by transposing the first two elements. This defines a one-to-one correspondence between even and odd permutations, hence there are equal numbers of each.

I found this proof somewhere. Can you explain with an example what they mean by transposing the first two elements. This is what I was meaning...
• September 27th 2011, 09:24 PM
Deveno
Re: Permutations
the key fact here is that if a permutation can be expressed as a product of an odd (resp. even) number of transpositions, it can ONLY be expressed as a product of an odd (resp.even) number of transpositions.

this is a deep fact, and one which is often used to PROVE that [Sn:An] = 2. this is equivalent to proving the "signum" (or sign) function sgn:Sn-->{-1,1} is well-defined, after which it is easy to show that |An| = |Sn|/2, and that An is normal. one way of proving this is to invoke the Vandermonde polynomial:

$p(x_1,x_2,...,x_n) = \prod_{i

and let a permutation σ in Sn act on p by taking:

$p(x_1,x_2,...,x_n) \rightarrow \prod_{i

odd permutations take p-->-p, while even permutations take p-->p.

my point is: all the difficulty is buried in ensuring that "even permutation" and "odd permutation" are well-defined terms, that we cannot have a permutation that is both. until this is done, An is not a well-defined set.

Quote:

Originally Posted by jzellt
A finite set with two or more elements has equal numbers of even and odd permutations.
Proof. For each even permutation, we can obtain a unique odd permutation by transposing the first two elements. This defines a one-to-one correspondence between even and odd permutations, hence there are equal numbers of each.
I found this proof somewhere. Can you explain with an example what they mean by transposing the first two elements. This is what I was meaning...

if we call our initial (even) permutation σ, and our second permutation τ, then this means:

τ(1) = σ(2)
τ(2) = σ(1)
τ(k) = σ(k), k = 3,4,...,n

this is equivalent to writing: τ = (σ(1) σ(2))σ.

note that τ has one more transpostion in its product than σ does.