All permutations of $1,2,...,n$ such that each element is larger than all previous elements or smaller than all previous elements

Question

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.

Answer 1

Note that the first two elements in the sequence must be adjacent to each other, but their order is irrelevant. So given a GOOD sequence $a_1,\ldots,a_n$ of length $n$, we can generate two GOOD sequences of length $n+1$:

$$a_1,a_1+1,b_2,\ldots,b_n$$ and $$a_1+1,a_1,b_2,\ldots,b_n$$

where $b_i=a_i$ if $a_i<a_1$, and $b_i=a_i+1$ if $a_i>a_1$. For instance, the sequence $23145$ generates $234156$ and $324156$. So we see that there are twice as many GOOD sequences of length $n+1$.

Answer 2

What I think the hint is trying to say:

Suppose that our current string is $a_1a_2a_3\cdots a_k$. Then either $a_{k+1}$ must be $\max\{a_1, \ldots, a_k\}+1$ or $\min\{a_1, \ldots, a_k\}-1$. If any other choice is made, then either $\max\{a_1, \ldots, a_k\}+1$ or $\min\{a_1, \ldots, a_k\}-1$ will not be legally allowed to be placed. Of course one needs to be careful with when either of these values doesn't exist (i.e. when either $1$ or $n$ has already been used). It's not clear to me how to fill in this gap.

---

Here's probably the simplest inductive argument.

Base cases up to $n=2$ are easy.

Suppose that the proposition is true for the case $n-1$.

First, notice that we have only two choice for $a_n$, as it must always be either $1$ or $n$. If not, then both $1$ and $n$ appear before $a_n$ (because $n \geq 3$) which means it can't be good.

If $a_n = 1$, then $a_1-1, \cdots a_{n-1}-1$ is a good sequence of length $n-1$, so there are $2^{n-2}$ choices for the other elements.

If $a_n = n$, then $a_1, \cdots a_{n-1}$ is a good sequence of length $n-1$, so there are $2^{n-2}$ choices.

In total then, there are $2^{n-2} + 2^{n-2} = 2^{n-1}$ choices.

Answer 3

We can prove it by strong induction. A GOOD sequence of length $n$ with $n$ in position $k$ consists of a GOOD sequence of the numbers from $n-k+1$ to $n-1$, followed by $n$, followed by the numbers from $1$ to $n-k$ in descending order. There is one sequence that starts with $n$ and has all the numbers in descending order.

The base case is $n=1$, where there is $2^{1-1}=1$ GOOD sequence. Assume we have shown there are $2^{n-1}$ GOOD sequences for $n$ up to $m$. Then for $m+1$ we have one sequence that starts with $m+1$ and $2^{k-2}$ for each position $k$ from $2$ through $m+1$ and $$1+\sum_{i=2}^{m+1}2^{i-2}=2^m$$

Answer 4

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