Secuencia más corto que contienen todas permutaciones

Question

Dado un número entero $n$, definir $s(n)$ a ser la longitud de la menor secuencia $S = (a_1, \cdots a_{s(n)})$ tal que cada permutación de $\{1,\cdots,n\}$ es un subsequence de $S$.

Si $n=1$, entonces el $S = (1)$ es la secuencia más corta que contiene todas las permutaciones de $\{1\}$, s(1) tan = 1. Si $n=2$, entonces el $S = (1, 2, 1)$ contiene todas las permutaciones de $\{1,2\}$ como un subsequence, así $s(2)=3$.

¿Hay una fórmula general para $s(n)$?

Answer 1

Para que sepas, después de una rápida búsqueda en Google encontré que su pregunta está catalogado como un problema abierto en el Jardín de problema abierto.

Un resultado parcial reciente da un límite inferior de $n^2-2n+3$ $s(n)$.

Answer 2

Actualización: el enlace de arriba no existe, pero el problema parece estar aún abierto, ver la secuencia de A062714 en OEIS y las referencias allí contenidas. La pregunta fue hecha recientemente en mathoverflow y más información. Brevemente me presenta aquí la respuesta.

Una mejor superior, a continuación, la que se muestra arriba fue probada por Radomirovic en 2012: $$s(n)≤⌈n^2−\frac{7}{3}n+\frac{19}{3}⌉.$$ La mejor cota inferior parece ser el que se encuentra por Kleitman y Kwiatkowski en 1976: $$s(n)≥n^2−C_{\epsilon}n^{7/4+\epsilon},$$ donde $C_{\epsilon}$ es una constante positiva para cualquier $ϵ>0$.