Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

4 Answers 4

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}

share|improve this answer
    
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.
share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
    
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
    
Ahh. Thank you very much! –  Aden Dong Jun 29 '12 at 14:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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