"EXPRESSIONS" (POLAND)
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?
Task
Write a program which
Output data
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.
Example
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:
(())()
()(())
(()())