De bruijn sorozat

A de Bruijn sorozat [1] egy olyan ciklikus rend, amelynek elemei egy adott véges halmazhoz tartoznak (a halmazt általában -nak tekintik ), így annak adott hosszúságú részsorozatai [2] különbözőek. $a_{1},\;\ldots ,\;a_{t}$ $\{0,\;1,\;\ldots ,\;k-1\}$ $a_{{i+1}},\;\ldots ,\;a_{{i+n}}$ $n$

Gyakran számításba veszik a periódusos periódusos sorozatokat , amelyek különböző részszekvenciákat tartalmaznak , azaz olyan periodikus sorozatokat, amelyekben bármely hosszúságú szakasz egy de Bruijn-szekvencia azonos paraméterekkel és . $T$ $T$ $a_{{i+1}},\;\ldots ,\;a_{{i+n}}$ $T+n-1$ $n$ $k$

A ciklusokat Nicholas de Bruijn holland matematikusról nevezték el , aki 1946 -ban tanulmányozta őket [3] , bár korábban is tanulmányozták őket [4] .

Tulajdonságok

Nyilvánvaló, hogy egy ilyen ciklus hossza (periódusa) nem haladhatja meg - az összes különböző hosszúságú vektorok számát ; Könnyű bizonyítani, hogy ez a becslés teljesült. Az ilyen maximális hosszúságú ciklusokat általában de Bruijn-ciklusoknak nevezik (azonban néha ezt a kifejezést a rövidebb ciklusokra is alkalmazzák). $k^{n}$ $n$ $\{0,\;1,\;\ldots ,\;k-1\}$

Mert vannak olyan de Bruijn -ciklusok, amelyek hossza eggyel kisebb, mint a maximum, és amelyeket a sorrend lineáris ismétlődési relációi fejeznek ki. Az ilyen szekvenciák alapján különösen a CRC32 (EDB88320) ciklikus redundáns kód épül fel. $k=2$ $n$ $n=3$ $x_{n}=x_{{n-2}}+x_{{n-3}}{\pmod 2}$

Példák

Példák de Bruijn-ciklusokra a 2., 4., 8., 16. periódusban: $k=2$

01 (0 és 1 részsorozatot tartalmaz)
0011 (00, 01, 11, 10 részsorozatokat tartalmaz)
00010111 (000, 001, 010, 101, 011, 111, 110, 100)
0000100110101111

De Bruijn ciklusok száma

A paraméterekkel ellátott de Bruijn-ciklusok száma is ( de Bruijn tételének speciális esete a BEST tételTatiana Ehrenfest , Cedric Smith és William Tutt nevéről kapta a nevét ). $n$ $k$ $k!^{{k^{{(n-1)}}}}/k^{n}$

Comte de Bruyne

Van egy kényelmes értelmezése a de Bruijn sorozatoknak és ciklusoknak az úgynevezett de Bruijn gráfon – egy irányított gráfon, amelynek csúcsai különböző hosszúságú halmazoknak felelnek meg elemekkel -ból , amelyben egy él akkor és csak akkor vezet csúcsból csúcsba, ha ( ); ebben az esetben maga az él társítható egy hosszúságkészlethez : . Egy ilyen gráf esetében azok az Euler-utak ( Euler-ciklusok ) , amelyek nem mennek át kétszer ugyanazon az élen , megfelelnek egy de Bruijn-sorozatnak (ciklusnak) és paraméterekkel , és azok a Hamilton-pályák ( Hamilton-ciklusok ) , amelyek nem mennek át kétszer ugyanazon a csúcson. de Bruijn sorozathoz (ciklushoz) és paraméterekkel . $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$

A de Bruijn gráfot széles körben használják a bioinformatikában genom összeállítási feladatokban .

Jegyzetek

↑ Vannak "de Bruyn" és "de Bruyn" elírások is.
↑ Ha , akkor az indexszel rendelkező elem ciklikus sorrendben kerül kiválasztásra $j>t$ $j{\bmod {t))$
↑ de Bruijn NG Kombinatorikus probléma // Koninklijke Nederlandse Akademie v. Wetenschhappen. 1946. - v. 49.-pp. 758-764.
↑ Flye Sainte-Marie C. 48. kérdés // L'intermédiaire math. - 1894. - v. 1.-pp. 107-110.

Sorozatok és sorok
Sorozatok	Numerikus sorozat Alapvető sorrend Lineáris ismétlődő sorozat Fibonacci számok göndör számok Faktoriális Barker sorozat de bruijn sorozat
Sorok, alap	Sor összege A sor többi része Feltételes konvergencia Váltakozó sorozatok Sor több szakasz
Számsorozat ( műveletek számsorokkal )	harmonikus sorozat Leibniz sorozat Inverz négyzetek sorozata Reciprok prímek sorozata Dirichlet sor Mercator sorozat Sor Grandi 1 - 2 + 3 - 4 + ... 1 + 2 + 3 + 4 + ...
funkcionális sorok	Taylor sorozat Laurent sorozat Fourier sorozat Trigonometrikus Fourier sorozat trigonometrikus sorozat Wiener sorozat
Egyéb sortípusok	Neumann sorozat Puiseux sor