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