# What is the number of expressions containing n pairs of matching brackets with nesting limit?

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.

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}

• Haha, I overkilled. This looks good. Do you want to solve it, too? – Raphael Jun 28 '12 at 19:32
• What does solving mean? – Aden Dong Jun 28 '12 at 22:22
• Solving the recurrence, that is finding a closed form for $C(i,j)$. – Raphael Jun 28 '12 at 22:46
• Is there actually a closed form for this recurrence? I am not actually very good at solving recurrences and I can only solve some basic ones. So would you mind solving the recurrence, if possible? – Aden Dong Jun 28 '12 at 23:53
• It probably has; whether we can find it is another question. There are some methods you can employ, but this is not a straightforward recurrence. I'll ask some experts. – Raphael Jun 29 '12 at 13:32

Turns out this is not an easy problem, but it has been solved. A similar case is treated in Bounded discrete walks by Banderier and Nicodème (2010) and they refer to the exact result you need in Combinatoire analytique des chemins et des cartes¹ by Banderier (2001).

1. This is a preliminary version. You can obtain a copy of the final version by contacting the author.

A comment and a suggestion.

For fixed $\ell$ the language of words with nesting limit $\ell$ is regular, with a very simple automaton, basically a line of states, each representing the current level. Form that automaton a recurrence formula can be obtained (in terms of the number of bracket pairs $n$, again for fixed $\ell$).

Your own formula reminds of the classical formula for Catalan numbers, using convolution $C_{n+1} = \sum_{i=0}^n C_iC_{n-i}$. Convolution is a nice operation when the sequence is presented as generating function, a formal infinite "polynomial"; for Catalan numbers $C(x) = \sum_{n\ge0} C_nx^n$. From the given recurrence one obtains $\frac {C(x)-1}x = C(x)^2$ from which experts can solve $C_n$.

In your formula you have an expression for $C_{\ell+1}(x)$ and $C_{\ell}(x)$, the generating functions for $\ell+1$ and $\ell$ bounded expressions. To me it seems [I might have errors here] that your formula is $\frac {C_{\ell+1}(x)-1}x = C_{\ell+1}(x)C_{\ell}(x)$. That is a recurrence relation for $C_\ell(x). Not in the numbers themselves, but in their generating functions. The question comes down to: how many ways are there to distribute$n$nodes into subtrees? This is related to integer partitions; in fact, this recurrence describes the desired quantity:$\qquad \displaystyle \begin{align} a(1,1) &= 1 \\ a(n,1) &= 0 \qquad\qquad\qquad\qquad\qquad\qquad, n>1 \\ a(n,l) &= \sum_{P \in \operatorname{Part}(n)} \prod_{i \in P} a(i,l-1) \qquad, n,l > 1 \end{align}$with$\operatorname{Part}(n)$the set of all partitions (as multi-sets) of$n$. Well, that does not seem to be too approachable. A more promising avenue might be via grammars and their generating function. For fixed$l \in \mathbb{N}_+$, the (unambiguous) grammar$G_l = (\{S_i \mid 0 \leq i \leq l \},\{(,)\},\delta_l, S_l)$with$\delta_l$given by$\qquad \displaystyle \begin{align} S_0 &\to \varepsilon \\ S_i &\to (S_{i-1})S_i \mid \varepsilon \qquad, 0<i\leq l \end{align}$generates the Dyck-language restricted to nesting depth$l$. This translates to the equation system$\qquad \displaystyle \begin{align} S_0(z) &= 1 \\ S_i(z) &= z^2S_{i-1}(z)S_i(z) + 1 \qquad, 0<i\leq l \end{align}$and$[z^n]S_l(z)$, that is the$n$-th coefficient of the series expansion of$S_l$(around$z=0$), is the number of such words of length$n$. See here and here for other examples of this technique with references. For every fixed$l$, solving this system is easily done by computer algebra. I will have to ask around whether there are techniques to solve it in$l\$; I know that similar cases have been solved before.

• Is there a good book from which I can learn what you wrote above (i.e. integer partitions, generating function etc.)? – Aden Dong Jun 28 '12 at 23:57
• @AdenDong: I have no expertise in number theory myself (maybe search/ask on Mathematics?). For generating functions, see generationfunctionology by Wilf and Analytic Combinatorics by Flajolet and Sedgewick. For the specific technique regarding grammars, have a look at the references I give in the linked answers. – Raphael Jun 29 '12 at 12:34