##### Wikipedia Description

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 nth Catalan number is given directly in terms of binomial coefficients byThe first Catalan numbers for n = 0, 1, 2, 3, areAn alternative expression for Cn iswhich is equivalent to the expression given above because. This shows that Cn 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 relationmoreover,This is because since choosing n numbers from a 2n 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