HMMT 二月 2012 · 冲刺赛 · 第 31 题

HMMT February 2012 — Guts Round — Problem 31

[ 19 ] Let S denote all the permutations of 1 , 2 , . . . , 7. For any π ∈ S , let f ( π ) be the smallest positive 7 7 ∑ integer i such that π (1) , π (2) , . . . , π ( i ) is a permutation of 1 , 2 , . . . , i . Compute f ( π ). π ∈ S 7

解析

[ 19 ] Let S denote all the permutations of 1 , 2 , . . . , 7. For any π ∈ S , let f ( π ) be the smallest positive 7 7 ∑ integer i such that π (1) , π (2) , . . . , π ( i ) is a permutation of 1 , 2 , . . . , i . Compute f ( π ). π ∈ S 7 Answer: 29093 Extend the definition of f to apply for any permutation of 1 , 2 , . . . , n , for any positive integer n . For positive integer n , let g ( n ) denote the number of permutations π of 1 , 2 , . . . , n such that f ( π ) = n . We have g (1) = 1. For fixed n, k (with k ≤ n ), the number of permutations π of 1 , 2 , . . . , n such that f ( π ) = k is g ( k )( n − k )!. This gives us the recursive formula g ( n ) = ∑ n − 1 n ! − g ( k )( n − k )!. Using this formula, we find that the first 7 values of g are 1 , 1 , 3 , 13 , 71 , 461 , 3447. k =1 ∑ 7 Our sum is then equal to k · g ( k )(7 − k )!. Using our computed values of g , we get that the sum k =1 evaluates to 29093.