en.wikipedia.org/wiki/De_Bruijn_sequence
2 corrections found
Such a sequence is denoted by B(k, n) and has length kn, which is also the number of distinct strings of length n on A.
The exponent is missing here: a de Bruijn sequence over an alphabet of size k has length k^n, not k·n.
Full reasoning
As written, this statement is mathematically incorrect. For a de Bruijn sequence of order n on an alphabet of size k, the sequence length equals the number of possible length-n strings over that alphabet, which is k^n.
Why this matters:
- There are
kchoices for each of thenpositions in a length-nstring. - By the multiplication principle, that gives
k × k × ... × k = k^ntotal strings. - A de Bruijn sequence contains each of those strings exactly once cyclically, so its length is
k^n.
Authoritative references state the definition this way. The Wolfram documentation says a de Bruijn sequence is a cyclic sequence of length k^n, and the debruijnsequence.org project gives the same definition.
So the text as written should say k^n, not kn.
2 sources
- DeBruijnSequence — Wolfram Documentation
A de Bruijn sequence of order n on a list of length k is a cyclic sequence of length ... DeBruijnSequence [ k , n ] returns a list of length ... Length[DeBruijnSequence[k, n]] == k ^ n
- De Bruijn Sequences and Universal Cycles
Given an alphabet of size k, a de Bruijn (DB) sequence of order n is a cyclic string of length k^n where every k-ary string of length n appears exactly once as a substring.
Goal: to construct a B(2, 4) de Bruijn sequence of length 24 = 16 using Eulerian (n − 1 = 4 − 1 = 3) 3-D de Bruijn graph cycle.
The length expression is wrong as written: for B(2,4) the length is 2^4 = 16, not 24 = 16.
Full reasoning
For a binary de Bruijn sequence of order 4, the length is 2^4 = 16 because a de Bruijn sequence on an alphabet of size k and order n has length k^n.
So for B(2,4):
- alphabet size
k = 2 - order
n = 4 - length
= 2^4 = 16
The written expression 24 = 16 is false as plain arithmetic. This appears to be a dropped superscript; the correct expression is 2^4 = 16.
2 sources
- De Bruijn Sequences and Universal Cycles
Given an alphabet of size k, a de Bruijn (DB) sequence of order n is a cyclic string of length k^n where every k-ary string of length n appears exactly once as a substring. Example n=4 and k=2 ... the 16 unique substrings of length 4...
- DeBruijnSequence — Wolfram Documentation
Length[DeBruijnSequence[k, n]] == k ^ n