Superpermutation
In combinatorial mathematics, a superpermutation on n symbols is a string that contains each permutation of n symbols as a substring. The smallest superpermutations for n < 5 are 1, 121, 123121321, and 123412314231243121342132413214321, having lengths of 1, 3, 9, and 33 (sequence A180632 in the OEIS). For all n, there is a superpermutation of length 1! + 2! + … + n!, which is minimal only for n < 6.
See also
- Superpattern, a permutation that contains each permutation of n symbols as a permutation pattern
Further reading
- Ashlock, Daniel A.; Tillotson, Jenett (1993), "Construction of small superpermutations and minimal injective superstrings", Congressus Numerantium, 93: 91–98, Zbl 0801.05004
- Johnston, Nathaniel (July 28, 2013), "Non-uniqueness of minimal superpermutations", Discrete Mathematics, 313 (14): 1553–1557, Zbl 06247765, arXiv:1303.4150
, doi:10.1016/j.disc.2013.03.024, retrieved March 16, 2014 - Houston, Robin (21 August 2014), Tackling the Minimal Superpermutation Problem, arXiv:1408.5108
External links
This article is issued from
Wikipedia.
The text is licensed under Creative Commons - Attribution - Sharealike.
Additional terms may apply for the media files.