wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Another derivation of Catalan numbers
        
(Message started by: Aryabhatta on May 31^st, 2007, 4:48pm)

Title: Another derivation of Catalan numbers
Post by Aryabhatta on May 31^st, 2007, 4:48pm

Let n be a positive integer and consider the 2n+1 tuple (a₀, a₁, ..., a_2n) satisfying

i) a₀ = 0
ii) |a_k - a_k+1| = 1 for 0 <= k < 2n
ii) a_i >= 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 n^th Catalan number is C(2n,n)/(n+1)

n^th Catalan number = number of different ways a n+2 sided convex polygon can be cut into n triangles by connecting vertices with straight lines.