Superpermutation

Distribution of permutations in a superpermutation with 3 symbols

In combinatorics, a super-permutation of n characters is a character string that contains every possible permutation , i.e. combination, of these n characters as a character string.

It was shown that for 1 ≤ n ≤ 5 the smallest super permutation is length 1! + 2! +… + N !, Well , has. For example, there are 6 permutations for the three elements { A, B, C} , namely ABC, ACB, BAC, BCA, CAB and CBA; and a smallest superpermutation, which contains all these permutations, has a length of 9 characters: CBACBCABC. ${\ displaystyle \ sum \ nolimits _ {i = 1} ^ {n} i!}$

The first five superpermutations have the lengths 1, 3, 9, 33 and 153. The strings of these permutations look like this:

1
121
123121321
123412314231243121342132413214321
123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321.

For a character set of n = 6, a shorter superpermutation than was found in 2014 . Instead of a length of 873 characters, only 872 characters were required for n = 6. It is therefore expected that for n ≥ 6, a maximum length of (1! + 2! +… + N!) - 1 is required for the shortest superpermutation: " The minimal length is still unknown for n ≥ 6, but we can show that for all n ≥ 6 it is strictly less than the conjectured length […] ”. ${\ displaystyle \ sum \ nolimits _ {i = 1} ^ {n} i!}$

On September 27, 2011, an anonymous user on the imageboard 4chan demonstrated that the shortest superpermutation for n ≥ 2 had a length of at least n! + (n - 1)! + (n - 2)! + n - 3 has. Robin Houston, Jay Pantone and Vince Vatter posted full evidence of this in the OEIS on October 25, 2018.

literature

Daniel A. Ashlock, Jenett Tillotson: Construction of small superpermutations and minimal injective superstrings. In: Congressus Numerantium. 1993, pp. 91-98, Zbl 0801.05004.
Nathaniel Johnston: Non-uniqueness of minimal superpermutations . In: Discrete Mathematics . tape 313 , no. 14 , July 28, 2013, p. 1553–1557 , doi : 10.1016 / j.disc.2013.03.024 , arxiv : 1303.4150 (Zbl 1368.05004).
Robin Houston: Tackling the Minimal Superpermutation Problem . August 21, 2014, arxiv : 1408.5108 .

Web links

The Minimal Superpermutation Problem - Nathaniel Johnston's blog
James Grime: Superpermutations - Numberphile (video) Brady Haran . Retrieved February 1, 2018.

Individual evidence

↑ Robin Houston: Tackling the Minimal Superpermutation Problem (PDF)
↑ / sci / - Science & Math. Retrieved January 2, 2019 .
↑ Anonymous 4chan Poster, Robin Houston, Jay Pantone, Vince Vatter: A lower bound on the length of the shortest superpattern. (PDF; 91.5 KB) In: OEIS. October 25, 2018, p. 3 , archived from the original on January 2, 2018 ; accessed on January 2, 2019 .

[1] Robin Houston: Tackling the Minimal Superpermutation Problem (PDF)

[2] / sci / - Science & Math. Retrieved January 2, 2019 .

[3] Anonymous 4chan Poster, Robin Houston, Jay Pantone, Vince Vatter: A lower bound on the length of the shortest superpattern. (PDF; 91.5 KB) In: OEIS. October 25, 2018, p. 3 , archived from the original on January 2, 2018 ; accessed on January 2, 2019 .