'''Последовательность де Брёйна''' {{---}} последовательность <math>a_1,\;\ldots,\;a_t</math>, элементы которой принадлежат заданному конечному множеству (обычно рассматривают множество <math>\{0,\;1,\;\ldots,\;k-1\}</math>), и все подпоследовательности <math>a_{i+1},\;\ldots,\;a_{i+n}</math> заданной длины <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>.
=== Свойства ===
Очевидно, что длина (период) такого цикла не может превосходить <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). На основе таких последовательностей построен, в частности, циклический избыточный код.
=== Примеры ===
