We have a sequence $a_1,a_2,…,a_n$ and $\forall i\in N;~~~ a_i\in\{1,2,3,…,n\}$. A sequence is $GOOD$ if we have that: For Every $k \in N$, we have $a_k≥a_i$ for every $i<k$, or $a_k≤a_i$ for every $i<k$. it means that every element is larger than all previous elements or smaller than all previous elements.
We want to find how many permutations of $1,2,3,…n$ are $GOOD$ ?
It was a question in an old exam and the answer was $2^{n-1}$ it said that in every choice, we can put the biggest or the smallest element from the remaining numbers, except that for the last one we have one choice so the answer is $2^{n-1}$. I don't completely understand this answer. (eg. if we follow this algorithm it could easily get to the point where we can't choose any other number: $1\to 1, \ n \to ?$ Can anyone explain this answer or give another answer for this question? Is this answer correct?
PS. Changed the condition so it is better understandable.
Best Answer
Think about choosing the permutation in reverse order $a_n,a_{n-1},\dots,a_1$. Each element must be highest or smallest of the elements not previously chosen, so there are two choices for each (except for $a_1$, where the highest and lowest are the same).
For example, the last element is always $1$ or $n$. If the last element is $1$, then the second to last is either $2$ or $n$. And so on $\dots$.