Shortest sequence containing all permutations

Given an integer $n$, define $s(n)$ to be the length of the shortest sequence $S = (a_1, \cdots a_{s(n)})$ such that every permutation of $\{1,\cdots,n\}$ is a subsequence of $S$.

If $n=1$, then $S = (1)$ is the shortest sequence containing all permutations of $\{1\}$, so s(1) = 1. If $n=2$, then $S = (1, 2, 1)$ contains all permutations of $\{1,2\}$ as a subsequence, so $s(2)=3$.

Is there a general formula for $s(n)$?

Solution 1:

Just so you know, after a quick Google search I found that your question is listed as an open problem on the Open Problem Garden.

A recent partial result gives a lower bound of $n^2-2n+3$ for $s(n)$.

Solution 2:

An update: the page linked above doesn't exist anymore but the problem still seems to be open, see sequence A062714 on OEIS and references therein. The question was asked recently on mathoverflow and more information was given. I briefly report here the answer.

A better upper then the one shown above was proven by Radomirovic in 2012: $$s(n)≤⌈n^2−\frac{7}{3}n+\frac{19}{3}⌉.$$ The best lower bound seems to be the one found by Kleitman and Kwiatkowski in 1976: $$s(n)≥n^2−C_{\epsilon}n^{7/4+\epsilon},$$ where $C_{\epsilon}$ is a positive constant for any $ϵ>0$.