2020-09 Displacement of permutations

For a permutation \(\pi: [n]\rightarrow [n]\), we define the displacement of \(\pi\) to be \(\sum_{i\in [n]} |i-\pi(i)|\).
For given \(k\), prove that the number of even permutations of \([n]\) with displacement \(2k\) minus the number of odd permutations of \([n]\) with displacement \(2k\) is \((-1)^{k}\binom{n-1}{k}\).

GD Star Rating
loading...
2020-09 Displacement of permutations, 4.0 out of 5 based on 1 rating