# Zero-one links: how many, and how to produce?

For $m \geq 1$, define a link to be a zero-one word $w=d_0d_1 \ldots d_k$, where $d_0=0$ and $k=2^m-1$ , such that the words

$$w_0=0^{m-1}d_0, w_1=w_0d_1, w_2=w_1d_2, \ldots, w_k = w_{k-1}d_k$$

include as subwords every zero-one word of length $m$. How many links are there, and how can they be produced? If the answer is known, all I need is a reference. Otherwise, the question extends naturally to links of words on the alphabet from $0$ to $n>1$.

Example: For $m = 3$ two links are $01011100$ and $01110100$. The first link codes the following words: $$w_0 = 000, w_01, w_010, w_0101, w_01011, w_010111, w_0101110, w_01011100, w_010111000,$$ in which all $8$ zero-one words of length $3$ occur as the final $3$ letters of the words. (The final word, $w_010111000$, is shown as the first word in a second link in an infinite chain.)

• Have you tried small values and searched OEIS? – Per Alexandersson Nov 20 '15 at 14:55
• Editor - can you fix the first display line? It looked just right when I submitted it. – Clark Kimberling Nov 20 '15 at 14:56
• DeBruijn sequences? Gerhard "Sure I've Seen This Before" Paseman, 2015.11.20 – Gerhard Paseman Nov 20 '15 at 15:45
• here is the Wikipedia article: en.wikipedia.org/wiki/De_Bruijn_sequence – Jan Kyncl Nov 21 '15 at 21:20