De bruijn rækkefølge

En de Bruijn-sekvens [1] er en cyklisk orden, hvis elementer tilhører en given endelig mængde (sættet betragtes normalt som ), således at alle dets underfølger [2] af en given længde er forskellige. $a_{1},\;\ldots ,\;a_{t}$ $\{0,\;1,\;\ldots ,\;k-1\}$ $a_{{i+1}},\;\ldots ,\;a_{{i+n}}$ $n$

Periodiske sekvenser med periode betragtes ofte indeholdende forskellige undersekvenser , dvs. sådanne periodiske sekvenser, hvor ethvert længdesegment er en de Bruijn-sekvens med de samme parametre og . $T$ $T$ $a_{{i+1}},\;\ldots ,\;a_{{i+n}}$ $T+n-1$ $n$ $k$

Cyklerne er opkaldt efter den hollandske matematiker Nicholas de Bruijn , som studerede dem i 1946 [3] , selvom de er blevet studeret før [4] .

Egenskaber

Længden (perioden) af en sådan cyklus kan naturligvis ikke overstige - antallet af alle forskellige længdevektorer med elementer fra ; Det er let at bevise, at dette skøn er opnåeligt. Cykler af denne maksimalt mulige længde kaldes sædvanligvis de Bruijn-cyklusser (men nogle gange anvendes dette udtryk også på cyklusser af kortere længde). $k^{n}$ $n$ $\{0,\;1,\;\ldots ,\;k-1\}$

For , der er sådanne de Bruijn- cyklusser med en længde, der er en mindre end maksimum, som er udtrykt ved lineære gentagelsesrelationer af rækkefølgen På basis af sådanne sekvenser er især den cykliske redundante kode CRC32 (EDB88320) bygget. $k=2$ $n$ $n=3$ $x_{n}=x_{{n-2}}+x_{{n-3}}{\pmod 2}$

Eksempler

Eksempler på de Bruijn-cyklusser for periode 2, 4, 8, 16: $k=2$

01 (indeholder undersekvens 0 og 1)
0011 (indeholder undersekvenser 00, 01, 11, 10)
00010111 (000, 001, 010, 101, 011, 111, 110, 100)
0000100110101111

Antal de Bruijn-cyklusser

Antallet af de Bruijn-cyklusser med parametre er også ( et specialtilfælde af de Bruijns sætning er BEDSTE sætning , opkaldt efter navnene på de Bruijn, Tatiana Ehrenfest , Cedric Smith og William Tutt ). $n$ $k$ $k!^{{k^{{(n-1)}}}}/k^{n}$

Comte de Bruyne

Der er en bekvem fortolkning af de Bruijn-sekvenser og cyklusser baseret på den såkaldte de Bruijn-graf - en rettet graf med toppunkter svarende til forskellige sæt længder med elementer fra , hvor en kant fører fra toppunkt til toppunkt , hvis og kun hvis ( ); i dette tilfælde kan selve kanten associeres med et sæt længder : . For en sådan graf svarer Euler-stier ( Eulerske cyklusser ) , der ikke passerer to gange gennem den samme kant , til en de Bruijn-sekvens (cyklus) med parametre og , og Hamiltonske stier ( Hamiltonske cyklusser ) , der ikke passerer to gange gennem samme toppunkt , svarer til til en sekvens (cyklus) de Bruijn med parametre og . $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 er meget udbredt i bioinformatik i genomsamlingsopgaver .

Noter

↑ Der er også stavemåder "de Bruyn" og "de Bruyn".
↑ Hvis , så vælges elementet med indeks i en cyklisk rækkefølge $j>t$ $j{\bmod {t))$
↑ de Bruijn NG Et kombinatorisk problem // Koninklijke Nederlandse Akademie v. Wetenschappen. 1946. - v. 49.-s. 758-764.
↑ Flye Sainte-Marie C. Spørgsmål 48 // L'intermédiaire math. - 1894. - v. 1.-s. 107-110.

Sekvenser og rækker
Sekvenser	Numerisk rækkefølge Grundlæggende rækkefølge Lineær tilbagevendende sekvens Fibonacci-tal krøllede tal Faktoriel Barker-sekvens de bruijn rækkefølge
Rækker, grundlæggende	Rækkesum Resten af rækken Betinget konvergens Skiftende serie Række multisektion
Talserier ( operationer med talserier )	harmoniske serier Leibniz-serien En række omvendte firkanter En række gensidige primtal Dirichlet række Mercator serien Række Grandi 1 - 2 + 3 - 4 + ... 1 + 2 + 3 + 4 + ...
funktionelle rækker	Taylor-serien Laurent-serien Fourier-serien Trigonometrisk Fourier-serie trigonometriske serier Wiener-serien
Andre rækketyper	Neumann-serien Puiseux række