2

So I need to find a correct recurrence relation to this problem:

How many series of size n over {0,1,2} exist, so that each digit never appears alone. For example, this series is good: 000110022, and this series is bad: 000122.

I did find a correct relation: $f(n) = f(n-1) + 2*f(n-2)$ or $f(n) = 3*f(n-2) + 2*f(n-3)$ (both work. But I have no idea how to explain them. I found them just by brute force.

I would think that $f(n) = 3*f(n-2) + 3*f(n-3)$ minus the intersection between the two, but again it seems as though that intersection is $f(n-3)$ (according to the above relation), and I have no idea why.

Any help would be appreciated. Thanks!

P.S. $f(1) = 0, f(2)=3, f(3)=3, f(4)=9, f(5)=15$

Cauthon
  • 389
  • 3
  • 16

2 Answers2

1

For simplification, consider only the number $F_n$ of legal strings that end with a fixed symbol $l\in\{0,1,2\}$ (your original series is then just $f_n=3F_n$).

For example for $n=5$ you count strings of the form

$$???ll,\quad ??lll,\quad ?llll,\quad lllll$$

Where the last $?$ is always $\neq l$.

This can be written as $$F_n = K_{n-2} + K_{n-3} + ... + K_1 + 1.$$

where $K_n$ counts the legal length-$n$ strings, that do not end with $l$, i.e. those $????$-strings from above. As they can only end with two other symbols, we have

$$K_n=2F_n$$ and we find

$$F_n=2F_{n-2} + 2F_{n-3} +...+2F_1+1$$

Now with this formula you find that

$$F_{n}=2F_{n-2}+F_{n-1}.$$

As we mentioned before, $f_n=3F_n$, hence the same recursion holds for $f_n$.

flonk
  • 2,434
1

Call the number of sequences of length $n$ as described $a_n$. We know $a_2 = 3$ and $a_3 = 3$ (they must be formed by one symbol type only).

A sequence of length $n$ is made of a sequence of length $n - 1$ by adding another symbol as the last one (1 way), or out of one of length $n - 2$ by adding two symbols different from the last one (2 ways): $$ a_n = a_{n - 1} + 2 a_{n - 2} \qquad a_2 = a_3 = 3 $$

vonbrand
  • 27,812
  • There's one thing I don't understand - let's say I'm building a sequence of length 12. I can either add 1 symbol to the end of a sequence of length 11, or add 2 symbols to a sequence of length 10. But these two last symbols can be any of the three 0,1,2 - which gives me 3 options, not 2. – Cauthon Apr 26 '14 at 15:27
  • 1
    @user2996797, consider the last three symbols; the case where the last three are the same was already counted with the other case. – vonbrand Apr 26 '14 at 16:29
  • Got it, thanks so much! – Cauthon Apr 26 '14 at 16:32