Integers $1,2,...,n$ are placed in a way that each value is either bigger or smaller than all preceding values. In how many ways this can be done?

Question

Firstly I should mention an example of this patter which is also given in the book that is for $n=5$ $3,2,4,1,5$ is valid whereas $3,2,5,1,4$ is not.
I have calculated that for $n=3$, the number of ways is $1+2+1=4$, for $n=4$, the number of ways is $1+3+3+1=8$, for $n=5$, the number of ways is $1+4+6+4+1=16$.
But even I can't get the general implication. Can anybody suggest me a proper way out to solve it?
Thanks for answer in advance.

Answer 1

You can use induction. Let $A_n$ be the number of such choices for $1,\ldots, n$. The number that must go in the last place (the $n$-th place) is either $n$ or 1. Then after the number that goes in the $n$-th place is decided, the number of ways to arrange the remaining $n-1$ numbers in the first $n-1$ places $1,2,\ldots, n-1$ is $A_{n-1}$. Thus $A_n = 2A_{n-1}$.

Finish by noting $A_2 = 2$ to get $A_n=2^{n-1}$.

Answer 2

For a non-inductive approach, note that for whatever your starting number is, the numbers less than it must all occur in decreasing order, and similarly the numbers greater than it must occur in increasing order. This is because each next number must either be less than the minimum so far or greater than the maximum. For being greater than the maximum, if it is more than $1$ greater, then the value which is $1$ greater will then be between the later minimum and maximum values so it can't be used, and similarly for a number being more than $1$ less than the minimum.

After you choose the initial number and where the values below it occur, the values above it are fixed to occur in an increasing order in the remaining positions. Thus, you just need to do a Permutation count of the smaller values. For any given first number $i$, there are $i - 1$ smaller numbers to be put into $n - 1$ positions, for $n - 1 \choose i - 1$ permutations. In total then, there are $\sum_{i=0}^{n-1} {n-1 \choose i}$ such permutations. The sums you show for your examples of $n = 3, 4, 5$ are these permutation values.

By the Binomial theorem, $\left(1 + 1\right)^{n-1} = \sum_{i=0}^{n-1} {n - 1 \choose i}$, so the total number of ways is $\left(1 + 1\right)^{n-1} = 2^{n-1}$.

Answer 3

Just sharing my answer on this, which is quite similar to Mike's answer but easier to understand (in my perspective)

for a list consist of n numbers ($1, 2, 3,..., n$), it is intuitive to see the last number will either be the smallest in the list or the largest in the list. (either n or 1). While the second to last number may have two cases: $n-1$ or $1$ if the last number is $n$, $n$ or $2$ if the last number is $1$. Similarly for all the number from 2nd to last. As for the first number in the list, it will be whichever number left, there will be no choice.

As a result, for a list with n numbers, the possible ways will be $2^{n-1}$, coming from $2 * 2 * ... * 2$ for $n-1$ times