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.

I've been thinking about this but there are a lot of overlap which makes things difficult.

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 have a few other candidates but again I think they largely double count in general.

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$.


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.