Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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
add comment

2 Answers

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
add comment

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
show 1 more comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.