×

zbMATH — the first resource for mathematics

Universal cycles for permutations. (English) Zbl 1181.05005
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 F. Chung, P. Diaconis, and 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.

MSC:
05A05 Permutations, words, matrices
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Chung, F.; Diaconis, P.; Graham, R., Universal cycles for combinatorial structures, Discrete math., 110, 43-59, (1993) · Zbl 0776.05001
[2] de Bruijn, N.G., A combinatorial problem, Nederl. akad. wetensch., proc., 49, 758-764, (1946) · Zbl 0060.02701
[3] Jackson, B.W., Universal cycles for \(k\)-subsets and \(k\)-permutations, Discrete math., 117, 141-150, (1993) · Zbl 0783.05001
[4] A.M. Williams, Shorthand universal cycles for permutations, in: ACM-SIAM Symposium on Discrete Algorithms 2008, 2007 (submitted for publication) · Zbl 1253.68273
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.