De Bruijn Sequence

In combinatorial mathematics, a k-ary De Bruijn sequence B(k, n) of order n, named after the Dutch mathematician Nicolaas Govert 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.

Each B(k, n) has length kn.

There are distinct De Bruijn sequences B(k, n).

According to De Bruijn himself, the existence of De Bruijn sequences for each order together with the above properties were first proved, for the case of alphabets with two elements, by Camille Flye Sainte-Marie in 1894, whereas the generalization to larger alphabets is originally due to Tanja van Ardenne-Ehrenfest and himself.

Read more about De Bruijn Sequence:  History, Examples, Construction, Uses, De Bruijn Torus, De Bruijn Decoding

Famous quotes containing the word sequence:

    It isn’t that you subordinate your ideas to the force of the facts in autobiography but that you construct a sequence of stories to bind up the facts with a persuasive hypothesis that unravels your history’s meaning.
    Philip Roth (b. 1933)