For a permutation σ=(i1,i2,…,in) of (1,2,…,n) define D(σ)=∑k=1n∣ik−k∣. Let Q(n,d) be the number of permutations σ of (1,2,…,n) with d=D(σ). Prove that Q(n,d) is even for d≥2n.
Original from the official PDF
This transcription was compared symbol by symbol with the original, but not yet by a person.
Time on this problem
Work for at least 45 minutes before opening the solution.
Official solution
Solution. Consider the n×n determinant
Δ(x)=1x⋮xn−1x1⋮xn−2……⋱…xn−1xn−2⋮1
where the ij-th entry is x∣i−j∣. From the definition of the determinant we get
where Sn is the set of all permutations of (1,2,...,n) and inv(i1,...,in) denotes the number of inversions in the sequence (i1,...,in). So Q(n,d) has the same parity as the coefficient of xd in Δ(x).
It remains to evaluate Δ(x). In order to eliminate the entries below the diagonal, subtract the (n−1)-th row, multiplied by x, from the n-th row. Then subtract the (n−2)-th row, multiplied by x, from the (n−1)-th and so on. Finally, subtract the first row, multiplied by x, from the second row.
For d≥2n, the coefficient of xd is 0 so Q(n,d) is even.
Transcribed from the official solutions, page 4. This transcription has not been checked a second time; if in doubt, look at the original.
Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.