Editing De Bruijn sequence (section)

{{Short description|Cycle through all length-k sequences}}
{{distinguish|text = the [[Moser–de Bruijn sequence]], an integer sequence from number theory}}

[[File:De Bruijn sequence.svg|thumb|The de Bruijn sequence for alphabet size {{nowrap|1= ''k'' = 2}} and substring length {{nowrap|1=  ''n'' = 2}}. In general there are many sequences for a particular ''n'' and ''k'' but in this example it is unique, [[up to]] cycling.]]

In [[combinatorics|combinatorial]] [[mathematics]], a '''de Bruijn sequence''' of order ''n'' on a size-''k'' [[alphabet (computer science)|alphabet]] ''A'' is a [[cyclic sequence]] in which every possible length-''n'' [[String (computer science)#Formal theory|string]] on ''A'' occurs exactly once as a [[substring]] (i.e., as a ''contiguous'' [[subsequence]]). Such a sequence is denoted by {{nowrap|''B''(''k'', ''n'')}} and has length {{nowrap|''k''<sup>''n''</sup>}}, which is also the number of distinct strings of length ''n'' on ''A''. Each of these distinct strings, when taken as a substring of {{nowrap|''B''(''k'', ''n'')}}, must start at a different position, because substrings starting at the same position are not distinct. Therefore, {{nowrap|''B''(''k'', ''n'')}} must have ''at least'' {{nowrap|''k''<sup>''n''</sup>}} symbols. And since {{nowrap|''B''(''k'', ''n'')}} has ''exactly'' {{nowrap|''k''<sup>''n''</sup>}} symbols, de Bruijn sequences are optimally short with respect to the property of containing every string of length ''n'' at least once.

The number of distinct de Bruijn sequences {{nowrap|''B''(''k'', ''n'')}} is
:<math>\dfrac{\left(k!\right)^{k^{n-1}}}{k^n}.</math>

For a binary alphabet this is <math>2^{2^{(n-1)} - n}</math>, leading to the following sequence for positive <math>n</math>: &nbsp; 1, 1, 2, 16, 2048, 67108864... ({{oeis|A016031}})

The sequences are named after the Dutch mathematician [[Nicolaas Govert de Bruijn]], who wrote about them in 1946.{{sfnp|de Bruijn|1946}} As he later wrote,{{sfnp|de Bruijn|1975}} the existence of de Bruijn sequences for each order together with the above properties were first [[mathematical proof|proved]], for the case of alphabets with two elements, by {{harvs|first=Camille|last=Flye Sainte-Marie|year=1894|txt}}. The generalization to larger alphabets is due to {{harvs|first1=Tatyana|last1=van Aardenne-Ehrenfest|author1-link=Tatyana Pavlovna Ehrenfest|last2=de Bruijn|year=1951|txt}}. [[automata theory|Automata]] for recognizing these sequences are denoted as de Bruijn automata.

In many applications, ''A'' = {0,1}.