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

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

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

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

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

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

Среди некоторых из них есть ключевые последовательности.

0011 - 2D ключ 000 до 001 ре 011 ми 111 ре 101 -

00010111 - 3D ключ 0000 до 0001 ми 0101 ре 0111 ми 0011 фа 1011 ре 1001 ми 1101 ре 1111 -

00000101100100011101010011011111 - 5D ключ 000000 до 000001 ми 000101 ре 000111 соль 010111 фа 011111 ми 011011 ре 011001 соль 001001 до 001000 ми 001100 фа 000100 соль 010100 ре 010110 ми 010010 фа 011010 соль 001010 ля 101010 фа 100010 соль 110010 ре 110000 ми 110100 фа 111100 соль 101100 ре 101110 ля 001110 фа 000110 ми 000010 ре 000000 соль 010000 фа 011000 ми 011100 ре 011110 -

Циклы де Брейна названы по имени голландского математика (англ. Nicolaas Govert de Bruijn), который рассматривал их в 1946 году, хотя они изучались и ранее.

Число циклов де Брейна с параметрами $n$ и $k$ есть $k!^{k^{(n-1)}}/k^{n}$ (частный случай теоремы де Брейна —  —  — , ).

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

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