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

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

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

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

Свойства

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

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

Примеры

Примеры циклов де Брёйна для $k=2$ $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$ $n$ и $k$ $k$ есть $k!^{k^{(n-1)}}/k^{n}$ $k!^{{k^{{(n-1)}}}}/k^{n}$ (частный случай теоремы де Брёйна — , названная по фамилиям де Брёйна, Татьяны Эренфест , и Уильяма Татта ).

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

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

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

Примечания

Встречаются также написания «де Бройна» и «де Брюина».
Если $j>t$ $j>t$ , то в циклическом порядке выбирается элемент с индексом $j{\bmod {t}}$ $j{\bmod {t}}$
de Bruijn N. G. A combinatorial problem // Koninklijke Nederlandse Akademie v. Wetenschappen. 1946. — v. 49. — pp. 758—764.
Flye Sainte-Marie C. Question 48 // L’intermédiaire math. — 1894. — v. 1. — pp. 107—110.

[1] Встречаются также написания «де Бройна» и «де Брюина».

[2] Если $j>t$ $j>t$ , то в циклическом порядке выбирается элемент с индексом $j{\bmod {t}}$ $j{\bmod {t}}$

[3] de Bruijn N. G. A combinatorial problem // Koninklijke Nederlandse Akademie v. Wetenschappen. 1946. — v. 49. — pp. 758—764.

[4] Flye Sainte-Marie C. Question 48 // L’intermédiaire math. — 1894. — v. 1. — pp. 107—110.