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 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 at 0:06

3 Answers 3

12
$\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$
5
  • $\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
  • $\begingroup$ thank you very much for confirming my conjecture $\endgroup$ Apr 4, 2012 at 2:36
  • $\begingroup$ @BrianM.Scott what if string end with $12$ ,$21$,$22$,$11$ ? $\endgroup$ Oct 3, 2016 at 7:48
  • 1
    $\begingroup$ @sourav: Those possibilities are all covered by the second sentence of the answer. $\endgroup$ Oct 3, 2016 at 9:14
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$

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.