HMMT 二月 2012 · COMB 赛 · 第 6 题

英文解析

6. For a permutation σ of 1 , 2 , . . . , 7, a transposition is a swapping of two elements. (For instance, wecould apply a transposition to the permutation 3 , 7 , 1 , 4 , 5 , 6 , 2 and get 3 , 7 , 6 , 4 , 5 , 1 , 2 by swapping the
   1 and the 6.)
   Let f ( σ ) be the minimum number of transpositions necessary to turn σ into the permutation 1 , 2 , 3 , 4 , 5 , 6 , 7.
   Find the sum of f ( σ ) over all permutations σ of 1 , 2 , . . . , 7.
   Answer: 22212 To solve this problem, we use the idea of a cycle in a permutation. If σ is apermutation, we say that ( a a · · · a ) is a cycle if σ ( a ) = σ ( a ) for 1 ≤ i ≤ k − 1 and σ ( a ) = a .
   1 2 k i i +1 k 1
   Any permutation can be decomposed into disjoint cycles; for instance, the permutation 3 , 7 , 6 , 4 , 5 , 1 , 2,
   can be written as (1 3 6)(2 7)(4)(5). For a permutation σ , let g ( σ ) be the number of cycles in its cycledecomposition. (This includes single-element cycles.)
   Claim. For any permutation σ on n elements, f ( σ ) = n − g ( σ ).
   Proof. Given a cycle ( a a · · · a ) (with k ≥ 2) of a permutation σ , we can turn this cycle into the
   1 2 kidentity permutation with k − 1 transpositions; first we swap a and a ; that is, we replace σ with a
   1 2
   ′ ′ ′
   permutation σ such that instead of σ ( a ) = a and σ ( a ) = a , we have σ ( a ) = a and σ ( a ) = a .
   k 1 1 2 k 2 1 1
   ′
   Now, σ takes a to itself, so we are left with the cycle ( a · · · a ). We continue until the entire cycle
   1 2 nis replaced by the identity, which takes k − 1 transpositions. Now, for any σ , we resolve each cycle inthis way, making a total of n − g ( σ ) transpositions, to turn σ into the identity permutation.
   This shows that n − g ( σ ) transpositions; now let us that we cannot do it in less. We show that wheneverwe make a transposition, the value of n − g ( σ ) can never decrease by more than 1. Whenever we swaptwo elements, if they are in different cycles, then those two cycles merge into one; thus n − g ( σ ) actuallyincreased. If the two elements are in one cycle, then the one cycle splits into two cycles, so n − g ( σ )
   decreased by only one, and this proves the claim.
   Thus, we want to find
   ∑ ∑
   (7 − g ( σ )) = 7 · 7! − g ( σ )
   σ ∈ S σ ∈ S
   7 7
   to evaluate the sum, we instead sum over every cycle the number of permutations it appears in. Forn !
   any 1 ≤ k ≤ 7, the number of cycles of size k is , and the number of permutations each such
   ( n − k )! kcycle can appear in is ( n − k )!. Thus we get that the answer is
   ∑7
   7!
   7 · 7! − = 22212 .
   k =1 k
   Combinatorics Test