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 swapchanges the positions of two integers in the sequence. His goal is to end with 2 , 3 , . . . , 2017 , 1 . Howmany 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 swapchanges the positions of two integers in the sequence. His goal is to end with 2 , 3 , . . . , 2017 , 1 . Howmany 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 ini i ithe sequence with the b -th integer in the sequence). Draw the graph with edges ( a , b ). One cani i ishow that the result is a cycle if and only if the resulting graph is acyclic, so it must be a tree. Theren − 2
are n trees by Cayley’s formula, and for each tree, it can be made in ( n − 1)! ways (any orderingn − 2
of the edges). So the total number of ways to end with a cycle is n · ( n − 1)! . By symmetry, eachcycle can be made in the same number of ways, so in particular the cycle 2 , 3 , . . . , n, 1 can be made inn − 2
n · ( n − 1)!
n − 2 = n ways.
( n − 1)!