4
$\begingroup$

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?

$\endgroup$
13
  • 1
    $\begingroup$ @RossMillikan my bad! Edited. Thanks for noting $\endgroup$
    – openspace
    Jan 17, 2020 at 5:50
  • 1
    $\begingroup$ Then the last of the $a_2$s should be $21$, not $02$. Why do you think that is the correct sequence? $\endgroup$ Jan 17, 2020 at 5:51
  • 1
    $\begingroup$ @RossMillikan yes, you're right $\endgroup$
    – openspace
    Jan 17, 2020 at 5:55
  • 2
    $\begingroup$ Note that Ross' comment above is on the original question, which had "even" instead of "odd". Please mark such fundamental edits as edits so that people can make sense of the comments. $\endgroup$
    – joriki
    Jan 17, 2020 at 6:28
  • 3
    $\begingroup$ @joriki. Ah, thanks! So on that basis, the strings length 4 would be $111x,x111,1xxx,x1xx,xx1x,xxx1,1x1x,1xx1,x1x1$ total 48. But I seem to get 149 instead of 145 for length 5: $11111,111xx (12),1xxxx (80),1x111 (4),1x1xx (48)$ and $1x1x1$ (4). $\endgroup$
    – almagest
    Jan 17, 2020 at 13:04

2 Answers 2

3
$\begingroup$

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*}

$\endgroup$
2
  • 1
    $\begingroup$ I've yet to get to the end... but: would it be better to write that, the number of words with $a$ instances of $X$, $b$ of $Y$, and $c$ of $Z$, no two consecutive letters equal, is the coefficient of $x^ay^bz^c$ in $(1-\frac{x}{1+x}-\frac{y}{1+y}-\frac{z}{1+z})^{-1}$ and then do substitutions of generating functions (counting letters) in for $x$ and $y$ and $z$. It's just a little weird how we're replacing things in equation (2) when there don't seem to be things to replace. $\endgroup$ Sep 22, 2021 at 21:05
  • 1
    $\begingroup$ @MiloBrandt: Many thanks for your hint. I agree and I've updated my answer accordingly. :-) $\endgroup$ Sep 23, 2021 at 16:05
1
$\begingroup$

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,

$\endgroup$
2
  • 1
    $\begingroup$ I don't think this is correct because we only consider the longest sequence of $1$s. If I start with $15\ 1$s and a $0$ the next $15$ numbers can be anything. $\endgroup$ Jan 17, 2020 at 15:35
  • 1
    $\begingroup$ @RossMillikan Many thanks. I failed to read the question carefully enough and thought that all the runs of 1s had to have odd length. Now rewritten. But I cannot see a closed form solution. $\endgroup$
    – almagest
    Jan 18, 2020 at 17:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .