The shortest word containing every permutation of ten symbols as a subsequence has length 83
Version 1 / Nov 19, 2026 / CC BY 4.0
Abstract
A word is universal for an alphabet if it contains every permutation of the alphabet as a subsequence. We prove that no word of length 82 is universal for ten symbols. Together with the known construction of length 83, this shows that the shortest universal word on ten symbols has length 83. The proof cuts a word at the copies of one symbol: universality is equivalent to complementary prefix and suffix conditions at consecutive copies. A counting argument confines a least frequent symbol to four, five, six or seven copies and excludes four. In the remaining cases, frequency tests reduce the possibilities to finitely many block templates, and machine-checked propositional refutations exclude every ordering of each. The computation also reproduces the nine-symbol value 66.
Provenance statement
Tools used
- Anthropic
- Claude CodeVersion Claude Opus 5.5
- OpenAI
- CodexVersion GPT-6.2-Astra
- Lean
- LeanVersion 4
References
- Leonard Adleman. Short permutation strings. Discrete Mathematics 10(2):197--200, 1974. doi:10.1016/0012-365X(74)90116-2 (https://doi.org/10.1016/0012-365X(74)90116-2).DOI
- Václav Chvátal, David A. Klarner and Donald E. Knuth. Selected combinatorial research problems . Stanford University Technical Report STAN-CS-72-292, 1972. http://infolab.stanford.edu/TR/CS-TR-72-292.html.link
- Jason Davies. Permutation supersequence length : software, proof certificates and Lean source. . This paper describes release v1.0 .
- Leonardo de Moura and Sebastian Ullrich. The Lean 4 theorem prover and programming language. In Automated Deduction -- CADE 28 , Lecture Notes in Computer Science, vol. 12699, pp. 625--635. Springer, 2021. doi:10.1007/978-3-030-79876-5_37 (https://doi.org/10.1007/978-3-030-79876-5_37).DOI
- Michael Engen and Vincent Vatter. Containing all permutations. American Mathematical Monthly 128:4--24, 2021. doi:10.1080/00029890.2021.1835384 (https://doi.org/10.1080/00029890.2021.1835384).DOI
- Vitaliy Garnashevich. Solver for OEIS A136094 . https://github.com/vsg/A136094.link
- Daniel J. Kleitman and David J. Kwiatkowski. A lower bound on the length of a sequence containing all permutations as subsequences. Journal of Combinatorial Theory, Series A 21(2):129--136, 1976. doi:10.1016/0097-3165(76)90057-1 (https://doi.org/10.1016/0097-3165(76)90057-1).DOI
- Malcolm Newey. Notes on a problem involving permutations as subsequences . Stanford Artificial Intelligence Laboratory Memo AIM-190, STAN-CS-73-340, 1973. http://infolab.stanford.edu/TR/CS-TR-73-340.html.link
- OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences , sequence A062714. https://oeis.org/A062714.link
- Saša Radomirović. A construction of short sequences containing all permutations of a set as subsequences. Electronic Journal of Combinatorics 19(4):#P31, 2012. doi:10.37236/2859 (https://doi.org/10.37236/2859).DOI
Show all 13 referencesShow fewer references
- Oliver Tan. Skip letters for short supersequence of all permutations. Discrete Mathematics 345, Article 113070, 2022. doi:10.1016/j.disc.2022.113070 (https://doi.org/10.1016/j.disc.2022.113070).DOI
- Oliver Tan. Conjecture on supersequence lower bound related to Connell sequence. arXiv:2501.11386 [math.CO], 2025. doi:10.48550/arXiv.2501.11386 (https://doi.org/10.48550/arXiv.2501.11386).arXivDOI
- Eugen Zălinescu. Shorter strings containing all -element permutations. Information Processing Letters 111(12):605--608, 2011. doi:10.1016/j.ipl.2011.03.018 (https://doi.org/10.1016/j.ipl.2011.03.018).DOI
Version history
- v1 · 8 pagesSubmitted by Jason DaviesInitial depositCurrentNov 19, 2026