1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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$? $\endgroup$ Oct 8, 2018 at 12:32
  • $\begingroup$ yes, this is the question $\endgroup$
    – ekosman
    Oct 8, 2018 at 15:00

2 Answers 2

2
$\begingroup$

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}$$

$\endgroup$
1
$\begingroup$

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.

$\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.