C(0) = 1
C(1) = 1
C(n+1) = Sigma(r, 0, n, C(r) x C(n-r))

Where Sigma() means: Sigma(index var, lower bound, upper bound (inclusive), function(r)) I'm not familiar with standard Latex notation as I'm not a mathematician, so please ignore the sloppy presentation of the problem.


You want Catalan number

  • $\begingroup$ How can the terms of such series be obtained in general given only the recursive representation? The product within the sigma causes difficulties in evaluation of the problem. $\endgroup$ – Divye Nov 6 '09 at 12:57
  • $\begingroup$ I am not familiar with combinatorics at all, so perhaps others can give you a better answer. In my understanding, one common technique of finding the general term uses the generating function (the first proof in wiki). The product in this situation looks exactly like the coefficients of multiplication of two power series. This suggests that generating function could work. $\endgroup$ – Ho Chung Siu Nov 6 '09 at 13:13

In response to the comment to the other answer: the general technique is to write the recursion as a generating function identity. In this particular case, the identity is C(x) = 1 + x C(x)^2 and one can use the quadratic formula, then the generalized binomial theorem. More generally there are now powerful computer packages that can solve certain general classes of recursions and spit back hypergeometric series; the canonical reference here is Petovsek, Wilf, and Zeilberger. If you don't know much about generating functions, you might want to check out Wilf's "generatingfunctionology" first.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.