Solution: 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}\).

The best solution was submitted by 홍의천 (수리과학과 2017학번). Congratulations!

Here is his solution of problem 2020-09.

Another solution was submitted by 고성훈 (수리과학과 2018학번, +3).

GD Star Rating
Solution: 2020-09 Displacement of permutations, 5.0 out of 5 based on 2 ratings