HMMT 二月 2017 · 冲刺赛 · 第 29 题

HMMT February 2017 — Guts Round — Problem 29

[ 17 ] Yang has the sequence of integers 1 , 2 , . . . , 2017. He makes 2016 swaps in order, where a swap changes the positions of two integers in the sequence. His goal is to end with 2 , 3 , . . . , 2017 , 1 . How many different sequences of swaps can Yang do to achieve his goal?

解析

[ 17 ] Yang has the sequence of integers 1 , 2 , . . . , 2017. He makes 2016 swaps in order, where a swap changes the positions of two integers in the sequence. His goal is to end with 2 , 3 , . . . , 2017 , 1 . How many different sequences of swaps can Yang do to achieve his goal? Proposed by: Yang Liu 2015 Answer: 2017 Let n = 2017 . The problem is asking to write a cycle permutation of n integers as the product of n − 1 transpositions. Say that the transpositions Yang uses are ( a , b ) (i.e. swapping the a -th integer in i i i the sequence with the b -th integer in the sequence). Draw the graph with edges ( a , b ). One can i i i show that the result is a cycle if and only if the resulting graph is acyclic, so it must be a tree. There n − 2 are n trees by Cayley’s formula, and for each tree, it can be made in ( n − 1)! ways (any ordering n − 2 of the edges). So the total number of ways to end with a cycle is n · ( n − 1)! . By symmetry, each cycle can be made in the same number of ways, so in particular the cycle 2 , 3 , . . . , n, 1 can be made in n − 2 n · ( n − 1)! n − 2 = n ways. ( n − 1)!