La cadena de bits universal más corta: una cadena para contener todas las demás

Question

Deje $s$ ser una cadena de bits. Tratarlo como un ciclo, con la primera poco después de la última. Decir que $s$ es universal para $n$ si todas las $2^n$ cadenas de $n$ bits se pueden encontrar en $s$ consecutivos, de izquierda a derecha los bits (con rotación). Definir $u(n)$ como la longitud de la menor de cadena universal para $n$.

Ejemplos:

$u(1)=2$: $$ \begin{matrix} \color{red}{0} & 1 \\ 0 & \color{red}{1} \end{de la matriz} $$

$u(2)=4$: $$ \begin{matrix} \color{red}{0} & \color{red}{0} & 1 & 1 \\ 0 & \color{red}{0} & \color{red}{1} & 1 \\ \color{red}{0} & 0 & 1 & \color{red}{1} \\ 0 & 0 & \color{red}{1} & \color{red}{1} \end{de la matriz} $$

$u(3)=8$:

$$ \begin{matrix} \color{red}{0} & \color{red}{0} & \color{red}{0} & 1 & 1 & 1 & 0 & 1\\ 0 & \color{red}{0} & \color{red}{0} & \color{red}{1} & 1 & 1 & 0 & 1\\ \color{red}{0} & 0 & 0 & 1 & 1 & 1 & \color{red}{0} & \color{red}{1}\\ 0 & 0 & \color{red}{0} & \color{red}{1} & \color{red}{1} & 1 & 0 & 1\\ \color{red}{0} & \color{red}{0} & 0 & 1 & 1 & 1 & 0 & \color{red}{1}\\ 0 & 0 & 0 & 1 & 1 & \color{red}{1} & \color{red}{0} & \color{red}{1}\\ 0 & 0 & 0 & 1 & \color{red}{1} & \color{red}{1} & \color{red}{0} & 1\\ 0 & 0 & 0 & \color{red}{1} & \color{red}{1} & \color{red}{1} & 0 & 1 \end{de la matriz} $$

Q1. ¿Qué es $u(n)$?

Este puede ser simple, pero el wrap-around parece que no es tan sencillo.

Q2. ¿Cuál es la generalización de las cadenas de $k$ símbolos? Deje $u(k,n)$ ser la longitud de la menor de cadena en $k$ símbolos que contiene todas las cadenas de longitud $n$.

Probablemente esto es de todos conocido...

Answer 1

Lo que estamos buscando es el relacionado con secuencias De Bruijn. La fórmula parece ser muy simple: $u(k,n) = k^n$ (y el caso especial $u(n) = 2^n$).

_{(fuente: Wikipedia, por Eviatar Bach)}