patternMinor
What is the number of expressions containing n pairs of matching brackets with nesting limit?
Viewed 0 times
containingnumberthenestingwhatwithlimitexpressionsbracketspairs
Problem
I know the answer without nesting limit is the Catalan number. My question is, specifically, is there a recurrence relation that gives the number of expression containing $n$ pairs of matching brackets such that no more than $l$ open brackets are not closed at any given point?
For instance, for $n=3$ and $l=2$ the answer is $4$. All possible combinations are $(())()$, $()(())$, $()()()$, $(()())$. We cannot have $((()))$ since there are three open brackets that are not closed at the middle.
For instance, for $n=3$ and $l=2$ the answer is $4$. All possible combinations are $(())()$, $()(())$, $()()()$, $(()())$. We cannot have $((()))$ since there are three open brackets that are not closed at the middle.
Solution
Okay. I think I may have figured it out myself. I invite everyone to check my answer to see if it makes sense. So the first bracket must be a left bracket and there must be some right bracket later on that corresponds to this first bracket. Inside these two brackets there is a valid bracket expression $A$ with depth at most $l-1$ and outside these two brackets there is another valid expression $B$ with depth at most $l$ (since it is not already contained in a pair of brackets like $A$). Also, just like the definition of Catalan numbers, if $n=0$ then the number of valid expressions is $1$. If $n\neq 0$ and $l=0$ then the number of valid expressions is $0$ (since if $n\neq 0$ then we must have at least one pair of brackets, but $l=0$ means that we cannot have more than $0$ open bracket at any time, meaning that there is no way we can construct any valid bracket expressions). So the recurrence relation I got is:
\begin{align}
C(i, j)= \begin{cases}
1 & i=0 \\
0 & i\neq 0, j=0 \\
\sum\limits_{k=0}^{i-1} C(k, j-1)\cdot C(i-k-1, j) & \text{otherwise.}
\end{cases}
\end{align}
\begin{align}
C(i, j)= \begin{cases}
1 & i=0 \\
0 & i\neq 0, j=0 \\
\sum\limits_{k=0}^{i-1} C(k, j-1)\cdot C(i-k-1, j) & \text{otherwise.}
\end{cases}
\end{align}
Context
StackExchange Computer Science Q#2532, answer score: 5
Revisions (0)
No revisions yet.