HMMT 二月 2016 · COMB 赛 · 第 9 题

英文解析

9. Let V = { 1 , . . . , 8 } . How many permutations σ : V → V are automorphisms of some tree?
   (A graph consists of a some set of vertices and some edges between pairs of distinct vertices. It isconnected if every two vertices in it are connected by some path of one or more edges. A tree G on
   V is a connected graph with vertex set V and exactly | V | − 1 edges, and an automorphism of G is apermutation σ : V → V such that vertices i, j ∈ V are connected by an edge if and only if σ ( i ) andσ ( j ) are.)
   Proposed by: Mitchell Lee
   Answer: 30212
   We decompose into cycle types of σ . Note that within each cycle, all vertices have the same degree;
   also note that the tree has total degree 14 across its vertices (by all its seven edges).
   For any permutation that has a 1 in its cycle type (i.e it has a fixed point), let 1 ≤ a ≤ 8 be a fixedpoint. Consider the tree that consists of the seven edges from a to the seven other vertices - thispermutation (with a as a fixed point) is an automorphism of this tree.
   For any permutation that has cycle type 2 + 6, let a and b be the two elements in the 2-cycle. If the
   6-cycle consists of c, d, e, f, g, h in that order, consider the tree with edges between a and b, c, e, g andbetween b and d, f, h . It’s easy to see σ is an automorphism of this tree.
   For any permutation that has cycle type 2 + 2 + 4, let a and b be the two elements of the first two-cycle.
   Let the other two cycle consist of c and d , and the four cycle be e, f, g, h in that order. Then considerthe tree with edges between a and b , a and c , b and d , a and e , b and f , a and g , b and h . It’s easy tosee σ is an automorphism of this tree.
   For any permutation that has cycle type 2 + 3 + 3, let a and b be the vertices in the 2-cycle. One of aand b must be connected to a vertex distinct from a, b (follows from connectedness), so there must bean edge between a vertex in the 2-cycle and a vertex in a 3-cycle. Repeatedly applying σ to this edgeleads to a cycle of length 4 in the tree, which is impossible (a tree has no cycles). Therefore, thesepermutations cannot be automorphisms of any tree.
   For any permutation that has cycle type 3 + 5, similarly, there must be an edge between a vertex inthe 3-cycle and a vertex in the 5-cycle. Repeatedly applying σ to this edge once again leads to a cyclein the tree, which is not possible. So these permutations cannot be automorphisms of any tree.
   The only remaining possible cycle types of σ are 4 + 4 and 8. In the first case, if we let x and y bethe degrees of the vertices in each of the cycles, then 4 x + 4 y = 14, which is impossible for integer x, y .
   In the second case, if we let x be the degree of the vertices in the 8-cycle, then 8 x = 14, which is notpossible either.
   So we are looking for the number of permutations whose cycle type is not 2 + 2 + 3, 8, 4 + 4, 3 + 5. The
   ( ) ( )
   8 6
   1 2
   number of permutations with cycle type 2 + 2 + 3 is (2!) = 1120, with cycle type 8 is 7! = 5040,
   2 2 3
   ( ) ( )
   8 8
   1 2
   with cycle type 4 + 4 is (3!) = 1260, with cycle type 3 + 5 is (2!)(4!) = 2688. Therefore,
   2 4 3
   by complementary counting, the number of permutations that ARE automorphisms of some tree is
   8! − 1120 − 1260 − 2688 − 5040 = 30212.