The nth Catalan number is the number of Dyck words (balanced strings of parenthesis or brackets such as [[][]]; formally defined as a string using two characters a and b such that any substring starting from the beginning has number of a characters greater than or equal to number of b characters, and the entire string has the same number of a and b characters) with length 2n. The nth Catalan number (for n >= 0) is also explicitly defined as:

$$ Cn = \frac1{n + 1} {2n \choose n} $$

Starting from n = 0, the first 20 Catalan numbers are:

#Challenge

##I/O

###Input

###Output

#Catalog The Stack Snippet at the bottom of this post generates the catalogue from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

The nth Catalan number is the number of Dyck words (balanced strings of parenthesis or brackets such as [[][]]; formally defined as a string using two characters a and b such that any substring starting from the beginning has number of a characters greater than or equal to number of b characters, and the entire string has the same number of a and b characters) with length 2n. The nth Catalan number (for \$n\ge0\$) is also explicitly defined as: $$C_n=\frac1{n+1}\binom{2n}n$$ Starting from \$n=0\$, the first 20 Catalan numbers are:

Challenge

I/O

Input

Output

Catalog

The Stack Snippet at the bottom of this post generates the catalogue from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

The nth Catalan number is the number of Dyck words (balanced strings of parenthesis or brackets such as [[][]]; formally defined as a string using two characters a and b such that any substring starting from the beginning has number of a characters greater than or equal to number of b characters, and the entire string has the same number of a and b characters) with length 2n. The nth Catalan number (for n >= 0) is also explicitly defined as:

Starting from n = 0, the first 20 Catalan numbers are:

Write a full program or function that takes a non-negative integer n via STDIN or an acceptable alternative, and outputs the nth Catalan number. Your program must work at minimum for inputs 0-19.

The nth Catalan number is the number of Dyck words (balanced strings of parenthesis or brackets such as [[][]]; formally defined as a string using two characters a and b such that any substring starting from the beginning has number of a characters greater than or equal to number of b characters, and the entire string has the same number of a and b characters) with length 2n. The nth Catalan number (for n >= 0) is also explicitly defined as:

$$ Cn = \frac1{n + 1} {2n \choose n} $$

Starting from n = 0, the first 20 Catalan numbers are:

Write a full program or function that takes a non-negative integer n via STDIN or an acceptable alternative, and outputs the nth Catalan number. Your program must work at minimum for inputs 0-19.

The Catalan numbers (OEIS) are a sequence of natural numbers often appearing in combinatorics.

The Catalan numbers (OEIS) are a sequence of natural numbers often appearing in combinatorics.