'''[[Main Page|Home]] * [[Programming]] * [[Data]] * De Bruijn Sequence'''
[[FILE:LW441-MC-Escher-Moebius-Strip-II-1963.jpg|border|right|thumb|link=http://www.mcescher.com/gallery/recognition-success/mobius-strip-ii/|[[Arts#Escher|M.C. Escher]] - Möbius Strip II <ref>[http://www.mcescher.com/gallery/recognition-success/ M.C. Escher - The Official Website – Recognition & Success] </ref> <ref>[https://en.wikipedia.org/wiki/M%C3%B6bius_strip Moebius Strip from Wikipedia]</ref> ]] In [https://en.wikipedia.org/wiki/Combinatorics combinatorial mathematics], a '''k'''-ary '''De Bruijn Sequence''' B(k, n) of order '''n''', named after the Dutch mathematician [[Nicolaas de Bruijn]], is a cyclic sequence of a given alphabet '''A''' with size '''k''' for which every possible subsequence of length '''n''' in '''A''' appears as a sequence of consecutive characters exactly once <ref>[https://en.wikipedia.org/wiki/De_Bruijn_sequence De Bruijn sequence from Wikipedia]</ref>. In chess programming there are applications of de Bruijn sequences with the Binary alphabet, in [[Hash Table|hashing]] sets like [[Piece-Sets]] or Square-sets, also called [[Bitboards]], most notably in [[BitScan#DeBruijnMultiplation|Bit scanning]] <ref>[[Charles Leiserson|Charles E. Leiserson]], [[Harald Prokop]], [[Keith H. Randall]] ('''1998'''). ''Using de Bruijn Sequences to Index a 1 in a Computer Word''. [http://supertech.csail.mit.edu/papers/debruijn.pdf pdf]</ref> .
=Binary alphabet=
<span id="DeBruijnGraphs"></span>
=De Bruijn Graphs=
A De Bruijn graph is a directed graph representing overlaps between sequences of symbols <ref>[https://en.wikipedia.org/wiki/De_Bruijn_graph De Bruijn graph from Wikipedia]</ref> .
* Each vertex has exactly m incoming and m outgoing edges
* Each n-dimensional de Bruijn graph is the [https://en.wikipedia.org/wiki/Line_graph line digraph] of the (n-1)-dimensional de Bruijn graph
=De Bruijn Networks=
So called De Bruijn Networks with the topology of De Bruijn Graphs have interesting properties in processor and computer networks, for instance as described by [[Rainer Feldmann|Feldmann et al.]] to connect [[Transputer]] networks <ref>[[Rainer Feldmann]], [[Peter Mysliwietz]], [[Burkhard Monien]] ('''1991'''). ''A Fully Distributed Chess Program''. [[Advances in Computer Chess 6]], [http://www.top-5000.nl/ps/A%20fully%20distribuited%20chess%20program.pdf pdf]</ref> <ref>[[Rainer Feldmann]] ('''1993'''). ''Game Tree Search on Massively Parallel Systems'' Phd-Thesis, [http://wwwcs.uni-paderborn.de/fachbereich/AG/monien/PUBLICATIONS/POSTSCRIPTS/feldmann_phd.pdf pdf]</ref> .
=See also=
* [https://oeis.org/A166315 A166315 - OEIS]
* [https://en.wikipedia.org/wiki/Lyndon_word Lyndon word from Wikipedia]
* [[Videos#:Category:If|If]] - [https://en.wikipedia.org/wiki/If_3 Forgotten Roads], [https://en.wikipedia.org/wiki/Beat-Club Beat-Club] [https://www.youtube.com/watch?v=V1BcLk19hVw #71], September 25, 1971, [https://en.wikipedia.org/wiki/YouTube YouTube] Video: {{#evu:https://www.youtube.com/watch?v=JFTX4cwxJLI2Hejk6KyYpk|alignment=left|valignment=top}}
=References=
<references /> '''[[Data|Up one Level]]'''[[Category:M. C. EscherIf]]
