Number of sequences of $0$s, $1$s, and $2$s with length $n$ such that there is a $0$ somewhere between every pair of $2$s

Question

Let $a(n)$ be the number of sequences with length $n$ which consists the digits $0,1,2$ such that between every two occurrences of $2$ there is an occurrence of $0$ (not necessarily next to the $2$'s). An example for good sequence is $0102102$. An example for bad sequence is $01212$.

A. Find a recursion formula for $a(n)$

B. Find an explicit expression for $a(n)$.

My try: let $x(n)$ be the number of sequences with length $n$ that if we add $2$ at the end of sequence it is still a good sequence with length $n+1$.

Now, if the last digit in the sequence was $0$, then we have to look on the number of good sequences with length $n-1$, hence $\displaystyle a(n-1)$.

If the last digit was $1$, then we now need to look on $x(n-1)$ and work with the same manipulation. This way we get the recursion $x(n)=a(n-1)+x(n-1)$. By induction I can get a recursion formula for $x(n)$, but I don't know how to find a formula for $a(n)$ or find an explicit expression for $a(n)$.

Any help will be appreciated, thank you!

Answer 1

$x(n) = x(n-1) + x(n-1) + \sum_{i=1}^{n-1}x(n-1 -i) + x(0), n\ge 2 $
$x(0)=1$ $, x(1)=3$.

Any valid string either start with $0$ (number of such strings are $x(n-1)$) or $1$ (number of such strings are $x(n-1))$ or $2$.If it starts with $2$ then it must have only $1's$ before first occurrence of $0$. Condition on the position of first $0$ after the $2$. It can be next to it, or one $1$ followed by $0$ an so on and the case that occurrence of $2$ is followed by only $1's$ (number of such strings are $x(0))$.

Edit

More Simpler Recurrence

Using the recurrence above subtract $x(n-1)$ from $x(n)$ to get this simpler recurrence, $$x(n)= 3x(n-1)-x(n-2), n \ge 2 $$

You can use this formula to compute the closed formula easily.

Answer 2

Hi Galc127, there are 3 disjoint cases that you must want to take into account.$$B_n=\{x\in \{0,1,2\}^n: x = r21^k ,r\in A_{n-k-1}\},$$is the set of good words that ends up with a $2$. $$C_n=\{x\in \{0,1,2\}^n: x = r2p0q ,r\in A_{n-k-2}\wedge pq\in \{0,1\}^k\},$$ Is the set of good words that ends up with $2$ and $0$.
$$D_n=\{0,1\}^n,$$is the set that does not have any $2$'s.
Therefore, $A_n=B_n\cup C_n\cup D_n$, and call $a_n=|A_n|,b_n=|B_n|,c_n=|C_n|,d_n=|D_n|$. The sets are disjoint so $a_n=b_n+c_n+d_n$ and $d_n=2^n$.
Now, $$b_n=d_{n-1}+c_{n-1}+b_{n-1}=2^{n-1}+c_{n-1}+b_{n-1},$$$$c_n=2*c_{n-1}+b_{n-1}$$ Do you see why?(try by appending proper characters at the end of strings in each set)

The thing with your try is that you are not using $B_n$ anywhere, your $x_n$ is like $d_n+c_n$.
Hope it helps.
Edit: As a comment, the generating function would be $$\frac{1}{1-2x}+\frac{x^2}{1-5x+7x^2-2x^3}+\frac{x}{1-3x+x^2}.$$

Answer 3

Consider the following: \begin{align*} r(n) &:= \text{number of sequences of 0s and 1s} = 2^n \\ s(n) &:= \text{number of sequences of 0s and 1s with at least one $0$} = 2^n - 1 \\ \end{align*} The corresponding (ordinary) generating functions are \begin{align*} R(x) &= \sum_{n \ge 0} 2^n x^n = \frac{1}{1 - 2x} \\ S(x) &= \sum_{n \ge 0} (2^n - 1) x^n = \frac{1}{1 - 2x} - \frac{1}{1 - x} = \frac{x}{(1-2x)(1-x)}. \end{align*} The generating function $A(x)$ of $a(n)$ satisfies, by casework on the number $k$ of $2$s in the sequence: \begin{align*} A(x) &= \underbrace{R(x)}_{k=0} + \underbrace{R(x) x R(x)}_{k=1} + \sum_{k \ge 2} R(x) (x S(x))^{k-1} x R(x) \\ &= R(x) + \sum_{k \ge 1} R(x)^2 S(x)^{k-1} x^{k} \\ &= R(x) + \frac{x R(x)^2}{1 - x S(x)} \\ &= \frac{1}{1 - 2x} + \frac{x / (1 - 2x)^2}{1 - \frac{x^2}{(1-x)(1-2x)}} \\ &= \frac{1}{1 - 2x} + \frac{x(1-x)}{(1-2x) \left[ (1-2x)(1-x) - x^2 \right]} \\ &= \frac{1 - 3x + x^2}{(1 - 2x)(1 - 3x + x^2)} + \frac{x - x^2}{(1-2x)(1 - 3x + x^2)} \\ &= \frac{1 - 2x}{(1 - 2x)(1 - 3x + x^2)} \\ &= \boxed{\frac{1}{1 - 3x + x^2}}. \end{align*}

---

Now that we have the generating function, we realize that $a(n)$ satisfies a much simpler recurrence: $$ a(n) = 3 a(n-1) - a(n-2) $$ which follows directly from $A(x) (1 - 3x + x^2) = 1$. This recurrence can be explained combinatorially as well, and if we had bothered to be a bit more clever we might have found the recurrence in the first place and saved some algebra.

Conclude either from the recurrence or from searching the first few values in oeis that in fact $$ a(n) = f(2n+2) $$ where $f(k)$ is the $k$th Fibonacci number.

Answer 4

Let $a(n)$ be the number of acceptable strings of length $n$ that have a $2$ after the last $0$. Let $b(n)$ be the number of acceptable strings of length $n$ that do not have a $2$ after the last zero. You have a pair of recurrences $a(n)=a(n-1)+b(n-1)$ because to get one you can append a $1$ to an $a$ or a $2$ to a $b$. $b(n)=2b(n-1)+a(n-1)$ because you can append either a $0$ or $1$ to a $b$ or append a $0$ to an $a$. Starting conditions are $a(1)=1, b(1)=2$ It turns out the $a$'s and $b$'s are alternate Fibonacci numbers.

Answer 5

Let $w$ be an arbitrary good word of length $n$. To extend $w$ to a good word of length $n+1$,

we have 3 choices for the last digit. The resulting word will always be good if the last digit is 0 or 1,

so we need to subtract the number of bad words that result when we append a 2:

Let T be the set of bad words of length $n+1$ which become good when the last digit (2) is deleted, and

let S be the set of good words of length $n-1$;

we will show below that T and S have the same number of elements, so then

$\hspace{.5 in}\color {red}{a(n+1)=3a(n)-a(n-1)}$.

---

$\textbf{1)} $Define $f:T\rightarrow S$ by deleting the last two digits.

$\textbf{2)} $Define $g:S\rightarrow T$ as follows:

$\;\;\;\textbf{a)}$ If $v$ ends in 0, let $g(v)=v22$.

$\;\;\;\textbf{b)}$ If $v$ ends in 2, let $g(v)=v12$.

$\;\;\;\textbf{a)}$ If $v$ ends in 1, let $g(v)=\begin{cases}v22, &\mbox{if v has a 0 after the last 2 (if any)}\\ v12, &\mbox{if v does not have a 0 after the last 2} \end{cases}$

Since $f$ and $g$ are clearly inverses, S and T have the same number of elements.