Последовательность де Брёйна

Последовательность де Брёйна — циклический порядок $a_1,\dots ,a_t$, элементы которого принадлежат заданному конечному множеству (обычно рассматривают множество $\{0,1,\dots ,k-1\}$), такой, что все его подпоследовательности $a_{i+1},\dots ,a_{i+n}$ заданной длины $n$ различны.

Часто рассматриваются периодические последовательности с периодом $T$, содержащие $T$ различных подпоследовательностей $a_{i+1},\dots ,a_{i+n}$, — то есть такие периодические последовательности, в которых любой отрезок длины $T+n-1$ является последовательностью де Брёйна с теми же параметрами $n$ и $k$.

Циклы названы по имени голландского математика Николаса де Брёйна, изучившего их в 1946 году, хотя они изучались и ранее.

Свойства

Очевидно, что длина (период) такого цикла не может превосходить $k^n$ — числа́ всех различных векторов длины $n$ с элементами из $\{0,1,\dots ,k-1\}$; несложно доказать, что эта оценка достигается. Циклы этой максимально возможной длины обычно называют циклами де Брёйна (впрочем, иногда этот термин применяют и к циклам меньшей длины).

При $k=2$ существуют такие циклы де Брёйна с длиной, на единицу меньшей максимума, которые выражаются линейными рекуррентными соотношениями порядка $n$: так, при $n=3$ соотношение $x_n=x_{n-2}+x_{n-3}(\mathrm{mod}2)$ порождает последовательности с периодом 7, например 0010111001011100… (цикл де Брёйна 0010111). На основе таких последовательностей построен, в частности, циклический избыточный код CRC32 (EDB88320).

Примеры

Примеры циклов де Брёйна для $k=2$ с периодом 2, 4, 8, 16:

• 01 (содержит подпоследовательности 0 и 1)
• 0011 (содержит подпоследовательности 00, 01, 11, 10)
• 00010111 (000, 001, 010, 101, 011, 111, 110, 100)
• 0000100110101111

Количество циклов де Брёйна

Количество циклов де Брёйна с параметрами $n$ и $k$ есть $k{!}^{k^{(n-1)}}/k^n$ (частный случай теоремы де Брёйна — Шаблон:Не переведено, названная по фамилиям де Брёйна, Татьяны Эренфест, Седрика Смита и Уильяма Татта).

Граф де Брёйна

Существует удобная интерпретация последовательностей и циклов де Брёйна, основанная на так называемом графе де Брёйна — ориентированном графе с $k^n$ вершинами, соответствующими $k^n$ различных наборов длины $n$ с элементами из $\{0,1,\dots ,k-1\}$, в котором из вершины $(x_1,\dots ,x_n)$ в вершину $(y_1,\dots ,y_n)$ ребро ведёт в том и только том случае, когда $x_i=y_{i-1}$ ($i=2,\dots ,n$); при этом самому ребру можно сопоставить набор длины $n+1$: $(x_1,\dots ,x_n,y_n)=(x_1,y_1,\dots ,y_n)$. Для такого графа не проходящие дважды через одно и то же ребро эйлеровы пути (эйлеровы циклы) соответствуют последовательности (циклу) де Брёйна с параметрами $n+1$ и $k$, а не проходящие дважды через одну и ту же вершину гамильтоновы пути (гамильтоновы циклы) — последовательности (циклу) де Брёйна с параметрами $n$ и $k$.

Граф де Брёйна широко применяется в биоинформатике в задачах сборки генома.