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?