Let be a permutation of [n]. Define another permutation by switching and ; i.e., define

for .

Since and differ only by a transposition, they have opposite parity, i.e. one is odd and one is even. So we have established a bijection between the even and odd permutations, and there are equal numbers of each.