2020-09 Displacement of permutations

For a permutation π:[n][n], we define the displacement of π to be i[n]|iπ(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