Minimum length of a superpermutation

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

For $n\in\mathbb N$, let $[n]=\{1,\ldots,n\}$. A word $w=w_1\cdots w_L$ with $w_i\in[n]$ is a superpermutation if every permutation $(\sigma(1),\ldots,\sigma(n))$ of $[n]$ occurs as $n$ consecutive letters of $w$; that is, for every $\sigma\in S_n$ there is an integer $j$ with $1\le j\le L-n+1$ such that $w_{j+k-1}=\sigma(k)$ for $1\le k\le n$. Put \[ s(n)=\min\{L:\text{a superpermutation on }[n]\text{ has length }L\}. \] The minimum exists, since concatenating all permutations produces a word with the required property.

Statement recorded in the supplied source.

Determine $s(n)$ exactly for every integer $n\ge6$. The problem asks for the optimum, rather than the length of a particular construction. Houston's length-$872$ construction at $n=6$ disproves the earlier proposed formula $\sum_{k=1}^{n}k!$, whose value at $n=6$ is $873$. [S2]

Short English statement

Find the shortest word containing every ordering of $n$ distinct symbols as a consecutive block, for each $n>5$.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3200005 (AMR-031-0005). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Robin Houston, Tackling the Minimal Superpermutation Problem (2014), §§1–3. https://arxiv.org/abs/1408.5108.