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)$?

up vote 11 down vote accepted

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)$.

  • Thanks, I had no idea this was a known problem. It came up in an applied context. – Fixee Jul 1 '11 at 3:17
  • [OEIS][1] has the first four terms 1,3,9,33 and suggests it may be $\sum k!$ [1]: oeis.org/A180632 – Ross Millikan Jul 1 '11 at 3:21
  • @Ross: I don't think 9 is right for $s(3)$. I think $2312321$ (length 7) contains all length-3 permutations of $\{1,2,3\}$ as subsequences. – enfield Jul 1 '11 at 3:23
  • 2
    The OEIS sequence is for substrings, not subsequences. – Yongyi Chen Jul 1 '11 at 3:27
  • @enfield: As Yongyi Chen points out, 9 is for substrings, not subsequences. – Ross Millikan Jul 1 '11 at 3:31

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$.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.