Lably
Skip to content

De Bruijn sequence

Cycle through all length-k sequences

  • 18 min read
  • 7 chapters

Related on Lably

Through Combinatorics, Mathematics and String (computer science)

LabHide & Seek GharLabTarazu BazaarLabThe Counting MarketLabFestival Mela

The number of distinct de Bruijn sequences B(k, n) is

(k!)kn−1kn.

For a binary alphabet this is 22(n−1)−n, leading to the following sequence for positive n: 1, 1, 2, 16, 2048, 67108864... (sequence A016031 in the OEIS)

The sequences are named after the Dutch mathematician Nicolaas Govert de Bruijn, who wrote about them in 1946. As he later wrote, 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 (1894). The generalization to larger alphabets is due to Tatyana van Aardenne-Ehrenfest and de Bruijn (1951). Automata for recognizing these sequences are denoted as de Bruijn automata.

In many applications, A = {0,1}.

History

The earliest known example of a de Bruijn sequence comes from Sanskrit prosody where, since the work of Pingala, each possible three-syllable pattern of long and short syllables is given a name, such as 'y' for short–long–long and 'm' for long–long–long. To remember these names, the mnemonic yamātārājabhānasalagām is used, in which each three-syllable pattern occurs starting at its name: 'yamātā' has a short–long–long pattern, 'mātārā' has a long–long–long pattern, and so on, until 'salagām' which has a short–short–long pattern. This mnemonic, equivalent to a de Bruijn sequence on binary 3-tuples, is of unknown antiquity, but is at least as old as Charles Philip Brown's 1869 book on Sanskrit prosody that mentions it and considers it "an ancient line, written by Pāṇini".

In 1894, A. de Rivière raised the question in an issue of the French problem journal L'Intermédiaire des Mathématiciens, of the existence of a circular arrangement of zeroes and ones of size 2n that contains all 2n binary sequences of length n. The problem was solved (in the affirmative), along with the count of 22n−1−n distinct solutions, by Camille Flye Sainte-Marie in the same year. This was largely forgotten, and Martin (1934) proved the existence of such cycles for general alphabet size in place of 2, with an algorithm for constructing them. Finally, when in 1944 Kees Posthumus conjectured the count 22n−1−n for binary sequences, de Bruijn proved the conjecture in 1946, through which the problem became well known.

Karl Popper independently describes these objects in his The Logic of Scientific Discovery (1934), calling them "shortest random-like sequences".

Sign in to keep reading

6 more chapters are free with a Lably account.

More in Computing and communication

ISBNUnique numeric book identifier since 1970X (social network)American social networking serviceWayback MachineDigital archive by the Internet ArchivePython (programming language)General-purpose programming languageMacOSOperating system for Apple computersUnicodeCharacter encoding standard