13
$\begingroup$

The question is: Find a recurrence relation for number of ternary strings of length n that contain two consecutive zeros.

I know for ternary strings with length one, there are 0. For a length of 2, there is just 1 (00), and for a length of 3, there are 5 (000,001,002,100,200).

I did a similar problem, finding a relation for the number of bit strings of length n with two consecutive zeros: $$a_n = a_{n-1} + a_{n-2} + 2^{n-2}$$

Since you can add "1" to the end of all the $a_{n-1}$ strings, "10" to all the $a_{n-2}$ strings, and "00" any string of size $n-2$.

For the ternary string problem, I'm pretty sure you would replace the $2^{n-2}$ with $3^{n-2}$, but confused about the other terms of the relation. My guess is that it would have the coefficient $2$ in front of the other terms, since you can add either $1$ or $2$ to the end of $a_{n-1}$ and either $01$ or $02$ at the end of $a_{n-1}$.

So I believe the answer for the relation is: $$a_n = 2a_{n-1} + 2a_{n-2} + 3^{n-2}$$

How does that look?

$\endgroup$
3
  • $\begingroup$ for the general case of q-ary words refer to this other post $\endgroup$
    – G Cab
    Apr 3, 2017 at 18:10
  • $\begingroup$ The recurrence relation is in oeis.org/A186244 . $\endgroup$ Feb 13, 2022 at 13:40
  • $\begingroup$ Thank you @R.J.Mathar. I was coincidentally thinking about my Discrete Math professor from the class I took 10 years ago recently. He made some witty comment about making sure we submit the homework assignments online before midnight a day before it was due in case the whole internet becomes unavailable due to the protests against SOPA and PIPA $\endgroup$ Feb 14, 2022 at 0:06

3 Answers 3

13
$\begingroup$

If a ‘good’ ternary string of length $n$ ends in $00$, the first $n-2$ elements can be anything, so there are indeed $3^{n-2}$ such strings. If a good string of length $n$ ends in $1$ or $2$, its initial substring of length $n-1$ must be good; that accounts for $2a_{n-1}$ more good strings of length $n$, since each of the shorter strings can be extended with either $1$ or $2$. What hasn’t been counted? Good strings of length $n$ that end in a $10$ or $20$. Each of these must be an extension of a good string of length $n-2$, so there are $2a_{n-2}$ of them, and your conjecture is correct: $$a_n=2a_{n-1}+2a_{n-2}+3^{n-2}\;.$$

$\endgroup$
9
  • $\begingroup$ fixed the typos $\endgroup$ Apr 4, 2012 at 2:21
  • $\begingroup$ @Pat: And I’ve removed the parenthetical note. $\endgroup$ Apr 4, 2012 at 2:26
  • 1
    $\begingroup$ @sourav: Those possibilities are all covered by the second sentence of the answer. $\endgroup$ Oct 3, 2016 at 9:14
  • 1
    $\begingroup$ @mathophile: $000$ is the fifth string. You’ve misunderstood contains two consecutive zeroes: it means contains the substring $00$, which $000$ certainly does. In fact, $000$ has two such substrings, the red ones here: $\color{red}{00}0$, $0\color{red}{00}$ $\endgroup$ Feb 9, 2023 at 19:53
  • 1
    $\begingroup$ @mathophile: I don’t offhand see any way to do so. $\endgroup$ Feb 10, 2023 at 22:25
3
$\begingroup$

You may also get an explicit formula directly, by invoking Markov chains / deterministic finite automata.
This is the DFA which accepts the strings over $\Sigma=\{0,1,2\}$ with at least two consecutive $0$s:

enter image description here

Its transition matrix is given by $$ P = \begin{pmatrix}2& 1 & 0 \\ 2 & 0 & 1 \\ 0 & 0 & 3 \end{pmatrix} $$ and the characteristic polynomial of this matrix is $(x-3)(x^2-2x-2)$. It follows that the number of strings over $\Sigma$ having length $n$ and containing at least two consecutive $0$s is $$ L_n = A\cdot 3^n + B\cdot (1+\sqrt{3})^n + C \cdot (1-\sqrt{3})^n $$ for some constants $A,B,C$ which can be found by interpolation. Since $L_1=0, L_2=1$ and $L_3=5$ $$\boxed{L_n=3^n-\left(\tfrac{1}{\sqrt{3}}+\tfrac{1}{2}\right)(1+\sqrt{3})^n+\left(\tfrac{1}{\sqrt{3}}-\tfrac{1}{2}\right)(1-\sqrt{3})^n\;}$$ which clearly fulfills the recurrence relation mentioned by Brian Scott.

$\endgroup$
2
  • $\begingroup$ The third term must have a $+$ sign. $\endgroup$ Apr 4, 2018 at 12:07
  • $\begingroup$ @Muralidharan: you are right, now fixed, thanks. $\endgroup$ Apr 4, 2018 at 12:09
3
$\begingroup$

Let us count the number of strings $a_n$ that do not contain $00$ as a substring. The required number of strings that contain $00$ is $3^n - a_n$.

Let us call a string that does not contain $00$ as good. Let $x_n, y_n, z_n$ be the number of good strings of length $n$ that end with $0, 1, 2$ respectively. Clearly, \begin{align*} x_{n+1} &= y_n + z_n \\ y_{n+1} &= x_n + y_n + z_n \\ z_{n+1} &= x_n + y_n + z_n \end{align*} Thus \begin{align*} y_n = z_n, \qquad x_{n+1} = 2y_n, \qquad y_{n+1} = x_n + 2y_n \end{align*} and $y_n$ satisfies the recurrence $y_{n+1} - 2y_n - 2y_{n-1} = 0$. The characteristic roots are $1 \pm \sqrt{3}$ and $$y_n = A(1+\sqrt{3})^n + B(1-\sqrt{3})^n$$ where $A, B$ are constants. Since $y_2 = 3$ and $y_3 = 8$ we get $$A = \frac{1+\sqrt{3}}{4\sqrt{3}}, \qquad B=-\frac{1-\sqrt{3}}{4\sqrt{3}}$$ Hence $$y_n = \frac{1}{4\sqrt{3}}\left(\alpha^{n+1} -\beta^{n+1}\right) $$ Since $a_n = x_n + y_n + z_n = 2y_{n-1} + 2y_n$, we get \begin{align*} a_n &= \frac{1}{2\sqrt{3}}\left(\alpha^n(1+\alpha) - \beta^n(1+\beta)\right)\\ &= \left(\frac{2+\sqrt{3}}{2\sqrt{3}}\right)\alpha^n - \left(\frac{2-\sqrt{3}}{2\sqrt{3}}\right)\beta^n \end{align*} Hence the number of sequences of length $n$ that contain $00$ is $$3^n - \left(\frac{2+\sqrt{3}}{2\sqrt{3}}\right)(1+\sqrt{3})^n + \left(\frac{2-\sqrt{3}}{2\sqrt{3}}\right)(1-\sqrt{3})^n$$

$\endgroup$

You must log in to answer this question.

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