HMMT 二月 2016 · 代数 · 第 9 题

英文解析

9. For any positive integer n , S be the set of all permutations of { 1 , 2 , 3 , . . . , n } . For each permutationnπ ∈ S , let f ( π ) be the number of ordered pairs ( j, k ) for which π ( j ) > π ( k ) and 1 ≤ j < k ≤ n .
   Further define g ( π ) to be the number of positive integers k ≤ n such that π ( k ) ≡ k ± 1 (mod n ).n
   Compute
   ∑
   f ( π )+ g ( π )
   ( − 1) .
   π ∈ S
   Proposed by: Ritesh Ragavender 999
   Answer: 995 × 2998
   Define an n × n matrix A ( x ) with entries a = x if i ≡ j ± 1 (mod n ) and 1 otherwise. Letn i,j
   ∑ ∏
   π ( u ) − π ( v )
   f ( π ) g ( π ) f ( π )
   F ( x ) = ( − 1) x (here ( − 1) gives the sign of the permutation π ). Note byπ ∈ Su − vnconstruction that F ( x ) = det( A ( x )).
   − 1 n
   We find that the eigenvalues of A ( x ) are 2 x + n − 2 (eigenvector of all ones) and ( x − 1)( ω + ω ),
   n jj
   2 πjinwhere ω = e , for 1 ≤ j ≤ n − 1. Since the determinant is the product of the eigenvalues,
   ( )jn − 1
   ∏
   2 πkn − 1 n − 1
   F ( x ) = (2 x + n − 2)2 ( x − 1) cos .
   k =1 n
   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.)