$C_n$(the $n^{th}$ catalan number) counts the number of expressions containing $n$ pairs of parenthesis which are correctly matched How to count the possibilities if the maximum nesting level is fixed to $d$?
Total no. of balanced parenthesis with maximum nesting of $d$
2
$\begingroup$
combinatorics
sequences-and-series
1 Answers
5
The answer is described in several equivalent ways in this blog post. For fixed $d$ the corresponding sequence $C_{d,n}$ satisfies a linear recurrence, and its generating function is "the $d^{th}$ convergent" of a continued fraction representation of the generating function of the Catalan numbers. Explicitly,
$C_{d,n} = \frac{1}{d+1} \sum_{i=1}^d 2 \sin^2 \frac{\pi}{d+1} \left( 2 \cos \frac{\pi i}{d+1} \right)^{2n}.$
(The indexing may be off by one.)