7
$\begingroup$

QUESTION:

A string that contains only 0s, 1s, and 2s is called a ternary string. Find a recurrence relation for the number of ternary strings of length n that do not contain two consecutive 0s or two consecutive 1s.

--

My approach:

Let's define a in-valid string, as the ternary string that contain two consecutive 0's or 1's, $b_n$. Now, let $a_n$ be the number of valid strings. We need to substract the number of in-valid ($b_n$) strings from the number of ternary strings, $3^n$. To count $b_n$, use the sum rule: partition the set of strings, depending on what digits start the string:

  1. The string that starts with a 2: $b_{n-1}$ ways to finish the string.
  2. The string that starts with a 1:
    • The remaining strings that start with a 0: $b_{n-2}$ ways to end the string.
    • The remaining strings that start with a 1: $3^{n-2}$ ways to finish the string.
    • The remaining strings that start with a 2: $b_{n-2}$ ways to finish the string.
  3. The string that starts with a 0:
    • The remaining strings that start with a 0: $3^{n-2}$ ways to end the string.
    • The remaining strings that start with a 1: $b_{n-2}$ ways to finish the string.
    • The remaining strings that start with a 2: $b_{n-2}$ ways to finish the string.

Summing it up, $b_n = b_{n-1} + 4b_{n-2} + 2\cdot(3^{n-2})$.

Note that the initial conditions are: $b_0 = b_1 = 0$.

Also note that this recurrence relation counts the number of in-valid strings; that is the ternary strings that contain two consecutive 0's or 1's. In order to obtain the number of valid ternary strings we would need to substract this from the total number of ternary strings, $3^n$. Hence we could use $a_n = 3^n - b_n$ where $a_n$ is the number of (valid) ternary strings that do not contain two consecutive 1's or 0's.

I tried for $b_2$ and $b_3$ but it does not give the right answers. What am I doing wrong?

$\endgroup$
5
$\begingroup$

What you're missing is that there are more than $b_{n-2}$ invalid ways to finish a string that starts with 10 -- namely, the rest of the string could start with 0 but otherwise be valid. And similarly for strings that start with 01.


The natural way to set up a recurrence would be to let $a_n$ be the number of valid strings of length $n$ that start with 0 or 1, and $c_n$ be the number of valid strings that start with 2. We then have $$ \begin{align} a_{n+1} &= a_n + 2c_n \\ c_{n+1} &= a_n + c_n \end{align} $$ and we get $$ \begin{pmatrix} a_n \\ c_n \end{pmatrix} = \begin{pmatrix}1&2\\1&1\end{pmatrix}^{n-1} \begin{pmatrix}2\\1\end{pmatrix} $$ and we can then try to diagonalize the matrix to find a closed solution to the recurrence.

In this particular case, however, it is easier to set $p_n=a_n+c_n$ (these are the numbers we're really interested in) and calculate $$p_{n+1}=a_{n+1}+c_{n+1}=2a_n+3c_n=2p_n + c_n = 2p_n + a_{n-1}+c_{n-1} = 2p_n+p_{n-1}$$ So a single second-degree recurrence for the result would be $$ p_n = 2p_{n-1} + p_{n-2} $$

This can be solved using standard techniques. The characteristic polynomial has roots $1\pm\sqrt 2$, and the exact solution turns out to be $$ p_n = \frac{(1+\sqrt2)^{n+1}+(1-\sqrt2)^{n+1}}2 = \left[\frac{(1+\sqrt2)^{n+1}}2\right] $$ where $[{\,\cdot\,}]$ rounds to the nearest integer.


Bonus question: Is there a straightforward combinatorial interpretation of the recurrence $p_n=2p_{n-1}+p_{n-2}$?

$\endgroup$
  • $\begingroup$ I understand the two recurrence equations. Is it possible to explain how to arrive at the matrix equation?. $\endgroup$ – Geoffrey Critzer Jun 9 '15 at 0:55
  • 1
    $\begingroup$ @GeoffreyCritzer: The two recurrence equations are the same as $$\begin{pmatrix}a_{n+1}\\c_{n+1}\end{pmatrix}=\begin{pmatrix} 1&2\\1&1\end{pmatrix}\begin{pmatrix}a_n\\c_n\end{pmatrix}$$ which you can just keep applying step for step until you reach $(a_1,c_1)$ which has the known values $(2,1)$. $\endgroup$ – hmakholm left over Monica Jun 9 '15 at 9:40
1
$\begingroup$

You only need to know the last digit of the string to decide what the possible next digits are. So there are three "states:" $0$, $1$ and $2$; if $x_n$, $y_n$ and $z_n$ are the numbers of strings of length $n$ ending in each one of these states, it's clear that $$\pmatrix{x_{n+1}\\y_{n+1}\\z_{n+1}}= \pmatrix{0&1&1\\1&0&1\\1&1&1}\pmatrix{x_{n}\\y_{n}\\z_{n}} $$ Let $A$ be this matrix; if you set $x_0=0$, $y_0=0$ and $z_0=1$ (so that all $1$-long strings are OK, you have $$\pmatrix{x_{n}\\y_{n}\\z_{n}}=A^n\pmatrix{0\\0\\1}.$$ The answer to your problem is $c_n=x_n+y_n+z_n$.

To compute this, note that the characteristic polynomial of $A$ is $z^3-z^2-3 z-1$, whose roots are $-1$ and $\sqrt2\pm1$. Thus $c_n$ satisfies the recurrence $c_n=c_{n-1}+3c_{n-2}+c_{n-3}$, and has the closed form $c_n=A(-1)^n + B(\sqrt2+1)^n+C(\sqrt2-1)^n$, where the constants $A$, $B$ and $C$ can be found by looking at $c_0=1$, $c_1=3$, and $c_2=7$; we find $A=0$, $B=(1+\sqrt2)/2$ and $C=(1-\sqrt2)/2$, so $$c_n=\frac12(1+\sqrt2)^{n+1}+\frac12(1-\sqrt2)^{n+1}.$$

$\endgroup$
0
$\begingroup$

Another approach is to use the symbolic method to establish a system of generating functions.

Let A(x) be the g.f. for the number of valid words that are empty or start with a 1 or start with a 2.

Let C(x) be the g.f for the number of valid nonempty words that start with a 2. We need to be familiar with the subtleties of the symbolic method.

The system: $A(x) = 1 + x + x A(x) + 2x C(x), C(x) = x A(x) + x C(x)$ gives

$A(x) = \frac{1 - x^2}{1 - 2x + x^2}$ and $C(x) = \frac{x + x^2}{1 - 2x + x^2}$.

We desire A(x) + C(x) and the sequence is given in Sloane's OEIS A078057.

$\endgroup$
  • $\begingroup$ How do you get $A(x)=1+x+xA(x)+2xA(x)$? $\endgroup$ – hmakholm left over Monica Jun 13 '15 at 14:44
  • $\begingroup$ I am sorry, the equation for A(x) had a typo which I have corrected now. A valid word that is empty or starts with a 0 or a 1 can be constructed by prepending a 0 or 1 to a valid word that starts with a 2 ( which accounts for the term 2*xC(x) ) OR prepending a 0 or a 1 to a word that starts with a 1 or 0 respectively ( this is the xA(x) term ). Now when we prepend to the empty word we really have two choices ( 0 or 1) so we have to add the term x. The term 1 is the empty word. $\endgroup$ – Geoffrey Critzer Jun 13 '15 at 18:29

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.