Science Fair Project Encyclopedia
De Bruijn sequence
In mathematics, a de Bruijn sequence in combinatorics is a cyclic sequence from a given alphabet A of size m, of length
- 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.
External links
Last updated: 06-04-2005 16:09:38
10-26-2009 08:16:03
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details