PUMaC 2012 · 组合（A 组） · 第 8 题

PUMaC 2012 — Combinatorics (Division A) — Problem 8

[ 8 ] Proctors Andy and Kristin have a PUMaC team of eight students labelled s , s , . . . , s 1 2 8 (the PUMaC staff being awful with names). The following occurs:

解析

Consider the permutation α = (1854)(2367) corresponding to the mapping x 7 → 3 ( x − 1) ≡ − 1 3 x − 3 on Z / 8 Z . The problem asks for the number of possible permutations π = β αβ as β − 1 ranges over S . The operation π ( β ) = β αβ is called the conjugation of α with respect to 8 β . The key fact here is that two permutations are conjugate if and only if they have the same ( ) 8 1 cycle structure. Thus, π also has two 4-cycles. There are = 35 ways to pick the elements 2 4 4! of one of the 4-cycles (the 1 / 2 since the order of the two 4-cycles does not matter), and = 6 4 2 ways to permute each of the two 4-cycles upto cyclic rotation. The answer is 35 × 6 = 1260 . We sketch a proof of the fact that conjugation preserves cycle structure. View each permutation as a function on { 1 , 2 , . . . , 8 } . Consider first when α = ( a a . . . a ) is a cycle. We claim that 1 2 n αβ = βπ where π is the cycle ( β ( a ) β ( a ) . . . β ( a )). Indeed, β ( α ( a )) = β ( a ) = π ( β ( a )), 1 2 n i i +1 i so αβ and βπ agree on all of the a ’s. For any other symbol b not in the a ’s, b is fixed by α i i and β ( b ) is fixed by π , so β ( α ( b )) = β ( b ) = π ( β ( b ), so αβ and βπ agree on all the symbols outside of the a ’s. To finish, we note that any cycle α can be written as a composition of i disjoint cycle permutations. 4