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,
loading...