HMMT 二月 2016 · COMB 赛 · 第 9 题
HMMT February 2016 — COMB Round — Problem 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 is connected 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 a permutation σ : V → V such that vertices i, j ∈ V are connected by an edge if and only if σ ( i ) and σ ( j ) are.)
解析
- 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 is connected 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 a permutation σ : 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 fixed point. Consider the tree that consists of the seven edges from a to the seven other vertices - this permutation (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 and between 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 consider the 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 to see σ 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 a and b must be connected to a vertex distinct from a, b (follows from connectedness), so there must be an edge between a vertex in the 2-cycle and a vertex in a 3-cycle. Repeatedly applying σ to this edge leads to a cycle of length 4 in the tree, which is impossible (a tree has no cycles). Therefore, these permutations cannot be automorphisms of any tree. For any permutation that has cycle type 3 + 5, similarly, there must be an edge between a vertex in the 3-cycle and a vertex in the 5-cycle. Repeatedly applying σ to this edge once again leads to a cycle in 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 be the 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 not possible 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.