4
$\begingroup$

I'm trying to figure out how to find the number of ternary strings of length $n$ that have 3 or more consecutive 2's. So far I've been able to establish that there is $n(2^{n-1})$ with a single 2. And I think (but am not certain) that this can be extrapolated to the number of strings with a single group of 2's of length $x$ by: $$\bigl(n-(x-1)\bigr)(2^{n-x})$$ What I'm getting caught on is the 'or more part', any help would be greatly appreciated.

$\endgroup$
4
$\begingroup$

Denote by $c_n$ the number of ternary words containing no $222$. Then $c_1=3$, $c_2=9$, $c_3=26$, and we have the recursion $$c_n=2c_{n-1}+2c_{n-2}+2c_{n-3}\qquad(n\geq4)\ .\tag{1}$$ Proof. An admissible word $w$ can begin with $Z$, $2Z$, or $22Z$ with $Z\in\{0,1\}$, followed by an admissible word $w'$.

Unfortunately the characteristic equation of $(1)$ has no rational roots, hence it remains to list the first few values: $$(c_n)_{n\geq1}=(3, 9, 26, 76, 222, 648, 1892, 5524, 16128, 47088, 137480, 401392,\ldots)\ .$$ The values $a_n=3^n-c_n$ required by the OP then are $$(a_n)_{n\geq1}=(0, 0, 1, 5, 21, 81, 295, 1037, 3555, 11961, 39667, 130049,\ldots)\ .$$

$\endgroup$
1
  • $\begingroup$ Very nice and exemplary approach. (+1) $\endgroup$ – Markus Scheuer Apr 14 '18 at 18:53
3
$\begingroup$

We consider the alphabet $V=\{0,1,2\}$ and we are looking for the number $c_n$ of strings of length $n$ having runs of $2$ less than three. The wanted number is $$a_n=3^n-c_n$$

We derive a generating function $C(z)=\sum_{n=0}^\infty c_nz^n$ from which the number $a_n$ can be obtained easily since \begin{align*} a_n=[z^n]\left(\frac{1}{1-3z}-C(z)\right)\tag{1} \end{align*} with $[z^n]$ denoting the coefficient of $z^n$ of a series.

Strings with no consecutive equal characters at all are called Smirnov or Carlitz words. See example III.24 Smirnov words from Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick for more information.

A generating function for the number of Smirnov words over a ternary alphabet $V$ is given by \begin{align*} \left(1-\frac{3z}{1+z}\right)^{-1}\tag{2} \end{align*}

Replacing occurrences of $0$ in a Smirnov word by one or more zeros generates words having runs of $0$ with length $\geq 1$. \begin{align*} z\longrightarrow z+z^2+z^3+\cdots=\frac{z}{1-z} \end{align*}

The same can be done with the digit $1$.

Replacing occurrences of $2$ in a Smirnov word by one or two $2$'s generates words with runs of $2$ of length less than three. \begin{align*} z\longrightarrow z+z^2=z(1+z) \end{align*}

The resulting generating function is according to (2) \begin{align*} \color{blue}{C(z)}=\left(1- 2\cdot\frac{\frac{z}{1-z}}{1+\frac{z}{1-z}}-\frac{z(1+z)}{1+z(1+z)}\right)^{-1} &\color{blue}{=\frac{1+z+z^3}{1-2z-2z^2-2z^3}}\tag{3} \end{align*}

We obtain for $n\geq 3$ the number of wanted words of length $n$ according to (1) and (3) as \begin{align*} \color{blue}{a_n}&=3^n-c_n\\ &=[z^n]\left(\frac{1}{1-3z}-\frac{1+z+z^3}{1-2z-2z^2-2z^3}\right)\\ &=[z^n]\left(\color{blue}{1}z^3+\color{blue}{5}z^4+\color{blue}{21}z^5+\color{blue}{81}z^6+\color{blue}{295}z^7+\color{blue}{1\,037}z^8+\color{blue}{3\,555}z^9+\cdots\right) \end{align*}

whereby the last line was obtained with some help of Wolfram Alpha.

$\endgroup$
1
  • $\begingroup$ Hi, Markus, very nice (+1), and ..here we are with another pair of symplectic answers ! $\endgroup$ – G Cab Apr 14 '18 at 16:47
1
$\begingroup$

Trying to count them directly will get you nowhere, because of double counting. The best approach is to come up with a recurrence relation, for the number of acceptable strings of length $n$ in terms of the number of shorter acceptable strings. Call a ternary string with at least three consecutive $2$'s "good" and other ternary strings "bad".

Let $a_n$ be the number of good strings of length $n$. To make a good string of length $n+1$ we can add any digit to an good string of length $n$ or we can add a $2$ to the end of a bad string of length $n$ that ends in two $2$'s. So we have $$a_{n+1}=3a_n+b_n$$ So, how many bad strings of length $n$ end in two $2$'s? We get them by adding two $2$'s to a a bad string of length $n-2$ that doesn't end in a $2$. $$b_{n}=c_{n-2}$$ So, how many bad strings of length $n-2$ don't end in $2$? We just add $0$ or $1$ to a bad string of length $n-3$, and there are $3^{n-3}-a_{n-3}$ bad strings of length $n-3$. $$ a_{n+1}=3a_{n}+2(3^{n-3}-a_{n-3})\implies a_{n+1}-3{a_n}+2a_{n-3}=2\cdot 3^{n-3}\tag 1$$

(I think the definitions of $b_n, c_n$ are obvious from the context.)

We have the initial data $$a_0=a_1=a_2=0,a_3=1$$

A little experimentation with python confirms this formula. The recurrence is not easy to solve. Besides the obvious root at $1$, the characteristic equation has one positive root, which Wolfram Alpha calculates as $2.9196.$ (You can click on the "Exact Forms" button to get the expression in terms of radicals, for what it's worth.)

You can try to use the RSolve feature of Wolfram Alpha to get an exact solution. I have no experience with this myself.

For grins, I did it with RSolve.

I also wrote a python script to calculate it up to $n=15$ in three different ways: explicitly, by generating the ternanry strings and counting the good ones, from the recurrence relation, and from the approximate formula from Wolfram Alpha. Here's the code:

from itertools import product

print("Explicit")
chars = '0 1 2'.split()
for n in range(4,16):
    print(n, len([s for s in product(chars, repeat=n) if '222' in ''.join(s)]))

print("Recurrence")
a=[0,0,0,1]
for n in range(4,16):
    a.append(3*a[n-1]-2*a[n-4]+2*3**(n-4))
    print(n, a[n])

r1 = .0231038-.0550705j
r2 = -.45982+.688173j
r3 = -1.04621
r4 = 2.91964

print("Formula")
for n in range(3,16):
    x = r1*r2**n
    print(n, 2*x.real+r3*r4**n+3**n)

This produced the output:

Explicit
4 5
5 21
6 81
7 295
8 1037
9 3555
10 11961
11 39667
12 130049
13 422403
14 1361385
15 4359115
Recurrence
4 5
5 21
6 81
7 295
8 1037
9 3555
10 11961
11 39667
12 130049
13 422403
14 1361385
15 4359115
Formula
3 0.9999269125799088
4 4.999775013651643
5 20.999310049238204
6 80.99788957631085
7 294.99355667854866
8 1036.9803663807425
9 3554.940278866641
10 11960.818633386094
11 39666.45003106547
12 130047.3346004755
13 422397.96336414735
14 1361369.7860350916
15 4359069.095182693

The recurrence gives the exact value, and is more efficient to compute than the approximate formula. Of course, it would be possible to get exact values for the constants in the formula, since they're the roots of cubics, but that would make the formula even harder to compute.

$\endgroup$
4
  • $\begingroup$ If I follow correctly, $b_{n-1}$ should be $b_n$ and so on? $\endgroup$ – Joffan Apr 11 '18 at 16:29
  • $\begingroup$ @Joffan Yes. I just checked with a python script, and I'm getting the wrong numbers. No doubt you've put your finger on it. Will edit. $\endgroup$ – saulspatz Apr 11 '18 at 16:48
  • $\begingroup$ That gives $a_4$ correctly now, good edit. $\endgroup$ – Joffan Apr 11 '18 at 16:54
  • $\begingroup$ I checked it out to $a_{10}$ with python, and it works. $\endgroup$ – saulspatz Apr 11 '18 at 17:10
1
$\begingroup$

Following another approach, consider a binary word, where the one stands for the ternary $2$ and the zero stands for $0,1$.

Take a binary word of length $n$, having $s$ ones and $n-s$ zeros in total, with no more than $r$ consecutive ones.

Now the number of such binary words is given by
$$ \eqalign{ & M_b (s,r,n) = N_b (s,r,n - s + 1)\quad \left| {\;0 \le {\rm integers }s,n,r} \right.\quad = \cr & = \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,\min \left( {{s \over {r + 1}}\,,\,n - s + 1} \right)} \right)} {\left( { - 1} \right)^k \left( \matrix{ n - s + 1 \cr k \cr} \right)\left( \matrix{ n - k\left( {r + 1} \right) \cr s - k\left( {r + 1} \right) \cr} \right)} \cr} $$ as explained in this related post.

Coming back to the ternary words, we just have to multiply $N_b$ by the number of ways to pad the $n-s$ zeros with $0$ or $1$. So in general we have $$ \eqalign{ & M_t (s,r,n) = 2^{\,n - s} M_b (s,r,n) = \cr & = 2^{\,n - s} \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,\min \left( {{s \over {r + 1}}\,,\,n - s + 1} \right)} \right)} {\left( { - 1} \right)^k \left( \matrix{ n - s + 1 \cr k \cr} \right)\left( \matrix{ n - k\left( {r + 1} \right) \cr s - k\left( {r + 1} \right) \cr} \right)} \cr} $$ which summed over $s$ gives
$T(r,n)=$ the number of ternary strings of length $n$ having max $r$ consecutive two's $$ \bbox[lightyellow] { T(r,n) = \sum\limits_{\left( {0\, \le } \right)\,\,s\,\,\left( { \le \,n} \right)} {2^{\,n - s} \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,\min \left( {{s \over {r + 1}}\,,\,n - s + 1} \right)} \right)} {\left( { - 1} \right)^k \left( \matrix{ n - s + 1 \cr k \cr} \right)\left( \matrix{ n - k\left( {r + 1} \right) \cr s - k\left( {r + 1} \right) \cr} \right)} } }$$

Note that it can be easily extended to quaternary, quinary, ... words.

For your particular case then, the number is given by $3^n-T(2,n)$, which checks with the formulas already given in the precedent answers.

$\endgroup$
1
  • $\begingroup$ Nice application of your general answer.(+1) $\endgroup$ – Markus Scheuer Apr 14 '18 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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