# Estimation of number of ways to concatenate strings of the form $01^k2^k$ to create a string of length n

In symbolic dynamics, the context-free shift is the set of biinfinite concatenations of strings of the form $01^k2^k$ for $k\in\mathbb{N}\cup\lbrace 0\rbrace$. I've reduced a certain problem to finding a reasonable upper bound on the number of ways to concatenate such strings to create a string of length n. This can be looked at as the number of ways to partition n into positive odd summands, taking combinations into account, but this doesn't seem to be a reasonable approach to the problem. How would I go about making this estimation?

-
It depends on how weak a bound you will accept. Using p(n), declare p(n) is at most 3^(alpha n), write a recurrence for p, and see what that tells you about alpha. –  The Masked Avenger Aug 16 at 0:17
It seems to me that p(n) satsfies the Fibonacci recurrence. I suspect your question will soon be migrated. –  The Masked Avenger Aug 16 at 0:28

Here is another approach to your question that could be used more generally for context-free shifts. Let C be the language of strings $01^k2^k$. This language is a suffix code (no two words are suffixes of each other). Thus the set $C^*$ of concatenations of elements of C is a free monoid generated freely by $C$ and so the generating function g(t) for $C^*$ is $\frac{1}{1-f(t)}$ where f(t) is the generating function for C. Now C is given by the unambiguous context-free grammar

$S\to 0T$,

$T\to \varepsilon \mid 1T2$

The Chomsky-Schutzenberger theorem then says $f(t)=tr(t)$ where $r(t)=1+t^2r(t)$. Thus $f(t)= \frac{t}{1-t^2}$. Thus $g(t)=\frac{1-t^2}{1-t-t^2}$ which is the Fibonacci generating series, or at least is the same recurrence.

-
The number of compositions of $n$ into odd parts is $F_n$, the $n$th Fibonacci number. See, e.g., page 259 of this paper by Hoggatt and Lind.
@The, I am thinking of the problem as one of composition of odd parts, rather than concatenation. When OP writes $01^k2^k$, I read $2k+1$. 000120 becomes $1+1+3+1$. –  Gerry Myerson Aug 16 at 0:58