In mathematics, a de Bruijn sequence in combinatorics is a cyclic sequence from a given alphabetA of size m, of length Wikibooks Wikiversity has more about this subject: School of Mathematics Wikiquote has a collection of quotations by or about: Mathematics Look up Mathematics in Wiktionary, the free dictionary Wikimedia Commons has more media related to: Mathematics Bogomolny, Alexander: Interactive Mathematics Miscellany and Puzzles. ... Combinatorics is a branch of mathematics that studies finite collections of objects that satisfy specified criteria. ... An alphabet is a complete standardized set of letters—basic written symbols—each of which roughly represents a phoneme of a spoken language, either as it exists now or as it may have been in the past. ...
N = mn
for which every possible subsequence of length n in A is present exactly once.
For example, with
m = 2, n = 3, A = {0,1}
one can take
11100010.
For
m = 2, n = 5, A = {0,1}
one can take
01000111110111001101011000001010.
References
de Bruijn, N. G. "A Combinatorial Problem." Koninklijke Nederlandse Akademie v. Wetenschappen 49, 758-764, 1946.
In combinatorial mathematics, a k-ary DeBruijnsequence B(k, n) of order n, named after Nicolaas Govert deBruijn, is a cyclic sequence from a given alphabet A of size k for which every possible subsequence of length n in A is present exactly once.
Each edge in this 3-dimensional deBruijn graph corresponds to a sequence of four digits: the three digits that label the vertex that the edge is leaving followed by the one that labels the edge.
The symbols of a DeBruijnsequence written around a circular object (possibly a wheel of a robot) can be used to identify its angle by examining the n consecutive symbols facing a fixed point.
Feeds |
Contact