Number of permutations of $\{1,2,\dots,n\}$ so that there are no $iWhat is the number of permutations $\pi$ of $\{1,\ldots,n\}$ so that there is no triple $i<j<k$ with $\pi(j)<\pi(i)<\pi(k)$?
My understanding:
We have triple $i\ge j\ge k$ such that $\pi(j)\ge\pi(i)\ge\pi(k)$. Then, the number of such permutations is equivalent to the number of monotone mappings. 
$$
\varphi: \{1,2,\ldots,n\}\rightarrow \{1,2,\ldots,n\},~1 \le\varphi(i)\le i.
$$
But I don't know how it leads to $\frac{1}{n+1}{2n\choose n}$. 
 A: Let $C_n$ be the number of such permutations. Consider the location of $1$ in the permutation, let is say it is at spot $j$. Then for every $i<j$ and every $k>j$, we must have $\pi(i)>\pi(k)$, otherwise we would have the illegal condition $\pi(j)<\pi(i)<\pi(k)$. This means that 


*

*$\pi(j+1),\pi(j+2),\dots,\pi(n)$ is some rearrangement of the numbers $2,3,\dots,n-j+1$, while 

*$\pi(1),\pi(2),\dots,\pi(j-1)$ is a rearrangment of the numbers $n-j+2,n-j+3,\dots,n$.
because all the numbers in the first list must be smaller than the ones in the second. 
How many ways are there to choose the rearrangement in $(1.)$? This is the same as choosing an arrangement of $1,2,\dots,n-j$ which has no $i<j<k$ for which $\pi(j)<\pi(i)<\pi(k)$, a smaller version of the whole problem. The number of ways to do this is $C_{n-j}$. Similarly, the number of ways to do $(2.)$ is $C_{j-1}$. Summing over all possible $j$, we conclude
$$
C_n=\sum_{j=1}^n C_{j-1}C_{n-j}
$$
This is the Catalan number recurrence, and it is well known that this implies $C_n=\frac1{n+1}\binom{2n}n$.
