HMMT 二月 2012 · COMB 赛 · 第 6 题
HMMT February 2012 — COMB Round — Problem 6
题目详情
- For a permutation σ of 1 , 2 , . . . , 7, a transposition is a swapping of two elements. (For instance, we could 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.
解析
- For a permutation σ of 1 , 2 , . . . , 7, a transposition is a swapping of two elements. (For instance, we could 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 a permutation, 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 cycle decomposition. (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 k identity 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 n is replaced by the identity, which takes k − 1 transpositions. Now, for any σ , we resolve each cycle in this 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 whenever we make a transposition, the value of n − g ( σ ) can never decrease by more than 1. Whenever we swap two elements, if they are in different cycles, then those two cycles merge into one; thus n − g ( σ ) actually increased. 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. For n ! any 1 ≤ k ≤ 7, the number of cycles of size k is , and the number of permutations each such ( n − k )! k cycle can appear in is ( n − k )!. Thus we get that the answer is 7 ∑ 7! 7 · 7! − = 22212 . k k =1 Combinatorics Test