# Number of ternary sequences of length $n$ with the property that $|x_i - x_{i - 1}| = 1$ for each $i$ such that $2 \leq i \leq n$

Question:

Find the number of ternary sequences (each element of the sequence is $$0$$, $$1$$, or $$2$$) of length $$n$$ such that $$|x_i - x_{i - 1}| = 1$$ for each $$i$$ such that $$2 \leq i \leq n$$.

My suggestion:

Firstly notice that every second element must be the digit "1".

Lets separate the problem into $$2$$ classes:

The sequence starts with 1 - The are exactly $$\lfloor n/2 \rfloor$$ elements that are not "1". For each element we have $$2$$ possibilities - it's $$\lfloor n/2\rfloor^n$$

The sequence starts with either 0 or 2 - The are exactly $$\lceil n/2 \rceil$$ elements that are not "1". For each element we have 2 possibilities - it's $$\lceil n/2 \rceil^n$$

Sum it up and get:

$$2\cdot\lceil n/2 \rceil^n+\lfloor n/2 \rfloor^n$$

Is it correct?

• Are you saying that we are counting $n$-tuples $(x_1, x_2, x_3, \ldots, x_n)$ with each $x_i \in \{0, 1, 2\}$ such that $|x_{i} - x_{i - 1}| = 1$ for $i = 2, 3, \ldots, n$? Oct 8, 2018 at 12:32
• yes, this is the question Oct 8, 2018 at 15:00

Most of your reasoning is correct, but the final result is not.

As you observed, every other element of a ternary sequence of length $$n$$ with the property that $$|x_i - x_{i - 1}| = 1$$ for $$i = 2, 3, \ldots, n$$ is a $$1$$.

Case 1: The sequence begins with $$1$$.

As you observed, exactly $$\lfloor \frac{n}{2} \rfloor$$ elements of the sequence are not equal to $$1$$. Each such entry can be filled in two ways, with either a $$0$$ or $$2$$. Hence, there are $$2^{\lfloor \frac{n}{2} \rfloor}$$ such sequences.

Case 2: The sequence begins with $$0$$ or $$2$$.

As you observed, exactly $$\lceil \frac{n}{2} \rceil$$ elements of the sequence do not have a $$1$$ in that position. Each such entry can be filled in two ways, with either a $$0$$ or $$2$$. Hence, there are $$2^{\lceil \frac{n}{2} \rceil}$$ such sequences.

Total: Since the two cases are mutually exclusive and exhaustive, the number of admissible sequences is $$2^{\lfloor \frac{n}{2} \rfloor} + 2^{\lceil \frac{n}{2} \rceil}$$

Let $$a_n,b_n,c_n$$ be the number of $$n$$ lenght sequences which start respectively with 0,1,2.

Then we are interested in $$d_n = a_n+b_n+c_n$$ and we have $$a_n = b_{n-1}$$ , $$b_n = a_{n-1}+c_{n-1}$$ and $$c_n = b_{n-1}$$. Now solve those recurences and youll get an answer.