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?
2
-
1$\begingroup$ 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. $\endgroup$– The Masked AvengerCommented Aug 16, 2013 at 0:17
-
$\begingroup$ It seems to me that p(n) satsfies the Fibonacci recurrence. I suspect your question will soon be migrated. $\endgroup$– The Masked AvengerCommented Aug 16, 2013 at 0:28
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
answered Aug 16, 2013 at 14:33
$\begingroup$
$\endgroup$
6
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.
answered Aug 16, 2013 at 0:29
-
$\begingroup$ 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. $\endgroup$ Commented Aug 16, 2013 at 0:41
-
$\begingroup$ I think you can get the recurrence even faster by considering those compositions that begin with a "1", and those that don't. $\endgroup$ Commented Aug 16, 2013 at 0:43
-
$\begingroup$ 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. $\endgroup$ Commented Aug 16, 2013 at 0:51
-
$\begingroup$ 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.) $\endgroup$ Commented Aug 16, 2013 at 0:53
-
$\begingroup$ @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$. $\endgroup$ Commented Aug 16, 2013 at 0:58