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$
  • $\begingroup$ for the general case of q-ary words refer to this other post $\endgroup$ – G Cab Apr 3 '17 at 18:10
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$
  • $\begingroup$ fixed the typos $\endgroup$ – Pat Needham Apr 4 '12 at 2:21
  • $\begingroup$ @Pat: And I’ve removed the parenthetical note. $\endgroup$ – Brian M. Scott Apr 4 '12 at 2:26
  • $\begingroup$ thank you very much for confirming my conjecture $\endgroup$ – Pat Needham Apr 4 '12 at 2:36
  • $\begingroup$ @BrianM.Scott what if string end with $12$ ,$21$,$22$,$11$ ? $\endgroup$ – virat Oct 3 '16 at 7:48
  • 1
    $\begingroup$ @sourav: Those possibilities are all covered by the second sentence of the answer. $\endgroup$ – Brian M. Scott Oct 3 '16 at 9:14
2
$\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$
1
$\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$
  • $\begingroup$ The third term must have a $+$ sign. $\endgroup$ – Muralidharan Apr 4 '18 at 12:07
  • $\begingroup$ @Muralidharan: you are right, now fixed, thanks. $\endgroup$ – Jack D'Aurizio Apr 4 '18 at 12:09

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.