Problem 816

Solution:

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_{i}, b_{i})$ (i.e. swapping the $a_{i}$-th integer in the sequence with the $b_{i}$-th integer in the sequence). Draw the graph with edges $(a_{i}, b_{i})$. One can show that the result is a cycle if and only if the resulting graph is acyclic, so it must be a tree. There are $n^{n-2}$ trees by Cayley's formula, and for each tree, it can be made in $(n-1)!$ ways (any ordering of the edges). So the total number of ways to end with a cycle is $n^{n-2} \cdot (n-1)!$. By symmetry, each cycle can be made in the same number of ways, so in particular the cycle $2,3, \ldots, n, 1$ can be made in $\frac{n^{n-2} \cdot (n-1)!}{(n-1)!} = n^{n-2}$ ways.