# Number of strings with unique substrings

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?

• The requirement that each possible substring of a certain length occurs exactly one is like the requirement of Lyndon words. Maybe you are looking for something that could be derived easily from the study of Lyndon words. – mikero Jun 20 '11 at 15:22
• @mikero this could very well be an answer :) – Suresh Venkat Jun 20 '11 at 15:52