3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ en.wikipedia.org/wiki/Catalan_number ... It is on their list of objects ... the bijection should be easy ? $\endgroup$ – Donald Splutterwit Mar 24 '17 at 14:32
  • $\begingroup$ @ Donald, I thought the bijection would be easy but could not help myself, how would you approach this ? $\endgroup$ – Indranil Bhattacharya Mar 24 '17 at 14:34
  • $\begingroup$ 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 ? $\endgroup$ – Donald Splutterwit Mar 24 '17 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.