show/hide this revision's text 2 added 720 characters in body

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)} .$$
show/hide this revision's text 1

Combinatorics of folding digit strings

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!