Number of strings of $\{0,1,2\}$ : the longest substrings of $1$ is odd-length.

Question

Consider $A^* = \{0,1,2\}^*$. We want to know how many string of length $n$ in this alphabet following such property : all longest substrings of 1-s has odd length(let it be $a_n$).

I know that it can be founded by regular-sequence, but I don't understand how to generate it.

Essential edits:

1. We don't consider zero numbers of $1s$.
2. Longest means maximal, i.e. $111011$, $1110111$ are valid, $11101111$ invalid.

So I've tried to consider some extra cases :

$a_1 = 1,a_2 = 4(10,12,01,21),a_3 = 15,a_4 = 48$. The OEIS gives me that it should be $a_n = n Pell(n)$. Maybe it's possible to show it somehow?

Answer 1

This is a partial solution. It provides a recurrence relation which allows manual calculation for small values of $n$, and makes it easier to get solutions for larger $n$ from Mathematica etc.

Let $g(n,k)$ denote the number of strings length $n$ with $k$ as the longest run of 1s. We have the following equations:

$g(n,0)=2^n$

$g(n,n)=1$

$g(n,n-1)=4\text{ for }n\ge2$

$g(n,k)=0\text{ for }n<k$

$g(n,k)=2\sum_{h=1}^kg(n-\,h,k)+2\sum_{h=0}^kg(n-\,k-\,1,k-\,h)$

The terms in the first sum of the last equation correspond to adding a non-1 followed by $h-1$ 1s. So $h=0$ gives strings ending with a non-1, whilst higher $h$ give strings ending with a run of 1s of length $<k$. The terms in the second sum correspond to strings ending with a run of $k$ 1s.

So we get:

$n=1: 2,1$

$n=2: 4,4,1$

$n=3: 8,14,4,1$

$n=4: 16,44,16,4,1$

$n=5: 32,132,58,16,4,1$

$n=6: 64,384,200,60,16,4,1$

$n=7: 128,1096,668,214,60,16,4,1$

As a check we see that the totals for each $n$ are just $3^n$. The sum of the odd maximum lengths gives: $$1,4,15,48,149,448,1327$$. These are the numbers sought in the question. Note that the sequence is not OEIS93967,

Answer 2

We show the wanted numbers $a_q$ have a generating function \begin{align*} \color{blue}{A(z)=\sum_{q=0}^\infty a_qz^q=\sum_{q=0}^\infty (-1)^{q+1}\frac{1-z^{q+1}}{1-3z+2z^{q+2}}}\tag{1} \end{align*} and derive from it an explicit expression for the coefficients $a_n=[z^n]A(z)$.

Generating function:

We start with the generating function of a ternary alphabet $\{0,1,2\}$ which provides the number of words with no consecutive equal characters at all. Such words are called Smirnov or Carlitz words. See example III.24 Smirnov words in Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick for more information. A generating function is \begin{align*} \left(1-\frac{u}{1+u}-\frac{v}{1+v}-\frac{w}{1+w}\right)^{-1}\tag{2} \end{align*} where the coefficient of the term $u^av^bw^c$ with $a+b+c=n$ denotes the number of words of length $n$ consisting of $a$ $0$s, $b$ $1$s and $c$ $2$s having no runs of characters with length $\geq 2$.

• We do not have any restrictions on $0$ and $2$ and so we replace in (2) occurrences of these characters by \begin{align*} u&\to z+z^2+z^3+\cdots=\frac{z}{1-z}\\ w&\to z+z^2+z^3+\cdots=\frac{z}{1-z}\\ \end{align*}

• We consider words which have longest runs of $1$ with length $\leq q$. We therefore substitute \begin{align*} v\to z+z^2+z^3+\cdots+z^q=\frac{z\left(1-z^q\right)}{1-z} \end{align*}

We so derive from (2) and from the substitutions above a generating function $A_q(z)$ which counts words having longest runs of $1$ with length $\leq q$: \begin{align*} \color{blue}{A_q(z)}&=\left(1-\frac{2\frac{z}{1-z}}{1+\frac{z}{1-z}}+\frac{\frac{z\left(1-z^q\right)}{1-z}}{1+\frac{z\left(1-z^q\right)}{1-z}}\right)^{-1}\\ &=\left(1-2z-\frac{z\left(1-z^{q}\right)}{1-z^{q+1}}\right)^{-1}\\ &\,\,\color{blue}{=\frac{1-z^{q+1}}{1-3z+z^{q+2}}}\tag{3} \end{align*} We use the $A_q(z)$ as building blocks for the generating function $A(z)$. At first we note that the number of words which have precisely a longest run of $1$ with odd length $2q+1$ is given by \begin{align*} A_{2q+1}(z)-A_{2q}(z)\qquad\qquad q\geq 0 \end{align*} and the generating function $A(z)$ counting words with longest run $1$ with odd length is therefore \begin{align*} \color{blue}{A(z)}&=\sum_{q=0}^{\infty}\left(A_{2q+1}(z)-A_{2q}(z)\right) \color{blue}{=\sum_{q=0}^{\infty}(-1)^{q+1}A_q(z)}\tag{4} \end{align*}

Since words which have longest run $1$ with length $2q+1$ we expect that \begin{align*} A_{2q+1}(z)-A_{2q}(z)=z^{2q+1}+a_{2q_2}z^{2q+2}+a_{2q+3}z^{2q+3}+\cdots \end{align*} with coefficients less than $2q+1$ being equal to zero. In fact when looking for $A_q(z)$ and differences of these generating functions for small values of $q$ we see with some help of Wolfram Alpha \begin{align*} \begin{array}{r|rrrrrrrrr} n&0&1&2&3&4&5&6&7&8\\ \hline A_0(z)&\color{blue}{1}&2&4&8&16&32&64&128&256\\ A_1(z)&\color{grey}{1}&\color{blue}{3}&8&22&60&164&448&1\,224&3\,344\\ A_2(z)&\color{grey}{1}&\color{grey}{3}&\color{blue}{9}&26&76&222&648&1\,882&5\,524\\ A_3(z)&\color{grey}{1}&\color{grey}{3}&\color{grey}{9}&\color{blue}{27}&80&238&708&2\,106&6\,264\\ A_4(z)&\color{grey}{1}&\color{grey}{3}&\color{grey}{9}&\color{grey}{27}&\color{blue}{81}&242&724&2\,166&6\,480\\ A_5(z)&\color{grey}{1}&\color{grey}{3}&\color{grey}{9}&\color{grey}{27}&\color{grey}{81}&\color{blue}{243}&728&2\,182&6\,540\\ A_6(z)&\color{grey}{1}&\color{grey}{3}&\color{grey}{9}&\color{grey}{27}&\color{grey}{81}&\color{grey}{243}&\color{blue}{729}&2\,186&6\,540\\ A_7(z)&\color{grey}{1}&\color{grey}{3}&\color{grey}{9}&\color{grey}{27}&\color{grey}{81}&\color{grey}{243}&\color{grey}{729}&\color{blue}{2\,187}&6\,560\\ A_8(z)&\color{grey}{1}&\color{grey}{3}&\color{grey}{9}&\color{grey}{27}&\color{grey}{81}&\color{grey}{243}&\color{grey}{729}&\color{grey}{2\,187}&\color{blue}{6\,561}\\ \hline \left(A_1-A_0\right)(z)&&1&4&14&44&132&384&1\,096&3\,088\\ \left(A_3-A_2\right)(z)&&&&1&4&16&60&214&740\\ \left(A_5-A_4\right)(z)&&&&&&1&4&16&60\\ \left(A_7-A_6\right)(z)&&&&&&&&1&4\\ \hline \color{blue}{A(z)}&&\color{blue}{1}&\color{blue}{4}&\color{blue}{15}&\color{blue}{48}&\color{blue}{149} &\color{blue}{448}&\color{blue}{1\,327}&\color{blue}{3\,892} \end{array} \end{align*}

We obtain from (2)-(4) and the table \begin{align*} \color{blue}{A(z)}&=\sum_{q=0}^{\infty}(-1)^{q+1}A_q(z)\\ &\color{blue}{=\sum_{q=0}^{\infty}(-1)^{q+1}\frac{1-z^{q+1}}{1-3z+z^{q+2}}}\tag{5}\\ &=z+4z^2+15z^3+48z^4+\color{blue}{149}z^5+448z^6+1\,327z^7+3\,892z^8+\cdots \end{align*}

Formula for $a_n=[z^n]A(z)$:

We start with deriving from (3) the coefficient $[z^n]$ of $A_q(z)$. We obtain \begin{align*} \color{blue}{[z^n]A_q(z)}&=[z^n]\frac{1-z^{q+1}}{1-3z+z^{q+2}}\\ &=[z^n]\sum_{k=0}^\infty z^k\left(3-2z^{q+1}\right)^k\left(1-z^{q+1}\right)\tag{6.1}\\ &=\sum_{k=0}^n [z^{n-k}]\left(3-2z^{q+1}\right)^k\left(1-z^{q+1}\right)\tag{6.2}\\ &=\sum_{k=0}^n [z^{k}]\left(3-2z^{q+1}\right)^{n-k}\left(1-z^{q+1}\right)\tag{6.3}\\ &=\sum_{k=0}^{\left\lfloor\frac{n}{q+1}\right\rfloor} [z^{(q+1)k}]\left(3-2z^{q+1}\right)^{n-(q+1)k}\left(1-z^{q+1}\right)\tag{6.4}\\ &=\sum_{k=0}^{\left\lfloor\frac{n}{q+1}\right\rfloor} [z^{(q+1)k}] \sum_{j=0}^{n-(q+1)k}\binom{n-(q+1)k}{j}\left(-2z^{(q+1)}\right)^j\tag{6.5}\\ &\qquad\qquad\qquad\qquad\qquad\qquad\cdot3^{n-(q+1)k-j}\left(1-z^{q+1}\right)\\ &=\sum_{k=0}^{\left\lfloor\frac{n}{q+1}\right\rfloor} \binom{n-(q+1)k}{k}(-2)^k3^{n-(q+2)k}\\ &\qquad\qquad-\sum_{k=0}^{\left\lfloor\frac{n}{q+1}\right\rfloor} \binom{n-(q+1)k}{k-1}(-2)^k3^{n+1-(q+2)k}\tag{6.6}\\ &\,\,\color{blue}{=3^n+\sum_{k=1}^{\left\lfloor\frac{n}{q+1}\right\rfloor} \left(\binom{n-(q+1)k}{k}\right.}\\ &\qquad\qquad\qquad\qquad\color{blue}{\left.+\frac{3}{2}\binom{n-(q+1)k}{k-1}\right)(-2)^k3^{n-(q+2)k}}\tag{6.7} \end{align*}

Comment:

• In (6.1) we use a geometric series expansion*.

• In (6.2) we apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$. We also set the upper limit of the sum to $n$ since other terms do not contribute.

• In (6.3) we change the order of summation: $k\to n-k$.

• In (6.4) we filter terms which are a multiple of $q+1$, since other terms do not contribute.

• In (6.5) we apply the binomial theorem.

• In (6.6) we select the coefficient of $z^{(q+1)k}$.

• In (6.7) we so some simplifications.

We finally obtain the coefficients $a_{2n+1}$ and $a_{2n}$ as \begin{align*} \color{blue}{a_{2n+1}}&=[z^{2n+1}]\left(\left(A_{2n+1}(z)-A_{2n}(z)\right)+\left(A_{2n-1}(z)-A_{2n-2}(z)\right)\right.\\ &\qquad\qquad\qquad\left.+\cdots+\left(A_1(z)-A_0(z)\right)\right)\\ &=[z^{2n+1}]\sum_{q=0}^{2n+1}(-1)^qA_q(z)\\ &\,\,\color{blue}{=\sum_{q=0}^{2n+1}(-1)^q\sum_{k=1}^{\left\lfloor\frac{2n+1}{q+1}\right\rfloor} \left(\binom{2n+1-(q+1)k}{k}\right.}\\ &\qquad\qquad\qquad\qquad\color{blue}{\left.+\frac{3}{2}\binom{2n+1-(q+1)k}{k-1}\right)(-2)^k3^{2n+1-(q+2)k}}\\ \color{blue}{a_{2n}}&\color{blue}{=[z^{2n}]\sum_{q=0}^{2n+1}(-1)^qA_q(z)}\\ \end{align*}

Example: $a_{5}=149$

Finally we look at a specific example and list from (5) the blue marked $149$ valid words of length $5$.

We obtain \begin{align*} \begin{array}{cccccccccc} 00001&00010&00012&00021&00100&00102&00120&00122&00201&00210\\ 00212&00221&01000&01002&01020&01022&01200&01202&01220&01222\\ 02001&02010&02012&02021&02100&02102&02120&02122&02201&02210\\ 02212&02221&10000&10002&10020&10022&10200&10202&10220&10222\\ 12000&12002&12020&12022&12200&12202&12220&12222&20001&20010\\ 20012&20021&20100&20102&20120&20122&20201&20210&20212&20221\\ 21000&21002&21020&21022&21200&21202&21220&21222&22001&22010\\ 22012&22021&22100&22102&22120&22122&22201&22210&22212&22221\\ \\ 00101&00121&01001&01010&01012&01021&01201&01210&01212&01221\\ 02101&02121&10001&10010&10012&10021&10100&10102&10120&10122\\ 10201&10210&10212&10221&12001&12010&12012&12021&12100&12102\\ 12120&12122&12201&12210&12212&12221&20101&20121&21001&21010\\ 21012&21021&21201&21210&21212&21221&22101&22121\\ \\ 10101&10121&12101&12121\\ \\ 00111&01110&01112&02111&11100&11102&11120&11122&20111&21110\\ 21112&22111\\ \\ 10111&11101&11121&12111\\ \\ 11111 \end{array} \end{align*}