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

Послідовність де Брейна — циклічний порядок ${\displaystyle a_{1},\;\ldots ,\;a_{t}}$, елементи якого належать заданій скінченній множині (зазвичай розглядають множину ${\displaystyle \{0,\;1,\;\ldots ,\;k-1\}}$), такий, що всі його підпослідовності ${\displaystyle a_{i+1},\;\ldots ,\;a_{i+n}}$[1] заданої довжини ${\displaystyle n}$ різні.

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

Цикли названо так на честь нідерландського математика Ніколаса де Брейна, який вивчав їх 1946 році[2], хоча вони вивчалися й раніше[3].

Властивості

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

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

Приклади

Приклади циклів де Брейна для ${\displaystyle k=2}$ з періодом 2, 4, 8, 16:

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

Кількість циклів де Брейна

Кількість циклів де Брейна з параметрами ${\displaystyle n}$ і ${\displaystyle k}$ є ${\displaystyle k!^{k^{(n-1)}}/k^{n}}$ (окремий випадок теореми де Брейна — BEST-теорема^[en], названа за прізвищами де Брейна, Тетяни Еренфест, Седріка Сміта і Вільяма Татта).

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

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

Граф де Брейна широко застосовується в біоінформатиці в задачах складання геному.

Примітки

1. Якщо ${\displaystyle j>t}$, то в циклічному порядку вибирається елемент з індексом ${\displaystyle j{\bmod {t}}}$
2. de Bruijn N. G. A combinatorial problem // Koninklijke Nederlandse Akademie v. Wetenschappen. 1946. — v. 49. — pp. 758—764.
3. Flye Sainte-Marie C. Question 48 // L'intermédiaire math. — 1894. — v. 1. — pp. 107—110.