# Counting number of permutations of {1,2,…,n} such that there is no 123 sub sequence.

Suppose there is a set of {1,2,...,n} and we have to find the number of permutations of this set such that there is no increasing sub array of length 3. For example, if n=4, then 1,4,2,3 is not a permissible permutation as 1,2,3 is an increasing sub sequence. I know the answer is Catalan number but I am not being able to find any bijection with the common examples

• en.wikipedia.org/wiki/Catalan_number ... It is on their list of objects ... the bijection should be easy ? – Donald Splutterwit Mar 24 '17 at 14:32
• @ Donald, I thought the bijection would be easy but could not help myself, how would you approach this ? – Indranil Bhattacharya Mar 24 '17 at 14:34
• A bijection to stack-sortable is easy (multiply by the permutation $231$) ... stack-sortable , the push-pop sequence can be mapped to parenthesis ... What other objects do you want a bijection to ? – Donald Splutterwit Mar 24 '17 at 14:42