Problem A: EXPRESSIONS
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
For every pair of integers in the input write single integer on one line - the number of
correctly built parenthesis expressions of length n and depth d.
Example
Input data
Output data
6 2
3
300 150
1
There are exactly three correctly built parenthesis expressions of length
6 and depth 2:
(())()
()(())
(()())