Construction of small superpermutations and minimal injective superstrings. (English) Zbl 0801.05004

Summary: A superpermutation is a string over an alphabet \(\mathcal A\) that contains every permutation of the elements of \(\mathcal A\) as a contiguous substring. In this paper, we present a recursive construction for a very small superpermutation on the alphabet \({\mathcal A}= \{1,2,\dots,n\}\). We also treat the case where every string of length \(k< n\) with no repeated characters is to appear as a contiguous substring. Such a string is called an injective superstring on strings of length \(k\) over \(\mathcal A\).


05A05 Permutations, words, matrices
05C99 Graph theory
68R15 Combinatorics on words
05C20 Directed graphs (digraphs), tournaments

Online Encyclopedia of Integer Sequences:

a(n) = Product_{k=1..n-4} (n-k-2)!^(k*k!).