Can someone please proof how number of permutations of first N natural numbers with no three-term increasing subsequence can be given by the Nth catalan number .. ?
More formally number of permutations such that there doesn't exist any i<j<k for which a[i]<a[j]<a[k].