Number of possible sequences 
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?
 A: Some extensive hints:


*

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

*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).
A: 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}$$
A: 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}$
