HMMT 二月 2013 · COMB 赛 · 第 9 题

英文解析

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
   ∑
   f ( σ ) .4
   σ ∈ S
   (Here, a permutation σ is a bijective mapping from { 1 , 2 , . . . , 2013 } to { 1 , 2 , . . . , 2013 } .)
   Answer: 15(2013!) First, note that
   ∑ ∑ ∑
   f ( σ ) = g ( σ, a , a , a , a ) ,4
   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 idistinct.) 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 ivalues, then the inner sum will evaluate to (2013 − k )!, because σ can be any permutation of theremaining 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 buti 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 arei i
   (2013 − k )! ways to choose σ on the remaining (2013 − k ) values such that it fixes the a , for a totaliof 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 iequality relations.
   Thus the answer is 2013! times the number of ways to choose equivalence classes on the a , so theiproblem reduces to finding the number of ways to partition 4 elements into nonempty sets. Thisprocess 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)
   (b) Either one set contains 3 elements and the other contains the fourth (4 possibilities) or one seticontains 2 elements and the other contains the other two (3 possibilities). (i.e. there are twodistinct values of a )
   ( )i
   (c) One set contains two elements, the other two each contain one. There are = 6 ways to choose 4
   the two elements in the set with two elements, and this uniquely determines the partition. (i.e.2
   there are three distinct values of a )
   (d) All sets contain one element, in which case there is only one possibility. (i.e. all the a are distinct)ii
   Thus the number of ways to construct such a partition is 1 + 4 + 3 + 6 + 1 = 15, and our answer is
   15 · 2013!.