You have a trie of sequence of correct bracket sequence of length 2n. What is the size of the maximum matching (the largest set of edges such that there are no two edges with a common vertex) in this trie?

For ex:
n = 1, output = 1
n = 3, output = 9

for n = 1, trie will look like this
root
|
(
|
)

Simple dp problem, took some time at first, but finally solved it : ). Fingers crossed !