HMMT 二月 2013 · COMB 赛 · 第 9 题
HMMT February 2013 — COMB Round — Problem 9
题目详情
- Given a permutation σ of { 1 , 2 , . . . , 2013 } , let f ( σ ) to be the number of fixed points of σ – that is, the number of k ∈ { 1 , 2 , . . . , 2013 } such that σ ( k ) = k . If S is the set of all possible permutations σ , compute ∑ 4 f ( σ ) . σ ∈ S (Here, a permutation σ is a bijective mapping from { 1 , 2 , . . . , 2013 } to { 1 , 2 , . . . , 2013 } .)
解析
- Given a permutation σ of { 1 , 2 , . . . , 2013 } , let f ( σ ) to be the number of fixed points of σ – that is, the number of k ∈ { 1 , 2 , . . . , 2013 } such that σ ( k ) = k . If S is the set of all possible permutations σ , compute ∑ 4 f ( σ ) . σ ∈ S (Here, a permutation σ is a bijective mapping from { 1 , 2 , . . . , 2013 } to { 1 , 2 , . . . , 2013 } .) Answer: 15(2013!) First, note that ∑ ∑ ∑ 4 f ( σ ) = g ( σ, a , a , a , a ) , 1 2 3 4 σ ∈ S σ ∈ S 1 ≤ a ,a ,a ,a ≤ 2013 1 2 3 4 where g ( σ, a , a , a , a ) = 1 if all a are fixed points of σ and 0 otherwise. (The a ’s need not be 1 2 3 4 i i distinct.) Switching the order of summation, we find that the desired sum is ∑ ∑ g ( σ, a , a , a , a ) . 1 2 3 4 1 ≤ a ,a ,a ,a ≤ 2013 σ ∈ S 1 2 3 4 Combinatorics Test Note that the inner sum is equal to the number of permutations on { 1 , 2 , . . . , 2013 } that fix a , a , a , 1 2 3 and a . This depends on the number of distinct values the a s take. If they take on exactly k distinct 4 i values, then the inner sum will evaluate to (2013 − k )!, because σ can be any permutation of the remaining 2013 − k elements. (For example, if a = a but a , a , and a are distinct, the inner sum 1 2 1 3 4 is 2010! because σ can be any permutation that fixes a , a , and a .) 1 3 4 Now, suppose we are given which of the a are equal (for example, we could be given a = a but i 1 2 a , a , a mutually distinct, as per the above example). Assuming there are k distinct values among 1 3 4 the a , there are 2013(2013 − 1) · · · (2013 − k + 1) ways to choose the a . At this point, there are i i (2013 − k )! ways to choose σ on the remaining (2013 − k ) values such that it fixes the a , for a total i of 2013! choices for ( σ, a , a , a , a ) such that g ( σ, a , a , a , a ) = 1 and the a satisfy the correct 1 2 3 4 1 2 3 4 i equality relations. Thus the answer is 2013! times the number of ways to choose equivalence classes on the a , so the i problem reduces to finding the number of ways to partition 4 elements into nonempty sets. This process can be accelerated by doing casework based on the number of sets: (a) One set must contain all four elements, only one possibility. (i.e. all the a s are equal) i (b) Either one set contains 3 elements and the other contains the fourth (4 possibilities) or one set contains 2 elements and the other contains the other two (3 possibilities). (i.e. there are two distinct values of a ) i ( ) 4 (c) One set contains two elements, the other two each contain one. There are = 6 ways to choose 2 the two elements in the set with two elements, and this uniquely determines the partition. (i.e. there are three distinct values of a ) i (d) All sets contain one element, in which case there is only one possibility. (i.e. all the a are distinct) i Thus the number of ways to construct such a partition is 1 + 4 + 3 + 6 + 1 = 15, and our answer is 15 · 2013!.