- Последовательность де Брейна
-
Последовательность де Бре́йна[1] — последовательность , элементы которой принадлежат заданному конечному множеству (обычно рассматривают множество ), и все подпоследовательности заданной длины n, различны.
Часто рассматриваются периодические последовательности с периодом T, содержащие T различных подпоследовательностей — то есть такие периодические последовательности, в которых любой отрезок длины T + n − 1 является последовательностью де Брейна с теми же параметрами n и k.
Очевидно, что длина (период) такого цикла не может превосходить числа kn всех различных векторов длины n с элементами из ; несложно доказать, что эта оценка достигается. Циклы этой максимально возможной длины обычно называют циклами де Брейна (впрочем, иногда этот термин применяют и к циклам меньшей длины).
Примеры циклов де Брейна для k = 2 с периодом 2, 4, 8, 16:
- 01 (содержит подпоследовательности 0 и 1)
- 0011 (содержит подпоследовательности 00, 01, 11, 10)
- 00010111 (000, 001, 010, 101, 011, 111, 110, 100)
- 0000100110101111
Циклы де Брейна названы по имени голландского математика Н. Г. де Брeйна (англ.) (англ. Nicolaas Govert de Bruijn), который рассматривал их в 1946 году[2], хотя они изучались и ранее[3].
Число циклов де Брейна с параметрами n и k есть (частный случай теоремы де Брейна — Эренфест (англ.) — Смита (англ.) — Тутте (англ.), BEST-теорема (англ.)).
Существует удобная интерпретация последовательностей и циклов де Брейна, основанная на так называемом графе де Брейна — ориентированном графе с kn вершинами, соответствующими kn различных наборов длины n с элементами из , в котором из вершины в вершину ребро ведёт в том и только том случае, когда xi = yi − 1 (); при этом самому ребру можно сопоставить набор длины n + 1: . Для такого графа не проходящие дважды через одно и то же ребро эйлеровы пути (эйлеровы циклы) соответствуют последовательности (циклу) де Брейна с параметрами n + 1 и k, а не проходящие дважды через одну и ту же вершину гамильтоновы пути (гамильтоновы циклы) — последовательности (циклу) де Брейна с параметрами n и k.
При k = 2 существуют такие циклы де Брейна с длиной, на единицу меньшей максимума, которые выражаются линейными рекуррентными соотношениями порядка n: так, при n = 3 соотношение xn = xn − 2 + xn − 3(mod 2) порождает последовательности с периодом 7, например 0010111001011100… (цикл де Брейна 0010111). На основе таких последовательностей построен, в частности, циклический избыточный код CRC32 (EDB88320).
Примечания
Категории:- Комбинаторика
- Ряды и последовательности
Wikimedia Foundation. 2010.