About Catalan Numbers
There are two common recursive formulas to find Catalan number
C(n) = sum(C(k), k= 1..n-1)
n*C(n) = (4*n-6)*C(n-1)
The first one yield a quadratic equation in terms of generating function f(x) and the second one leads to a simple first order differential equation which can be solved to obtain the same quadratic equation in terms of the same generating function f(x). Where f(x) = c(0)+c(1)x+c(2)x^2+c(3)x^3+.. = sum(c(n)*x^n,n=0..infinity).
First few Catalan numbers are 1,1,2,5,14,42,132,..
Catalan numbers occur in many disguises in Mathematics. One of the standard way to define them as C(n) by thinking of them as the different way to parenthesize the multiplicative expression, then number of rectangular paths in a lattice gives C(n+1) and the number of ways to divide a polygon to give triangles using non intersecting diagonals C(n-1)
C(n) = sum(C(k), k= 1..n-1)
n*C(n) = (4*n-6)*C(n-1)
The first one yield a quadratic equation in terms of generating function f(x) and the second one leads to a simple first order differential equation which can be solved to obtain the same quadratic equation in terms of the same generating function f(x). Where f(x) = c(0)+c(1)x+c(2)x^2+c(3)x^3+.. = sum(c(n)*x^n,n=0..infinity).
First few Catalan numbers are 1,1,2,5,14,42,132,..
Catalan numbers occur in many disguises in Mathematics. One of the standard way to define them as C(n) by thinking of them as the different way to parenthesize the multiplicative expression, then number of rectangular paths in a lattice gives C(n+1) and the number of ways to divide a polygon to give triangles using non intersecting diagonals C(n-1)
posted by Sumant at 5:51 PM
0 Comments:
Post a Comment
<< Home