<p>You mean that each nonzero n-bit substring occurs once, and the all-zero n-bit substring occurs no times, right? Essentially, what you are looking for is a <a href="http://en.wikipedia.org/wiki/De_Bruijn_sequence" rel="nofollow">De Bruijn sequence</a>.</p>

<p>The number of de Bruijn sequences should be in OEIS somewhere but I'm having trouble finding it. My guess is that it grows doubly exponentially, since it is the number of Hamiltonian cycles in an exponential sized graph (the de Bruijn graph) and graphs tend to have exponentially many such cycles when they have any.</p>

CC BY-SA 3.0
2011-06-20T18:39:01.607Z
Thanks David, this indeed looks very close to answer i was looking for. However, the De Bruijn sequence demands that "every possible subsequence of length n in A appears as a sequence of consecutive characters exactly once." But i guess one could simply cut off each of these sequences at a earlier point to get all possible shorter sequences :)
Etsch
CC BY-SA 3.0
2011-06-20T18:08:03.530Z
2011-06-20T18:08:03.530Z
David Eppstein
<p>I have a question about binary strings with a certain property:</p>

<p>Given an integer $n$-bit integer $p$, that is not a perfect power of $2$. Count the number of $(p+n-2)$-bit strings that have the property that they start with $\underbrace{00...01}_{n-bit}$
and end with $\underbrace{100...0}_{n-\mathrm{bit}}$ and each $n$-bit substring occurs exactly once. </p>

<p>E.g., for $n=3$, $p=7$ there are $001 01 100$ and $001 10 100$, which are the only ones for the pair $(n,p)$.</p>

<p>Further examples are: $n=5$ and $p=29$: $00001 0001101001111011100101 10000$ </p>

<p>and $n=5$ and $p=19$: $00001 101011110010 10000$.  </p>

<p>I searched for related work and found papers about incompressible strings and Kolmogorov complexity. However, they did not helped me out. </p>

<p>Does there exists a combinatorial approach to count the number of solutions? Or is there an heuristic argument that gives a good approximation?</p>

CC BY-SA 3.0
2011-06-20T15:22:55.520Z
The requirement that each possible substring of a certain length occurs exactly one is like the requirement of [Lyndon words](http://en.wikipedia.org/wiki/Lyndon_word).  Maybe you are looking for something that could be derived easily from the study of Lyndon words.
mikero
CC BY-SA 3.0
2011-06-20T15:52:51.290Z
@mikero this could very well be an answer :)
Suresh Venkat
<co.combinatorics><string-search>
Number of strings with unique substrings
Etsch
# Number of strings with unique substrings

(Asked by: username_0 on 2011-06-20)

I have a question about binary strings with a certain property:

Given an integer $n$-bit integer $p$, that is not a perfect power of $2$. Count the number of $(p+n-2)$-bit strings that have the property that they start with $\underbrace{00...01}\_{n-bit}$
and end with $\underbrace{100...0}\_{n-\mathrm{bit}}$ and each $n$-bit substring occurs exactly once.

E.g., for $n=3$, $p=7$ there are $001 01 100$ and $001 10 100$, which are the only ones for the pair $(n,p)$.

Further examples are: $n=5$ and $p=29$: $00001 0001101001111011100101 10000$

and $n=5$ and $p=19$: $00001 101011110010 10000$.

I searched for related work and found papers about incompressible strings and Kolmogorov complexity. However, they did not helped me out.

Does there exists a combinatorial approach to count the number of solutions? Or is there an heuristic argument that gives a good approximation?

**Tags:** co.combinatorics, string-search
> **Comments:**
> **username_1**: The requirement that each possible substring of a certain length occurs exactly one is like the requirement of [Lyndon words](http://en.wikipedia.org/wiki/Lyndon_word).  Maybe you are looking for something that could be derived easily from the study of Lyndon words.  
> **username_2**: @mikero this could very well be an answer :)  

---

## 1 answers

### Answer by username_3 on 2011-06-20. Score: 8

You mean that each nonzero n-bit substring occurs once, and the all-zero n-bit substring occurs no times, right? Essentially, what you are looking for is a [De Bruijn sequence](http://en.wikipedia.org/wiki/De_Bruijn_sequence).

The number of de Bruijn sequences should be in OEIS somewhere but I'm having trouble finding it. My guess is that it grows doubly exponentially, since it is the number of Hamiltonian cycles in an exponential sized graph (the de Bruijn graph) and graphs tend to have exponentially many such cycles when they have any.

> **Comments:**
> **username_0**: Thanks David, this indeed looks very close to answer i was looking for. However, the De Bruijn sequence demands that "every possible subsequence of length n in A appears as a sequence of consecutive characters exactly once." But i guess one could simply cut off each of these sequences at a earlier point to get all possible shorter sequences :)  

---

