16
$\begingroup$

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

  • 5
    Too bad you're not writing for a Putnam. This screams B1.2011-07-01
  • 3
    Somewhat related: [De Bruijn Sequence](http://en.wikipedia.org/wiki/De_Bruijn_sequence).2011-07-01

2 Answers 2

11

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

  • 0
    Thanks, I had no idea this was a known problem. It came up in an applied context.2011-07-01
  • 0
    [OEIS][1] has the first four terms 1,3,9,33 and suggests it may be $\sum k!$ [1]: http://oeis.org/A1806322011-07-01
  • 0
    @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.2011-07-01
  • 0
    @enfield: As Yongyi Chen points out, 9 is for substrings, not subsequences.2011-07-01
  • 0
    @Ross and anybody interested: [this question](http://math.stackexchange.com/questions/15510/what-is-the-shortest-string-that-contains-all-permutations-of-an-alphabet) is about substrings.2011-07-01
  • 2
    The OEIS sequence is for substrings, not subsequences.2011-07-01
  • 0
    9 is correct for $s^\prime(3)$ where $s^\prime$ is the substring version of the problem. It's obvious any string of this type has to be at least of length 8, so that it has enough substrings. But if it's of length 8 then every substring has to be different, so you start constructing the string 12312ohcrap. 123121321, of length 9, works.2011-07-02
  • 0
    It seems that the problem was removed from the Open Problem Garden. Do you know why? Has it been solved? And can you please provide a reference for this lower bound? I need to cite it.2014-05-02
  • 0
    As can be seen from http://oeis.org/A062714, it’s not a lower bound, but an upper bound, and one can do a bit better.2014-05-06
  • 0
    The first link in the answer is now broken2018-10-26
1

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