Number of possible sequences

Question

Let $(a_1,...,a_{10})$ be a sequence with $a_i \in \{1,...,10\}$ and the following properties:

$i)$ $a_1\in\{1,...,10\}$

$ii)$ $a_i\neq a_j \ \forall i,j\in \{1,...,10\}$ with $i\neq j$

$iii)$ $a_i\in \{a_1\pm 1,...,a_{i-1}\pm1\}\cap\{1,...,10\} \quad \forall i\in \{2,...,10\}$

How many sequences with these properties exist? Is it possible to generalize this for any $n$ instead of $10$?

I tried looking at the different cases for starting values: For $a_1=\{1,10\}$ there is only one possible sequence each. For $a_1=\{2,9\}$ there are 9 possible seuqences each, because you have 9 possibilities for $1$ or $10$ and the rest of the sequences is clear. But for $a_i=\{3,4,5,6,7\}$ I don't know how to go one with that way of thinking. Can someone give me a hint?

Answer 1

Some extensive hints:

1. By induction we have $$A_i := \{ a_1, \dotsc, a_i \} = \{ \min A_i, \min A_i + 1, \dotsc, \max A_i \}.$$ Thus, $a_{i+1} = \min A_i - 1$ or $\max A_i + 1$.

2. You can and must go down exactly $k:=a_1 - 1$ times. Thus, we want to know at which $k$ indices we go down. So basically we count the subsets of $\{1, \dotsc, 9\}$ with $k$ elements (which is well-known).

Answer 2

Let $N(k)$ be the numbers of ways to end up with a $\{a_1,...., a_k\} = \{1,2,...k\}$.

Now if you have $\{a_1,...., a_k\} = \{1,2,...k\}$ then $a_k = 1$ or $a_k = k$ (but $a_1$ may be anything). After all, you can't have group of $a_i < m$ and a group of $a_j > m$ without some $a_l = m$.

Now the numbers of ways $\{a_1,....., a_k\} = \{1,2,...k\}$ and $a_k = k$ are the number of ways $\{a_1,..., a_{k-1}\} = \{1,....,k-1\}$ and there are $N(k-1)$ ways to do that

And the numbers of ways $\{a_1,....., a_k\} = \{1,2,...k\}$ and $a_k = 1$ are the number of ways $\{a_1,..., a_{k-1}\} = \{2,....,k\}$. And there are as many ways to do that as there are ways to do $b_i = a_i -1$ so $\{b_1,....,a_{k-1}\} = \{1,....,k-1\}$. And there are $N(k-1)$ to do that.

So $N(k) = 2N(k-1)$ and as $N(1) = 1$ (as $\{a_1\} = \{1\} \iff a_1 =1$) inductively $N(k) = 2^{k-1}$

Answer 3

For the set $\{1,2,\ldots,n\}$, let $N_k(n)$ be the number of allowable sequences $(a_1,a_2,\ldots,a_n)$ such that $a_k=n$. It is easy to see that

$$\begin{align} N_1(n+1)&=N_1(n)\\ N_2(n+1)&=N_1(n)\\ N_3(n+1)&=N_1(n)+N_2(n)\\ N_4(n+1)&=N_1(n)+N_2(n)+N_3(n)\\ &\,\,\vdots\\ N_{n+1}(n+1)&=N_1(n)+N_2(n)+\cdots+N_n(n) \end{align}$$

It follows by induction that, for $n\ge2$,

$$\begin{align} N_1(n)=N_2(n)&=1\\ N_3(n)=1+1&=2\\ N_4(n)=1+1+2&=4\\ &\,\,\vdots\\ N_n(n)=1+1+2+4+\cdots+2^{n-3}&=2^{n-2} \end{align}$$

and thus the total number of allowable sequences is

$$N_1(n)+N_2(n)+\cdots+N_n(n)=1+1+2+4+\cdots+2^{n-2}=2^{n-1}$$