HMMT 二月 2016 · 代数 · 第 9 题

HMMT February 2016 — Algebra — Problem 9

For any positive integer n , S be the set of all permutations of { 1 , 2 , 3 , . . . , n } . For each permutation n π ∈ S , let f ( π ) be the number of ordered pairs ( j, k ) for which π ( j ) > π ( k ) and 1 ≤ j < k ≤ n . n Further define g ( π ) to be the number of positive integers k ≤ n such that π ( k ) ≡ k ± 1 (mod n ). Compute ∑ f ( π )+ g ( π ) ( − 1) . π ∈ S 999

解析

For any positive integer n , S be the set of all permutations of { 1 , 2 , 3 , . . . , n } . For each permutation n π ∈ S , let f ( π ) be the number of ordered pairs ( j, k ) for which π ( j ) > π ( k ) and 1 ≤ j < k ≤ n . n Further define g ( π ) to be the number of positive integers k ≤ n such that π ( k ) ≡ k ± 1 (mod n ). Compute ∑ f ( π )+ g ( π ) ( − 1) . π ∈ S 999 Proposed by: Ritesh Ragavender 998 Answer: 995 × 2 Define an n × n matrix A ( x ) with entries a = x if i ≡ j ± 1 (mod n ) and 1 otherwise. Let n i,j ∑ ∏ π ( u ) − π ( v ) f ( π ) g ( π ) f ( π ) F ( x ) = ( − 1) x (here ( − 1) gives the sign of the permutation π ). Note by π ∈ S u − v n construction that F ( x ) = det( A ( x )). n − 1 We find that the eigenvalues of A ( x ) are 2 x + n − 2 (eigenvector of all ones) and ( x − 1)( ω + ω ), n j j 2 πji n where ω = e , for 1 ≤ j ≤ n − 1. Since the determinant is the product of the eigenvalues, j ( ) n − 1 ∏ 2 πk n − 1 n − 1 F ( x ) = (2 x + n − 2)2 ( x − 1) cos . n k =1 Evaluate the product and plug in x = − 1 to finish. (As an aside, this approach also tells us that the sum is 0 whenever n is a multiple of 4.)