Find the number of permutations of (1,2,3...n) possessing the following feature:

The number n is the only local maximum e.g. 123465, 123564, 654321,
as opposed to 651432, 261354.

Any permutation of 1..n has some number of local maxima of at least one.  Adding the (n+1) term anywhere in the list cannot reduce the number of maxima.

If there is one local maximum there are exactly two places that keep the number at one: directly before or directly after the previous maximum.

Therefore the number of permutations with a single local maximum doubles with each additional number.

When n=1, there is one local maximum (2^0)
So the formula is 2^(n-1)

Posted by Jer on 2015-10-02 07:28:14