Proof that there are $n!/2$ even permutations of [n]

Question

Let $n \geq 2$ be an integer. Prove that the number of even permutations of the set $\left[n\right] = \left\{1,2,\ldots,n\right\}$ is $n!/2$.

In my combinatorics class, we defined even permutations of [n] as having an even number of inversions - that is, an even number of pairs of entries where the larger entry precedes the smaller entry.

For example $[5,1,2,3,4,6]$ written in one-line notation is even because there are four inversions: (5,1), (5,2), (5,3), (5,4).

Is there some intuitive way to think about or prove that in general the number of even permutations of $[n]$ is $n!/2$?

Thank you for any insights!

Answer 1

First, we notice that there are $n!$ permutations of $[n]$ since the permutations are simply all the possible arrangements of ${1, 2, 3, ...n}$.

It remains to prove that the number of the odd permutations is equal to the number of even permutations. This is obvious for $n=2$, so it suffices to prove for every $n$ such that $n>2$.

For every n, denote the number of even permutations as $a$, the number of odd permutations as $b$. By definition, by adding a permutation $(1,2)$ at the end of an even permutation we will obtain an odd permutation. This holds for every even permutation so $a\leq b$. By adding a permutation $(1,2)$ at the end of an odd permutation we obtain an even permutation. This holds for every odd permutation so $b\leq a$. Thus we have $a=b$, and we have the desired result that $a=n!/2$.

Answer 2

HINT: Pair up permutation $[ a_1,a_2,a_3,a_4, \ldots, a_n]$ with the permutation $[a_2,a_1,a_3,a_4, \ldots, a_n]$ i.e., $a_1$ and $a_2$ are switched, but $a_3,a_4, \ldots, a_n$ stay the same.