284 6 Combinatorics and Probability
Example.Consider the permutations
σ 1 =(
1234 ···19 20
a 1 a 2 a 3 a 4 ···a 19 a 20)
,
σ 2 =(
1234 ···19 20
a 19 a 20 a 17 a 18 ···a 1 a 2)
.
Prove that ifσ 1 has 100 inversions, thenσ 2 has at most 100 inversions.
Solution.Let us see what an inversion(ai,aj)ofσ 1 becomes inσ 2 .Ifiandjhave the
same parity, thenaiandajare switched inσ 2 , and so(aj,ai)is no longer an inversion.
Ifiis even andjis odd, thenaiandajare also switched inσ 2 , so the inversion again
disappears.
We investigate the caseiodd andjeven more closely. Ifj>i+1, then inσ 2 the two
elements appear in the order(aj,ai), which is again not an inversion. However, ifiand
jare consecutive, then the pair is not permuted inσ 2 ; the inversion is preserved. There
are at most 10 such pairs, becauseican take only the values 1, 3 ,...,19. So at most 10
inversions are “transmitted’’ fromσ 1 toσ 2. From the 100 inversions ofσ 1 , at most 10
become inversions ofσ 2 , while 90 are “lost’’: they are no longer inversions inσ 2.
It follows that from the
( 20
2)
=190 pairs(ai,aj)inσ 2 withi<j, at least 90 are not
inversions, which means that at most 190− 90 =100 are inversions. This completes the
proof.
Here is a different way of saying this. Define
σ 3 =(
1234 ···19 20
a 20 a 19 a 18 a 17 ···a 2 a 1)
.
Then between themσ 1 andσ 3 have exactly
( 20
2)
inversions, since each pair is an inversion
in exactly one. Henceσ 3 has at most 90 inversions. Becauseσ 2 differs fromσ 3 by
swapping 10 pairs of adjacent outputs, these are the only pairs in which it can differ from
σ 3 in whether it has has an inversion. Henceσ 2 has at most 100 inversions.
And now an example with a geometric flavor.Example.Letσbe a permutation of the set{ 1 , 2 ,...,n}. Prove that there exist permu-
tationsσ 1 andσ 2 of the same set such thatσ=σ 1 σ 2 andσ 12 andσ 22 are both equal to the
identity permutation.
Solution.Decompose the permutationσinto a product of disjoint cycles. It suffices to
prove the property for each of these cycles; therefore, we can assume from the beginning
thatσitself is a cycle of lengthn.Ifn=1 or 2, then we chooseσ 1 =σandσ 2 the identity
permutation. Otherwise, we think ofσas the rotation of a regularn-gonA 1 A 2 ...Anby