Universal cycles for permutations (Q1044883)

A word \(u_1u_2\ldots u_{n!}\) is called a universal cycle for \(S_n\) if there is exactly one \(u_{i+1}u_{i+2}\ldots u_{i+n}\) order-isomorphic to each permutation in \(S_n\). The author shows how to construct a universal cycle for \(S_n\) using only \(n+1\) letters. This is best possible and proves a conjecture of \textit{F. Chung, P. Diaconis}, and \textit{R. Graham} [Discrete Math. 110, No.1-3, 43--59 (1992; Zbl 0776.05001)]. Moreover, bounds on the number of universal cycles for \(S_n\) over the alphabet \(\{0,1,\ldots,n\}\) are given.