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

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, or $$a_k≤a_i$$ for every $$i. 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.

• sorry, why isn't the answer just $2$?
– lulu
Feb 25 '19 at 21:33
• @lulu I am wondering about the same thing, definitely missing something Feb 25 '19 at 21:34
• I think the question is written incorrectly. It should be "for every $k \in N$, we have $a_k \geq a_i$ for all $i < k$ or $a_k \leq a_i$ for all $i < k$". So an example of a good sequence is $3456721$ Feb 25 '19 at 21:35
• @Vinyl_coat_jawa My only guess is that the OP doesn't know what "permutation" means. Maybe strings like $1,1,1,1\cdots,1$ are allowed.
– lulu
Feb 25 '19 at 21:35
• Your edit has clarified things slightly. But when you say $a_k\ge a_i$ or $a_k\le a_i$ for every $i<k$, you are making two mistakes: first, it should be $>$ and $<$ instead of $\ge$ and $\le$; and secondly, it should be "$a_k > a_i$ for every $i<k$, or $a_k < a_i$ for every $i<k$". Feb 25 '19 at 21:42

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

• Yes. And this explains the OP's question: the answer in the third paragraph makes perfect sense if we choose the elements backwards. Feb 26 '19 at 2:56

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

• If I don't get any complete non-inductive answers till tomorrow, I will select this answer as the best because the complete solution of this answer is submitted earlier than the other(s). Thank you very much. Feb 25 '19 at 22:25

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.

• But $a_1$ can be any number, so there are $n$ choices for it. I haven't figured out how to do the counting to justify $2^{n-1}$. I am thinking induction, starting with the GOOD sequences of $n$ and adding in $n+1$. If you start with $n+1$ you have to use the descending sequence. Otherwise $n+1$ can go anywhere after $n$ so we want to show there are $2^{n-1}-1$ choices for that. Feb 25 '19 at 21:58
• I think the hint in the question is nonsense, and your approach is doomed to failure. Feb 25 '19 at 22:01
• @RossMillikan I understand most part of Dan Rust proof except that like you, I can't figure the $a_1$ because it has n choices (or at least n-2 if we don't count 1 and n). I think induction can be a good approach. Feb 25 '19 at 22:04
• "There is exactly one sequence...": no there isn't. Any sequence ending in $n$ will do, and there are $2^{n-2}$ of those. Feb 25 '19 at 22:16
• @TonyK thanks, fixed. Feb 25 '19 at 22:25

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