Combinatorics of folding digit strings

2012-07-15T02:27:13Z

Say that a string of $n$ digits, each from $\lbrace 0,1,2,\ldots,b-1 \rbrace$,is foldable if, were each digit on its own stamp in a sequence of connected stamps, one could fold the stamps so that like digits are on top of one another, forming a "stack" of $0$s, adjacent to a stack of $1$s, adjacent to a stack of $2$s, and so on. For example, for $b=2$ binary strings, the stamps should form two piles: $0$s and $1$s, like this:

For binary strings, it is clear that a foldable string must have runs of an even number of $0$s and $1$s everywhere except at the two ends of the string; these end runs can be of even or odd length. It is not too difficult to work out that of the $2^n$ binary strings of length $n$, the number foldable is $$f(n) = 3 \cdot 2^{n/2} -2 \;\;, n \; \mathrm{even}$$ $$f(n) = 2 \cdot 2^{\lceil n/2 \rceil} - 2 \;\;, n \; \mathrm{odd}$$ For example, for $n=10$, $3 \cdot 2^5 -2 = 94$ of the $1024$ strings are foldable; for $n=11$, $126$ are foldable.

I am having difficulty generalizing the count to strings of digits from larger sets $\lbrace 0,1,2,\ldots,b-1 \rbrace$, $b>2$. For $b=3$, there should be three consecutive "stacks", of $0$s, $1$s, and $2$s. Although an exact formula would be nice, I am particularly interested in whether the exponential growth remains $2^{n/2}$. Perhaps someone has seen this before, perhaps in another guise? If so, I'd appreciate a reference. Thanks!

Addendum. In case anyone wants to try to understand the exact count for $b=3$, here are some tentative computational enumerations, with $n$ the number of digits, $f$ the number of foldable strings, and $u$ the number of unfoldable strings: $$n=1 \;,\; f=3 \;,\; u=0 \;,\; f+u = 3$$ $$n=2 \;,\; f=7 \;,\; u=2 \;,\; f+u = 9$$ $$n=3 \;,\; f=13 \;,\; u=14 \;,\; f+u = 27$$ $$n=4 \;,\; f=23 \;,\; u=58 \;,\; f+u = 81$$ $$n=5 \;,\; f=39 \;,\; u=204 \;,\; f+u = 243$$ $$n=6 \;,\; f=65 \;,\; u=664 \;,\; f+u = 729$$ $$n=7 \;,\; f=107 \;,\; u=2080 \;,\; f+u = 2187$$ OEIS identifies the $f$-sequence as A154691: Expansion of $$ \frac {1+x+x^2}{(1-x-x^2)(1-x)} .$$

Answer by Anthony Quas for Combinatorics of folding digit strings

2012-07-15T04:50:04Z

The exponential growth rate is greater than $2^{n/2}$. It's $2^{r_bn}$ where $r_b\to 1$ as $b\to\infty$. What you're essentially looking at is the number of random walks on $b+1$ vertices (you can see this in your picture).

From this, you see that $2^{r_b}$ is the leading eigenvalue of the adjacency matrix of a path on $b+1$ vertices, which is $2\cos(\pi/(b+2))$.

Answer by Florian Eisele for Combinatorics of folding digit strings

2012-07-15T23:53:01Z

Edit: On second thought, this is pretty much exactly Anthony's answer, only slightly more explicit. Didn't see this when I wrote this up, sorry.

There's an approach to this problem using elementary linear algebra, which gives you an explicit formula for $f(n)$ each $b$ (however no nice formula for an all $b$ at once), and an algebraic integer $a$ such that $f(n)=c\cdot a^n + \textrm{lower order terms}$. For instance, for $b=3$ you obtain $a = \frac{1+\sqrt{5}}{2}$ and for $b=4$ you obtain $a = \sqrt{3}$. The actual formulas get really messy, for instance for $b=3$ you get (thanks to Maple) $$ f(n) = 8/5\cdot {\frac {-120-60\,\sqrt {5}+10\, \left( -1 \right) ^{1+n} \left( \sqrt {5}+1 \right) ^{-n}{2}^{n}+11\, \left( \sqrt {5}+2 \right) ^{n-1 } \left( 3+\sqrt {5} \right) ^{2-n}\sqrt {5}{2}^{n}+5\, \left( -1 \right) ^{n} \left( \sqrt {5}-1 \right) ^{-n+1} \left( 3+\sqrt {5} \right) ^{-n+1}{4}^{n}+ \left( -1 \right) ^{1+n}{2}^{1+n}\sqrt {5} \left( \sqrt {5}+1 \right) ^{-n}+25\, \left( \sqrt {5}+2 \right) ^{n- 1} \left( 3+\sqrt {5} \right) ^{2-n}{2}^{n}}{ \left( \sqrt {5}-1 \right) ^{2} \left( 3+\sqrt {5} \right) ^{2} \left( \sqrt {5}+1 \right) }} $$ the first ten values of which are $3, 7, 13, 23, 39, 65, 107, 175, 285, 463, \ldots$

So, the following is a description of how to obtain the growth behavior and explicit formulas (some details are missing since this got a bit longer than I expected):

First notice that the diagrams that you draw in your question are uniquely determined by the foldable sequence in all except in $b$ cases, namely the sequences $[i,i,\ldots,i]$ for which there are two possible diagrams. To see this just notice that whenever a sequence contains a subsequence [i-1,i] or $[i,i-1]$ this subsequence is represented in the diagram by a blue line crossing the $i$-th vertical red line in your digram, and the rest of the diagram is hence determined (See it this way: whenever you "add a digit" to your sequence this corresponds to a unique extension of the blue line, the only ambiguous part was the placement of the first line segment). In conclusion we focus our interest on the number $g(n)$ of possible "folding diagrams", and we have $$ g(n) = f(n) + b $$ (in fact this is where the summand $-2$ comes from in your formula; it will turn out that $g(n)$ is essentially a linear combination of exponential functions)

Now we decompose $$ g(n) = g_{0,0}(n) + g_{1,0}(n)+ g_{1,1}(n)+g_{2,1}(n)+g_{2,2}(n) + \ldots + g_{b-1,b-2}(n) + g_{b-1,b-1}(n) + g_{b,b-1}(n) $$ where $g_{i,j}(n)$ denotes the number of all folding diagrams corresponding to a sequence which starts with the digit $j \in \{ 0,\ldots,b-1 \}$ and is rooted at the $i$-th vertical red line in your diagram (counting from the left starting at $0$; so, $j\in \{0,\ldots, b\}$ and for a given $i$ the value of $j$ has to be $i$ or $i-1$).

Now the $g_{i,j}$ satisfy a linear recursive formula (this is obvious: once we specify the first line segment of a folding diagram we can concatenate it with any folding diagram of length $n-1$ which starts at the right vertical red line to obtain a folding diagram of length $n$): $$ g_{i,i}(n) = g_{i+1,i}(n-1) + g_{i+1,i+1}(n-1) \quad \textrm{ for } i\in\{0,\ldots,b-2\} $$ $$ g_{i,i-1}(n) = g_{i-1,i-1}(n-1) + g_{i-1,i-2}(n-1) \quad \textrm{ for } i\in\{2,\ldots,b\} $$ $$ g_{1,0}(n) = g_{0,0}(n-1) \quad \textrm{and} \quad g_{b-1,b-1}(n) = g_{b,b-1}(n-1) $$ Note that by definition $g_{i,j}(1)=1$ for all $g_{i,j}$'s which occur in these recursion relations. So we can put this recursion relation into a matrix $A_b$, and we will get a formula $$ \left(\begin{array}{c}g_{0,0}(n)\newline g_{1,0}(n) \newline g_{1,1}(n)\newline \vdots \newline g_{b,b-1}(n) \end{array}\right) = A_b \cdot \left(\begin{array}{c}g_{0,0}(n-1)\newline g_{1,0}(n-1) \newline g_{1,1}(n-1)\newline \vdots \newline g_{b,b-1}(n-1) \end{array}\right) = A_b^{n-1}\cdot \left(\begin{array}{c} 1\newline 1 \newline 1 \newline \vdots \newline 1\end{array}\right) $$ Since $g(n)$ was just the sum of all $g_{i,j}(n)$ and $f(n)=g(n)-2$ we get $$ f(n) = [1,\ldots,1]\cdot A_b^{n-1} \cdot [1,\ldots,1]^\top-b $$ It should be clear now that by transforming $A_b$ into Jordan normal form we can get an explicit formula for each $b$ (as a linear combination of $\leq n$-th powers of the eigenvalues of $A_b$).

So when it comes to the growth behavior, we're interested in the eigenvalue of $A_b$ of biggest absolute value. Now the matrices $A_b$ have a very simple form: $$ A_3 = \left[ \begin {array}{cccccc} 0&1&1&0&0&0\newline 1&0&0&0 &0&0\newline 0&0&0&1&1&0\newline 0&1&1&0&0&0 \newline 0&0&0&0&0&1\newline 0&0&0&1&1&0 \end {array} \right] \quad A_4 = \left[ \begin {array}{cccccccc} 0&1&1&0&0&0&0&0\newline 1 &0&0&0&0&0&0&0\newline 0&0&0&1&1&0&0&0 \newline 0&1&1&0&0&0&0&0\newline 0&0&0&0&0&1&1 &0\newline 0&0&0&1&1&0&0&0\newline 0&0&0&0&0&0 &0&1\newline 0&0&0&0&0&1&1&0\end {array} \right] $$ Notice how $A_{b}$ sits as a submatrix in the lower right corner of $A_{b+1}$, and this should be suffice to prove the following recurrence relation for the characteristic polynomials $\chi_b(x)$ of $A_b$ (to be honest I just checked it up to $b=10$ but it should be doable): $$ \chi_{b+1}(x) = x^2\cdot(\chi_b(x) - \chi_{b-1}(x)) $$ Together with the information that $\chi_2(x)=x^2-2$ and $\chi_3(x)=x^4-2x^2$ this gives you all characteristic polynomials for all the $A_b$ fairly easily.

So we get $$ f(n) = c \cdot a^n + \textrm{lower order terms} $$ where $a$ is the largest absolute value of a root of $\chi_b(x)$.

A few technicalities are required to make sure that $c\neq 0$: one should only consider roots of $\chi_b(x)$ which aren't multiples of $\sqrt{-1}$ (these will cancel each other out) and secondly, one needs to make sure that the vector $[1,\ldots,1]^\top$ doesn't lie in an $A_b$-stable proper subspace of $\mathbb R^{2b}$ (this can probably be shown, but it's too messy for me right now and I already spent more time on this answer than I should've).

Combinatorics of folding digit strings - MathOverflow

Combinatorics of folding digit strings

Answer by Anthony Quas for Combinatorics of folding digit strings

Answer by Florian Eisele for Combinatorics of folding digit strings