Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
5  
Too bad you're not writing for a Putnam. This screams B1. –  jspecter Jul 1 '11 at 2:44
3  
Somewhat related: De Bruijn Sequence. –  Aryabhata Jul 1 '11 at 16:37

2 Answers 2

up vote 10 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)$.

share|improve this answer
    
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
1  
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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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