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, arXiv:1303.4150
, doi:10.1016/j.disc.2013.03.024, Zbl 06247765, 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 - version of the 8/24/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.