Yellow.Flash's blog

number of permutations with no three-term increasing subsequence.
By Yellow.Flash, history, 8 years ago, In English

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].

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Catalan Number is the number of different ways a convex polygon with n + 2 sides can be cut into triangles by connecting vertices with straight lines (a form of Polygon triangulation).Try to find similarity between your problem and this problem. I do not have any formal proof as of now. Hope it helps.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://math.stackexchange.com/questions/155867/penguin-brainteaser-321-avoiding-permutations

check this

→ Reply