6
$\begingroup$

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:
          FoldingDigits
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)} .$$

$\endgroup$
2
  • $\begingroup$ Martin Gardner had a similar item in Mathematical Games. Perhaps you may find it useful. Gerhard "Ask Me About System Design" Paseman, 2012.07.14 $\endgroup$ Jul 15, 2012 at 3:44
  • 1
    $\begingroup$ Also, if you stick with one dimension, any sequence will be a concatenation of sequences of foldable strings of length 2, with some restrictions. In particular, 0X2 being a foldable substring implies X has an odd number of 1's. Gerhard "Ask Me About System Design" Paseman, 2012.07.14 $\endgroup$ Jul 15, 2012 at 3:51

2 Answers 2

7
$\begingroup$

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))$.

$\endgroup$
4
  • $\begingroup$ @Anthony: Very nice to connect this situation to random walks---Thanks! $\endgroup$ Jul 15, 2012 at 12:36
  • $\begingroup$ In so far as the growth rate you identify can be interpreted as "most strings are foldable," I find that surprising, because only those strings whose every digit $d$ is adjacent to digit $d \pm 1$ is foldable. Of course perhaps there is a constant diminishing as $b \to \infty$... $\endgroup$ Jul 15, 2012 at 13:16
  • $\begingroup$ All strings are $b^n$, a far cry from "almost $2^n$". Most strings are not foldable. $\endgroup$
    – Will Sawin
    Jul 15, 2012 at 13:41
  • $\begingroup$ So I'm looking at this again. I believe the conclusion is correct but my approach was incorrect! I (now) think the growth rate is the top eigenvalue of the adjacency matrix of the directed graph with vertices $\{1L,1R,2L,2R,\ldots,bL,bR\}$ where $iL$ and $iR$ are connected by a double edge; $iL$ connects to $(i-1)L$ and $iR$ connects to $(i+1)R$. Since almost every vertex has 2 edges coming out, the top eigenvalue will be close to 2. Conversely, given any path in this graph, it's fairly easy to translate it to a "stamp folding". $\endgroup$ Aug 10, 2015 at 21:44
3
$\begingroup$

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).

$\endgroup$
2
  • $\begingroup$ Sorry, first version contained an error (i.e. the formula was wrong), but I fixed that $\endgroup$ Jul 16, 2012 at 0:08
  • $\begingroup$ @Florian: Your example for $b=3$ accords exactly with my computational count. Impressive! Note I remark in an addendum that this is OEIS A154691. $\endgroup$ Jul 16, 2012 at 1:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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