2
$\begingroup$

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.)

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

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.