Let $S = (\pi(1), \pi(2),\cdots,\pi(n))$ be a permutation of $\{1,2,\cdots,n\}$ such that $S$ does not contain the pattern $\pi(i)<\pi(j)<\pi(k)$ for any $i<j<k$.
For example, the permutation $(1,4,3,2,5)$ is not allowed since it contains $1,\cdots,2,5$ in that order.
How do we count the number of such permutations (of $n$ numbers)?
I know how to count permutations that forbid the pattern $\pi(k)<\pi(i)<\pi(j)$ for any $i<j<k$, namely they are counted by the Catalan Number $C_n$. But the $\pi(i)<\pi(j)<\pi(k)$ pattern doesn't seem to yield to such a method. Any help would be appreciated, Thanks!