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

Последовательность де Брёйна — последовательность <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>.

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

Свойства

Очевидно, что длина (период) такого цикла не может превосходить <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)
• 00110 (содержит подпоследовательности 00, 01, 11, 10)
• 0001011100 (000, 001, 010, 101, 011, 111, 110, 100)
• 0000100110101111

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

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

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

Существует удобная интерпретация последовательностей и циклов де Брёйна, основанная на так называемом графе де Брёйна — ориентированном графе с <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>.

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

Отрывок, характеризующий Последовательность де Брёйна

Наташа знала, что ей надо уйти, но она не могла этого сделать: что то сжимало ей горло, и она неучтиво, прямо, открытыми глазами смотрела на князя Андрея.
«Сейчас? Сию минуту!… Нет, это не может быть!» думала она.
Он опять взглянул на нее, и этот взгляд убедил ее в том, что она не ошиблась. – Да, сейчас, сию минуту решалась ее судьба.
– Поди, Наташа, я позову тебя, – сказала графиня шопотом.
Наташа испуганными, умоляющими глазами взглянула на князя Андрея и на мать, и вышла.
– Я приехал, графиня, просить руки вашей дочери, – сказал князь Андрей. Лицо графини вспыхнуло, но она ничего не сказала.
– Ваше предложение… – степенно начала графиня. – Он молчал, глядя ей в глаза. – Ваше предложение… (она сконфузилась) нам приятно, и… я принимаю ваше предложение, я рада. И муж мой… я надеюсь… но от нее самой будет зависеть…
– Я скажу ей тогда, когда буду иметь ваше согласие… даете ли вы мне его? – сказал князь Андрей.
– Да, – сказала графиня и протянула ему руку и с смешанным чувством отчужденности и нежности прижалась губами к его лбу, когда он наклонился над ее рукой. Она желала любить его, как сына; но чувствовала, что он был чужой и страшный для нее человек. – Я уверена, что мой муж будет согласен, – сказала графиня, – но ваш батюшка…
– Мой отец, которому я сообщил свои планы, непременным условием согласия положил то, чтобы свадьба была не раньше года. И это то я хотел сообщить вам, – сказал князь Андрей.
– Правда, что Наташа еще молода, но так долго.
– Это не могло быть иначе, – со вздохом сказал князь Андрей.
– Я пошлю вам ее, – сказала графиня и вышла из комнаты.
– Господи, помилуй нас, – твердила она, отыскивая дочь. Соня сказала, что Наташа в спальне. Наташа сидела на своей кровати, бледная, с сухими глазами, смотрела на образа и, быстро крестясь, шептала что то. Увидав мать, она вскочила и бросилась к ней.
– Что? Мама?… Что?
– Поди, поди к нему. Он просит твоей руки, – сказала графиня холодно, как показалось Наташе… – Поди… поди, – проговорила мать с грустью и укоризной вслед убегавшей дочери, и тяжело вздохнула.
Наташа не помнила, как она вошла в гостиную. Войдя в дверь и увидав его, она остановилась. «Неужели этот чужой человек сделался теперь всё для меня?» спросила она себя и мгновенно ответила: «Да, всё: он один теперь дороже для меня всего на свете». Князь Андрей подошел к ней, опустив глаза.
– Я полюбил вас с той минуты, как увидал вас. Могу ли я надеяться?
Он взглянул на нее, и серьезная страстность выражения ее лица поразила его. Лицо ее говорило: «Зачем спрашивать? Зачем сомневаться в том, чего нельзя не знать? Зачем говорить, когда нельзя словами выразить того, что чувствуешь».
Она приблизилась к нему и остановилась. Он взял ее руку и поцеловал.
– Любите ли вы меня?
– Да, да, – как будто с досадой проговорила Наташа, громко вздохнула, другой раз, чаще и чаще, и зарыдала.
– Об чем? Что с вами?
– Ах, я так счастлива, – отвечала она, улыбнулась сквозь слезы, нагнулась ближе к нему, подумала секунду, как будто спрашивая себя, можно ли это, и поцеловала его.
Князь Андрей держал ее руки, смотрел ей в глаза, и не находил в своей душе прежней любви к ней. В душе его вдруг повернулось что то: не было прежней поэтической и таинственной прелести желания, а была жалость к ее женской и детской слабости, был страх перед ее преданностью и доверчивостью, тяжелое и вместе радостное сознание долга, навеки связавшего его с нею. Настоящее чувство, хотя и не было так светло и поэтично как прежнее, было серьезнее и сильнее.