In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively -defined objects. They are named after the Belgian mathematician Eugne Charles Catalan (18141894). Using zero-based numbering, the n th Catalan number is given directly in terms of binomial coefficients by The first Catalan numbers for n = 0, 1, 2, 3, are An alternative expression for C n is which is equivalent to the expression given above because. This shows that C n is an integer, which is not immediately obvious from the first formula given. This expression forms the basis for a proof of the correctness of the formula . The Catalan numbers satisfy the recurrence relation moreover, This is because since choosing n numbers from a 2 n set of numbers can be uniquely divided into 2 parts: choosing i numbers out of the first n numbers and then choosing n - i numbers from the remaining n numbers. https://en.wikipedia.org/wiki/Catalan_number