Interesting sequence catalan

[This was found in my stack of loose notes from May 2013]

Consider the following problems

  • Number of plane binary trees with n end points
  • Number valid k-ary parenthesis for a string of n characters?
  • Sequence of X and Y such that no initial segment of the sequence has more X than Y.
  • Number of path P in the (x,y) plane from (0,0) to (n-1,0) using steps (1,k), where k+1 in S or k = -1, with a total of m-1 steps of the form (1,-1) such that P never passes below the x-axis.
  • Number of dissections of a convex (m+1)-gon C into n-m regions, each a k-gon, by drawing diagonals that don’t intersect in their interiors

All these problems can be solved by the sequence known as the Catalan number. The first few numbers in the sequence are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862

It can be computed using this formula:

equation

 

Or by the recurrence relationpasted_image001

 

 

 

Advertisements

Published by

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s