# A recursive relation for the number of well formed nested parentheses of length $n$ and depth $\leq d$

Consider a function $$C(n, d)$$ which counts the number of well formed, i.e, balanced, parenthetical 'words' of length $$n$$ and maximal nested depth $$\leq d$$.

That is, $$(())$$ has $$n = 4, d = 2$$. $$()((())())$$ has $$n = 10, d = 3$$ and so on.

$$C(n, d)$$ counts all well formed strings above (i.e, $$($$ and $$)$$ are balanced), of length exactly $$n$$ and depth at most $$d$$ (that is, smaller depths are allowed).

There should be a recursive expression for $$C(n, d)$$.

The base cases are easy enough:

$$C(n, d) = 0$$ if $$n$$ is odd regardless.

$$C(n, d) = 0$$ if $$d = 0$$ but $$n> 0$$

$$C(n, d) = 1$$ if $$d = n= 0$$ (the empty string)

Now for the recursive step.

For instance, I first guessed $$\sum_{i}\sum_j C(n- i, d-j)C(i, j)$$ That is, you mixing all strings of length $$i$$ with strings of length $$n-i$$ should give you strings of length $$n$$. I think the depth in general will remain $$\leq d$$ without problems. But the problem with this approach is that I'm pretty sure there will be plenty of double/extra counting of the same strings more than once.
I was also thinking if I could express it solely in terms of $$C(n-2, d-1)$$ as $${n-2 \choose 2}C(n-2, d-2)$$ (placing $$(, )$$ at any positions in an $$n-2$$ string) but then this misses out on potential $$d$$ depth strings. But doing $${n-2 \choose 2}C(n-2, d)$$ might inculcate depth of $$d$$.
Suppose that $$w$$ is a well-formed parenthetical word of depth at most $$d$$. Then either $$w = \epsilon$$, or $$d > 0$$ and $$w = (x)y$$, where $$x$$ is a parenthetical word of depth at most $$d-1$$, and $$y$$ is a parenthetical word of depth at most $$d$$; furthermore, the decomposition is unique.