Superpermutation

source

An interesting problem of finding the shortest sequence of numbers in $\{1,2,\ldots,n\}$ such that each of the $n!$ permutations of $1 2\ldots n$ appears at least once without interruption in this shortest sequence. Another interesting thing about it is the discussion from Japanese anime forum, see more details.

A simple yet beautiful construction gives an upper bound of $1!+2!+\cdots+n!$ on the shortest length. I'll just list a couple of self-explanatory examples below and how induction argument would prove it is then obvious.

$1$
$\underline{1}21$
$\underline{12}312\underline{1}321$
$\underline{123}4123\underline{1}4231\underline{2}4312\underline{13}4213\underline{2}4132\underline{1}4321$