Русская Википедия:Последовательность де Брёйна
Последовательность де Брёйна[1] — циклический порядок <math>a_1,\;\ldots,\;a_t</math>, элементы которого принадлежат заданному конечному множеству (обычно рассматривают множество <math>\{0,\;1,\;\ldots,\;k-1\}</math>), такой, что все его подпоследовательности <math>a_{i+1},\;\ldots,\;a_{i+n}</math>[2] заданной длины <math>n</math> различны.
Часто рассматриваются периодические последовательности с периодом <math>T</math>, содержащие <math>T</math> различных подпоследовательностей <math>a_{i+1},\;\ldots,\;a_{i+n}</math>, — то есть такие периодические последовательности, в которых любой отрезок длины <math>T+n-1</math> является последовательностью де Брёйна с теми же параметрами <math>n</math> и <math>k</math>.
Циклы названы по имени голландского математика Николаса де Брёйна, изучившего их в 1946 году[3], хотя они изучались и ранее[4].
Свойства
Очевидно, что длина (период) такого цикла не может превосходить <math>k^n</math> — числа́ всех различных векторов длины <math>n</math> с элементами из <math>\{0,\;1,\;\ldots,\;k-1\}</math>; несложно доказать, что эта оценка достигается. Циклы этой максимально возможной длины обычно называют циклами де Брёйна (впрочем, иногда этот термин применяют и к циклам меньшей длины).
При <math>k=2</math> существуют такие циклы де Брёйна с длиной, на единицу меньшей максимума, которые выражаются линейными рекуррентными соотношениями порядка <math>n</math>: так, при <math>n=3</math> соотношение <math>x_n=x_{n-2}+x_{n-3}\pmod 2</math> порождает последовательности с периодом 7, например 0010111001011100… (цикл де Брёйна 0010111). На основе таких последовательностей построен, в частности, циклический избыточный код CRC32 (EDB88320).
Примеры
Примеры циклов де Брёйна для <math>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>n</math> и <math>k</math> есть <math>k!^{k^{(n - 1)}}/k^n</math> (частный случай теоремы де Брёйна — en (BEST theorem), названная по фамилиям де Брёйна, Татьяны Эренфест, Седрика Смита и Уильяма Татта).
Граф де Брёйна
Существует удобная интерпретация последовательностей и циклов де Брёйна, основанная на так называемом графе де Брёйна — ориентированном графе с <math>k^n</math> вершинами, соответствующими <math>k^n</math> различных наборов длины <math>n</math> с элементами из <math>\{0,\;1,\;\ldots,\;k-1\}</math>, в котором из вершины <math>(x_1,\;\ldots,\;x_n)</math> в вершину <math>(y_1,\;\ldots,\;y_n)</math> ребро ведёт в том и только том случае, когда <math>x_i=y_{i-1}</math> (<math>i=2,\;\ldots,\;n</math>); при этом самому ребру можно сопоставить набор длины <math>n+1</math>: <math>(x_1,\;\ldots,\;x_n,\;y_n)=(x_1,\;y_1,\;\ldots,\;y_n)</math>. Для такого графа не проходящие дважды через одно и то же ребро эйлеровы пути (эйлеровы циклы) соответствуют последовательности (циклу) де Брёйна с параметрами <math>n+1</math> и <math>k</math>, а не проходящие дважды через одну и ту же вершину гамильтоновы пути (гамильтоновы циклы) — последовательности (циклу) де Брёйна с параметрами <math>n</math> и <math>k</math>.
Граф де Брёйна широко применяется в биоинформатике в задачах сборки генома.
Примечания
Шаблон:Последовательности и ряды
- ↑ Встречаются также написания «де Бройна» и «де Брюина».
- ↑ Если <math>j>t</math>, то в циклическом порядке выбирается элемент с индексом <math>j \bmod t</math>
- ↑ 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.
