Module: Catalan numbers

Problem

1 /2

Where do Catalan numbers occur?

-Number of psp with a given number of pairs of brackets

-Number of binary trees with given number of leaves

-The number of paths from the lower left corner to the upper right corner in the square n * n that do not touch the diagonal

-Number of divisions of the n-gon into triangles

How to count?

1) Formula for the nth Catalan number:

2)
•Let's have a PSS of length 2n

•Obviously it starts with an opening brace

•So, say P = (A)B, where A and B – also psp (moreover, A and B can be empty)

•If the length of A = 2k, then the sequence A can be composed in Ck ways

•Then the length of B = 2(n – k - 1) and B can be composed in Cn-k-1 ways

•We see the formula for dp: Cn = sum(Ck * Cn-k-1) for all k <

Materials used:

Output N-th number of Catalan

Input

The first line of the input contains a single number N (\(1 <= N <= 20\)).

Output

Print one number - Nth number of Catalan

#	Input	Output
1	1	1

Attach a file with the source code of the program:

or select a programming language and type your program

Auto