0
$\begingroup$

I am given such a problem: Find the number $a_n$ of n-element ternary sequences (composed only of 0s, 1s and 2s), where:

a) There are no repetitions of 1 (two 1s cannot stand next to each other)

b) There are no repetitions of 1 and no repetitions of 2 (two 1s cannot stand next to each other, same for 2s)

I've managed to solve part a and got the following formula: $$a_n = a_n = 2\cdot a_{n-1} + 2\cdot a_{n-2}$$

However, when I attempt to solve part b, I cannot find a way to do it properly. I solved part a by assuming a 1-element sequence, and if the only element is 0 or 2 i can join any proper sequence of length $n-1$, else if the only element is 1, i can join either 0 or 2, and then join any proper sequence of length $n - 2$. Thanks for any help.

$\endgroup$
2
$\begingroup$

I’ll take you through my attack on the problem. As I’ll point out in places, it isn’t the most efficient, but it does illustrate a reasonable approach.

Let $a_n$ be the number of good strings of length $n$, $b_n$ the number of those that end in $0$, $c_n$ the number of them that end in $1$, and $d_n$ the number of them that end in $2$. Clearly $$a_n=b_n+c_n+d_n\;.$$

Since a $0$ can be appended to any good string to get another good string, we must have $b_n=a_{n-1}$. A $1$ can be appended to a good string that ends in $0$ or $2$ to get a good string, so $c_n=b_{n-1}+d_{n-1}=a_{n-2}+d_{n-1}$. Similarly, $$d_n=b_{n-1}+c_{n-1}=a_{n-2}+c_{n-1}\;.$$ Note that $$c_n+d_n=2a_{n-2}+c_{n-1}+d_{n-1}\;;$$ this suggests that we should combine the strings ending in $1$ and $2$ by defining $e_n=c_n+d_n$ and observing that $e_n=2a_{n-2}+e_{n-1}$. We now have only two variables, $a_n$ and $e_n$, with recurrences

$$a_n=b_n+e_n=a_{n-1}+2a_{n-2}+e_{n-1}\tag{1}$$

and

$$e_n=2a_{n-2}+e_{n-1}\;.\tag{2}$$

Here’s where we’ll do something a little tricky. We can rewrite $(1)$ as

$$e_{n-1}=a_n-a_{n-1}-2a_{n-2}$$

and shift the index down $1$ to get

$$e_{n-2}=a_{n-1}-a_{n-2}-2a_{n-3}\;.\tag{3}$$

Shifting the index down in $(2)$ yields $e_{n-1}=2a_{n-3}+e_{n-2}$, which we can combine with $(3)$ to express $e_{n-1}$ entirely in terms of $a_k$s with $k<n$:

$$e_{n-1}=2a_{n-3}+a_{n-1}-a_{n-2}-2a_{n-3}=a_{n-1}-a_{n-2}\;.$$

At this point we might realize that we could have got this much more directly: $a_n=b_n+e_n$, and $b_n=a_{n-1}$, so of course $e_n=a_n-a_{n-1}$ and hence $e_{n-1}=a_{n-1}-a_{n-2}$. Oh, well!

Now we can substitute this back into $(1)$ to get a recurrence for $a$:

$$a_n=a_{n-1}+2a_{n-2}+a_{n-1}-a_{n-2}=2a_{n-1}+a_{n-2}\;.$$

And this is so simple that it’s worth considering how we might have arrived at it directly. If we have a good string of length $n-1$ that ends in $d$, we can always append one of the two ternary digits different from $d$; that automatically gives us $2a_{n-1}$ good strings of length $n$. If $d=0$, we can also append a $0$. And how many good strings of length $n-1$ end in $0$? One for every good string of length $n-2$, since we could have appended a $0$ to any of them! Had we reasoned that way to begin with, we’d have arrived at the recurrence

$$a_n=2a_{n-1}+a_{n-2}$$

almost immediately.

| cite | improve this answer | |
$\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.