It seems that I write about superpermutations way too frequently, and today I’m going to continue the trend. Recall that a superpermutation is a string on n symbols that contains all n! permutations of those n symbols as contiguous substrings. For example, when n = 3, the 3! = 6 permutations of the symbols “1”, “2”, and “3” are 123, 132, 213, 231, 312, and 321, and a superpermutation is

123121321

since it contains all 6 of those permutations as substrings. That superpermutation is “minimal”: no shorter superpermutation on 3 symbols exists. We know how long minimal superpermutations are when n ≤ 5, but when n ≥ 6 determining this minimal length is still an open problem.

Somewhat surprisingly, there is a natural generalization of this problem that is actually easier to solve… in all cases except for the original case (superpermutations) that we care about. Here’s how it works: instead of requiring that the superstring contain all permutations as substrings, fix an additional parameter k that specifies the length of the substrings that it must contain. We say that a (length-k) string is injective if all of the characters in it are distinct, and we say that an injective superstring is a string that contains all injective strings (for a fixed pair of parameters n and k) as contiguous substrings. What is the minimal length of an injective superstring?

The requirement that the characters in an injective string be distinct forces the inequality k ≤ n. In the extreme case when k = n, an injective string is simply a permutation, so an injective superstring is simply a superpermutation, in which case the problem of finding a minimal one is hard. However, all other cases are easy: whenever k < n, it is known that minimal injective superstrings have length exactly equal to n!/(n-k)! + (k-1). For example, if n = 3 and k = 2 then the injective strings (strings of length 2 on the symbols “1”, “2”, and “3” in which all characters are distinct) are 12, 13, 21, 23, 31, and 32, and a minimal injective superstring (of length n!/(n-k)! + (k-1) = 6/1 + 2 = 8) is 1231321.

My latest video demonstrates how to construct minimal injective superstrings, and explains why they are so much easier to construct than minimal superpermutations: