HMMT 二月 2012 · 冲刺赛 · 第 31 题
HMMT February 2012 — Guts Round — Problem 31
题目详情
英文原题
[19] Let S7denote all the permutations of 1 ,2, . . . , 7. For any π∈S7, letf(π) be the smallest positive integer isuch that π(1), π(2), . . . , π (i) is a permutation of 1 ,2, . . . , i . Compute/summationtext π∈S7f(π).
解析
英文解析
- [ 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
Answer: 29093 Extend the definition of f to apply for any permutation of 1 , 2 , . . . , n , for any 7
positive integer n . For positive integer n , let g ( n ) denote the number of permutations π of 1 , 2 , . . . , nsuch 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
∑
Our sum is then equal to k · g ( k )(7 − k )!. Using our computed values of g , we get that the sum 7
k =1
evaluates to 29093.