0
$\begingroup$

I know this problem is familiar to "the number of binary strings of length $n$ with no consecutive zeros" but still it is a way different problem. But in that question the alphabet is set to $\{0,1\}$ and here:

Q:

Let $A=\{0,1,2\}$ be an alphabet, what is the the number of possible strings of length $n$ with no consecutive zeros in it?

$\endgroup$
1
$\begingroup$

This is a general way that you can apply to this kind of problems (I'll call the strings with no consecutive $0$'s, good strings.):

Let's denote the number of good strings of length $n$ with $a_n$, and let's define $b_n$ and $c_n$ to be the number of good strings starting with $0$ and starting with something other than $0$, respectively. So $a_n=b_n+c_n$.

Now, if a good string of length $n+1$ starts with $0$, then the string obtained by omiting the $0$, must start with something other than $0$, since no two consecutive $0$'s are allowed. Conversly, if you add a $0$ to the beginning of a good string of length $n$, starting with $1$ or $2$, then you get a good string of length $n+1$. So we have $b_{n+1}=c_n$.

Also, if a good string of length $n+1$ start with $1$ or $2$, by dropping the first element, we get a good string of length $n$. Conversly, adding $1$ or $2$ to the beginning of an arbitary good string of length $n$, results in a good string of length $n+1$. So we have $c_{n+1}=2a_n=2b_n+2c_n$.

Now combining the derived equations, we get (Note that we have those equations for any natural number $n$, so we can change the indices to any natural number we want.): $$b_{n+2}=2b_{n+1}+2b_n$$ $$c_{n+2}=2c_{n+1}+2c_n$$ Summing up: $$a_{n+2}=2a_{n+1}+2a_n$$ Now, you can use this recurrence relation for $a_n$.

It's easy to see that similar to this way, you can solve the problems in which you want to find the number of strings in any finite language, that contain no instances of some finite patterns (like $102$, $11$ or so). Just define $b_n$, $c_n$, $\dots$ in a way that fits your problem, find the relations between them and combine them to find a recurrence relation for $a_n$.

$\endgroup$
  • $\begingroup$ Ok but, a0=0 (number of good words of length zero), a1=3 and a2=3^2-1=8 and an=2a(n-1)+2a(n-2) doesn't work for a2. Am I counting right? $\endgroup$ – Alfredo Lozano Dec 4 '15 at 16:05
  • $\begingroup$ No. $a_0=1$ since we have one sequence of length zero which is the empty sequence. But if it's not comfortable for you to accept this, you can start from $n=1$ and check the formula. $\endgroup$ – Mohsen Shahriari Dec 4 '15 at 17:05
3
$\begingroup$

A different approach, while not generic as @Mohsen Shahriari 's.

Lets break up by the number of zero's contained in the sequence of length $n$. Suppose there are $k$ (max of $\frac{n}{2}$ when $n$ is even, $\frac{n + 1}{2}$ when $n$ is odd) zeroes. Using balls and sticks argument: We need to have some element between two $0$'s. There are $k-1$ gaps. After filling those gaps, we are left with $n - k - (k-1)$ of $1$'s and $2$'s to be filled in $k+1$ available places. This can be done in $\binom{n-2k+1 + k}{k}$ ways and $2^{n-k}$ ways to assign $1$'s and $2$'s.

Summing up, $$\sum_{k = 0}^{v}\binom{n-k+1}{k} \cdot 2^{n-k}$$ where $v=\frac{n}{2}$ (when $n$ is even) and $v=\frac{n + 1}{2}$ (when $n$ is odd)

$\endgroup$
  • $\begingroup$ Thank you very much! this is a very interesting approach this is actually closer to where my efforts were going, I don't have enough rep for voting up but I'll vote when I get some more. $\endgroup$ – Alfredo Lozano Dec 4 '15 at 14:17
  • $\begingroup$ The number of ways in which $n-k-(k-1)$ balls to filled in $k+1$ buckets should be $\binom{n-2k+1+k}{k}=\binom{n-k+1}{k}$ $\endgroup$ – Deepak Gupta Dec 18 '15 at 19:44
  • $\begingroup$ @DeepakGupta You are right, I got the sign of $k$ wrong. Please see the edit. $\endgroup$ – talegari Dec 20 '15 at 10:11

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.