Take the 2-minute tour ×

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?

share|improve this question
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 '13 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 '13 at 0:28

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
More directly (and abusing index notation for functions on nonnegative integers), p(n) = sum_i p(n-1-2i) = p(n-1) + sum_i p(n-3-2i) = p(n-1)+p(n-2), where p(n) appears in my comments to the question. –  The Masked Avenger Aug 16 '13 at 0:41
I think you can get the recurrence even faster by considering those compositions that begin with a "1", and those that don't. –  Gerry Myerson Aug 16 '13 at 0:43
Afte the indirection of substituting (12)^k for (1^k 2^k) , any length n such string ends in 0 or a 12, giving a (conjugation of a) direct route to the recurrence. This is the first time recall using conjugation in a nongroup setting. –  The Masked Avenger Aug 16 '13 at 0:51
You are probably right Gerry, but since they all begin with 0, I have a hard time understanding your comment. (If you mean size 1, that does seem good.) –  The Masked Avenger Aug 16 '13 at 0:53
@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 '13 at 0:58

Your Answer


