Author |
Topic: Another derivation of Catalan numbers (Read 639 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
Another derivation of Catalan numbers
« on: May 31st, 2007, 4:48pm » |
 Quote  Modify
|
Let n be a positive integer and consider the 2n+1 tuple (a0, a1, ..., a2n) satisfying
i) a0 = 0
ii) |ak - ak+1| = 1 for 0 <= k < 2n
ii) ai >= 0 for 0 <= i <= 2n
Show that the number of tuples satisfying the above 3 conditions is C(2n,n) (2n choose n)
Using this, show that the nth Catalan number is C(2n,n)/(n+1)
nth Catalan number = number of different ways a n+2 sided convex polygon can be cut into n triangles by connecting vertices with straight lines.
|
|
 IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print