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

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

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

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

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

Свойства

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

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

Примеры

Примеры циклов де Брёйна для [math]\displaystyle{ k=2 }[/math] с периодом 2, 4, 8, 16:

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

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

Количество циклов де Брёйна с параметрами [math]\displaystyle{ n }[/math] и [math]\displaystyle{ k }[/math] есть [math]\displaystyle{ k!^{k^{(n - 1)}}/k^n }[/math] (частный случай теоремы де Брёйна — BEST-теорема[en], названная по фамилиям де Брёйна, Татьяны Эренфест, Седрика Смита и Уильяма Татта).

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

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

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

Примечания

  1. Встречаются также написания «де Бройна» и «де Брюина».
  2. Если [math]\displaystyle{ j\gt t }[/math], то в циклическом порядке выбирается элемент с индексом [math]\displaystyle{ j \bmod t }[/math]
  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.