Posted 02/05/2017

----------------------
Previous    Next
----------------------

This problem is proposed by Ran Pan. If you want to submit your problem, please click here.

----------------------

In this problem, we are interested in enumerating permutations in $\mathcal{S}_n$ that do not have contiguous left to right maxima.

For a permutation $\pi=\pi_1\pi_2\cdots\pi_n\in\mathcal S_n$, $\pi_i$ is a left to right maximum of $\pi$ if and only if $\pi_i=\textrm{max}\{\pi_1,\pi_2,\cdots,\pi_{i}\}$. For example, if we take $\pi=3145276$, then the set of left to right maxima of $\pi$ is $\{3,4,5,7\}$.

We say permutation $\pi$ has contiguous left to right maxima if $\exists\ i$ such that both $\pi_i$ and $\pi_{i+1}$ are left to right maxima of $\pi$. For example, $\pi=3146275$ has contiguous left to right maxima since both $\pi_3=4$ and $\pi_4=6$ are left to right maxima and they are contiguous, while $\tau=3164275$ does not have contiguous left to right maxima.


Suppose we let $a_{n}$ denote the number of permutations in $\mathcal{S}_n$ that do not have contiguous left to right maxima.

Find $a_{n}$.