About
Warm-ups
Problems
News
Problem 34
Posted 02/05/2017
Refresh the webpage if formulas are not shown correctly.
----------------------
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}$.
----------------------
Updated 02/10/2017 by Dun Qiu
We take such permutation as canonical cycle notation, then $a_{n}$ counts for number of permutations such that only the cycle with largest minimum number can be of size $1$, i.e. only number $n$ can be a fixed point.
Let $D(n)$ be the number of Derangement of set $[n]$, then
$a(n)=D(n)+D(n-1)$ is counted by A000255.
Back to top