De bruijn sekvens

En de Bruijn-sekvens [1] är en cyklisk ordning vars element tillhör en given finit mängd (mängden anses vanligtvis ), så att alla dess underföljder [2] av en given längd är olika. $a_{1},\;\ldots ,\;a_{t}$ $\{0,\;1,\;\ldots ,\;k-1\}$ $a_{{i+1}},\;\ldots ,\;a_{{i+n}}$ $n$

Periodiska sekvenser med period anses ofta innehållande olika delsekvenser , dvs sådana periodiska sekvenser där vilket längdsegment som helst är en de Bruijn-sekvens med samma parametrar och . $T$ $T$ $a_{{i+1}},\;\ldots ,\;a_{{i+n}}$ $T+n-1$ $n$ $k$

Cyklerna är uppkallade efter den holländska matematikern Nicholas de Bruijn , som studerade dem 1946 [3] , även om de har studerats tidigare [4] .

Egenskaper

Uppenbarligen kan längden (perioden) av en sådan cykel inte överstiga - antalet alla vektorer med olika längd med element från ; Det är lätt att bevisa att denna uppskattning är möjlig. Cykler av denna maximalt möjliga längd kallas vanligtvis de Bruijn-cykler (dock ibland används denna term även för cykler med kortare längd). $k^{n}$ $n$ $\{0,\;1,\;\ldots ,\;k-1\}$

För , det finns sådana de Bruijn- cykler med en längd som är mindre än maximinivån, som uttrycks av linjära återkommande relationer av ordningen På basis av sådana sekvenser, i synnerhet, byggs den cykliska redundanta koden CRC32 (EDB88320). $k=2$ $n$ $n=3$ $x_{n}=x_{{n-2}}+x_{{n-3}}{\pmod 2}$

Exempel

Exempel på de Bruijn-cykler för perioderna 2, 4, 8, 16: $k=2$

01 (innehåller undersekvenserna 0 och 1)
0011 (innehåller undersekvenserna 00, 01, 11, 10)
00010111 (000, 001, 010, 101, 011, 111, 110, 100)
0000100110101111

Antal de Bruijn-cykler

Antalet de Bruijn-cykler med parametrar är också ( ett specialfall av de Bruijns sats är BÄSTA satsen , uppkallad efter namnen på de Bruijn, Tatiana Ehrenfest , Cedric Smith och William Tutt ). $n$ $k$ $k!^{{k^{{(n-1)}}}}/k^{n}$

Comte de Bruyne

Det finns en bekväm tolkning av de Bruijn-sekvenser och cykler baserad på den så kallade de Bruijn-grafen - en riktad graf med hörn som motsvarar olika uppsättningar av längder med element från , där en kant leder från vertex till vertex om och endast om ( ); i detta fall kan själva kanten associeras med en uppsättning längder : . För en sådan graf motsvarar Eulerbanor ( Euleriska cykler ) som inte passerar två gånger genom samma kant en de Bruijn-sekvens (cykel) med parametrar och , och Hamiltonska banor ( Hamiltonska cykler ) som inte passerar två gånger genom samma vertex motsvarar till en sekvens (cykel) de Bruijn med parametrar och . $k^{n}$ $k^{n}$ $n$ $\{0,\;1,\;\ldots ,\;k-1\}$ $(x_{1},\;\ldots ,\;x_{n})$ $(y_{1},\;\ldots ,\;y_{n})$ $x_{i}=y_{{i-1}}$ $i=2,\;\ldots ,\;n$ $n+1$ $(x_{1},\;\ldots ,\;x_{n},\;y_{n})=(x_{1},\;y_{1},\;\ldots ,\;y_{n} )$ $n+1$ $k$ $n$ $k$

De Bruijn-grafen används i stor utsträckning inom bioinformatik i genomsammansättningsuppgifter .

Anteckningar

↑ Det finns också stavningar "de Bruyn" och "de Bruyn".
↑ Om , så väljs elementet med index i en cyklisk ordning $j>t$ $j{\bmod {t))$
↑ de Bruijn NG Ett kombinatoriskt problem // Koninklijke Nederlandse Akademie v. Wetenschappen. 1946. - v. 49.-s. 758-764.
↑ Flye Sainte-Marie C. Fråga 48 // L'intermédiaire math. - 1894. - v. 1.-s. 107-110.

Sekvenser och rader
Sekvenser	Numerisk sekvens Grundläggande sekvens Linjär återkommande sekvens Fibonacci-siffror lockiga siffror Faktoriell Barker-sekvens de bruijn sekvens
Rader, grundläggande	Radsumma Resten av raden Villkorlig konvergens Omväxlande serie Rad flersektion
Nummerserier ( operationer med nummerserier )	harmonisk serie Leibniz-serien En serie omvända kvadrater En serie ömsesidiga primtal Dirichlet rad Mercator-serien Rad Grandi 1 - 2 + 3 - 4 + ... 1 + 2 + 3 + 4 + ...
funktionella rader	Taylor-serien Laurent-serien Fourier-serier Trigonometrisk Fourier-serie trigonometrisk serie Wiener-serien
Andra radtyper	Neumann-serien Puiseux rad