Let X be the set of correctly built parenthesis expressions. The elements of X are strings consisting only of the characters ( and ). The set X is defined as follows:
The expressions below are not correctly built parenthesis expressions (and are thus not in X):
Let E be a correctly built parenthesis expression (therefore E is a string belonging to X).
The length of E is the number of single parenthesis (characters) in E.
The depth D(E) of E is defined as follows:
ì 0 if E is empty
D(E)= í D(A)+1 if E = (A), and A is in X
î max(D(A),D(B)) if E = AB, and A, B are in X
For example, the length of ()(())() is 8, and its depth is 2.
What is the number of correctly built parenthesis expressions of length n and depth d, for given positive integers n and d?
Write a program which
The only line of the output file PAR.OUT should contain a single integer - the number of correctly built parenthesis expressions of length n and depth d.
Input data (file PAR.IN) Output data (file PAR.OUT)
6 2 3
There are exactly three correctly built parenthesis expressions of length
6 and depth 2: