CLR cover
Previous problem

Problem 14: Short Superword of Permutations

Next problem
\( \def\sa#1{\tt{#1}} \)

The goal of the problem is to show that a certain set of patterns can be packed into a single word in a space-economic way. This can be viewed as a compression technique for the specific set.

The present patterns called $n$-permutations are drawn from the alphabet of natural numbers. They are words on the alphabet $\{\sa{1},\sa{2},\dots,n\}$ in which every number from $\{\sa{1},\sa{2},\dots,n\}$ appears exactly once. The aim is to build words, called $n$-superwords, which contain all the $n$-permutations as factors.

For $n=2$ the word $\sa{121}$ is a shortest $2$-superword, since it contains the two $2$-permutations $\sa{12}$ and $\sa{21}$. For $n=3$, $\sa{123121321}$ is a shortest $3$-superword. The six $3$-permutations appear in it in the order $$\pi_1=\sa{123},\,\pi_2=\sa{231},\,\pi_3=\sa{312},\,\pi_4=\sa{213}, \,\pi_5=\sa{132},\,\pi_6=\sa{321}.$$ Note how is the structure of $\sa{123121321}$: each occurrence of letter $\sa{3}$ is flanked by two occurrences of a $2$-permutation.

The two examples of superwords are of respective lengths $\alpha_2=3$ and $\alpha_3=9$, where $\alpha_n=\sum_{i=1}^n i!$. But it is not clear whether a shortest $n$-superword is of length $\alpha_n$ for $n\geq 4$.

The problem consists in constructing a short $n$-superword, which may not be of minimal length.

Show how to construct an $n$-superword of length $\alpha_n$ for each natural number $n$.
Use this above remark on the structure of $\sa{123121321}$ to build an $n$-superword from an $(n-1)$-superword.

References

  • R. Houston. Tackling the minimal superpermutation problem. CoRR, abs/1408.5108, 2014.
  • N. Johnston. All minimal superpermutations on five symbols have been found. http://www.njohnston.ca/2014/08/all-minimal-superpermutations-on-five-symbols-have-been-found/, 2014.