Supersecuencia más corta de todas las permutaciones de $n$ elementos

Question

Dado un alfabeto con $n$ caracteres, ¿cuál es la secuencia más corta que contiene todos los $n!$ ¿permutaciones como subsecuentes?

Una subsecuencia puede obtenerse a partir de una secuencia eliminando cualquier carácter, por lo que es diferente de una subcadena, cuyos elementos tienen que ser contiguos en la secuencia original. Digo esto porque el problema similar de encontrar la secuencia más corta teniendo todas las permutaciones como subcadenas parece estar más estudiado, pero es diferente de lo que estoy preguntando aquí.

Algunos ejemplos de supersecuencias más cortas:

• $n=2\quad-\quad121$ (longitud 3)
• $n=3\quad-\quad1213121$ (longitud 7)
• $n=4\quad-\quad1234123142134$ (longitud 13 - no se ha demostrado que sea la más corta).

Es fácil ver que $n^2$ es un límite superior, ya que una secuencia $$12\ldots n\, 12\ldots n\, \ldots\, 12\ldots n $$ ( $n$ veces) contiene todas las permutaciones. Un límite inferior simple es $n(n+1)/2$ básicamente porque $$12\ldots n\; 12\ldots (n-1)\; 12\ldots (n-2)\;\ldots $$ es demasiado corto (esto se puede demostrar rigurosamente). ¿Se sabe algo más sobre este problema?

La pregunta se formuló en intercambio de pilas pero la respuesta dista mucho de ser satisfactoria, ya que sólo ofrece un enlace roto y ninguna referencia.

Answer 1

Esto parece ser un problema abierto. En la OEIS figura como secuencia A062714 como ha señalado Ilya. Resumiendo los resultados más importantes:

Dejemos que $m$ sea la longitud de dicha secuencia. Entonces Newey (entre otros) describe un sencillo algoritmo para generarlas con $$m = n^2 -2n +4.$$ Sin embargo, ésta no es la mejor. Radomirovic demuestra que las secuencias más cortas obedecen al límite superior más estricto de $$m \le \left\lceil n^2 - \frac73 n + \frac{19}3\right\rceil.$$ Un límite inferior mejor que el trivial mostrado por OP viene dado por Kleitman y Kwiatkowski : $$m \ge n^2 - C_\epsilon n^{7/4+\epsilon},$$ para cualquier $\epsilon > 0$ .

Answer 2

Se trata de una sugerencia para un mayor desarrollo, en lugar de una respuesta. Parece ser muy prometedor prometedor.

Obsérvese que el límite superior de n^2 puede acortarse fácilmente en 2, ya que cualquier permutación no que empiece por 1 y no termine en n no necesita esas letras del ejemplo, y por otra parte codifica una permutación más corta que no necesita las primeras n ni las últimas n letras del ejemplo.

Más generalmente, la única permutación que "necesita" todas las n^2 letras es la permutación con todas las letras descendentes: si a_i es menor que a_{i+1} entonces ponlas en la ith carrera, y ahora puedes con una serie de letras menos. Creo que se puede extender esto para cortar n-1 letras de cualquier cuando n es lo suficientemente grande.

De forma aún más general, sustituya uno de los tramos intermedios 1...n por un tramo decreciente más corto n-1...2: si ahora hay una disminución de tres o más elementos consecutivos, el más largo o quizás el "más central" tal carrera decreciente puede colocarse en el centro, y el resto de la permutación a ambos lados.

Creo que un análisis cuidadoso de las secuencias ascendentes y descendentes en las permutaciones mostrará un límite superior de n(n - sqrt(n)) utilizando un ejemplo de sqrt(n) carreras descendentes intercaladas con n- 2sqrt(n) carreras ascendentes.