離散数学・組合せ論の問題

0 以上の整数 $h$ に対し、入れ子の深さが $h$ 以下の正しい括弧列を、括弧の組の個数 $n$（長さ $2n$）で数えた母関数を
$$F_h(x)=\sum _{n=0}^{\infty }{a}_{h,n}{x}^n$$
とする（長さ 0 の空列も 1 個と数える）。深さの制限がなければ $a_{\infty ,n}$ はカタラン数である。

最初の対応による分解. 空でない正しい括弧列 $w$ は、先頭の「(」とそれに対応する「)」によって、ただ 1 通りに
$$w=(u)v$$
と分解できる。ここで $u,v$ は正しい括弧列（空列でもよい）である。$w$ の深さが $h$ 以下であることは、$u$ の深さが $h-1$ 以下（外側の括弧で 1 段深くなるため）かつ $v$ の深さが $h$ 以下であることと同値である。括弧の組の個数は $1+(u\text{ の組数})+(v\text{ の組数})$ なので
$$F_h(x)=1+x{F}_{h-1}(x)F_h(x),\text{すなわち}{F}_h(x)=\frac{1}{1-x{F}_{h-1}(x)}.$$
$F_0(x)=1$（深さ 0 は空列のみ）から順に計算する。
$$F_1(x)=\frac{1}{1-x},F_2(x)=\frac{1}{1-\frac{x}{1-x}}=\frac{1-x}{1-2x},$$
$$F_3(x)=\frac{1}{1-\frac{x(1-x)}{1-2x}}=\frac{1-2x}{(1-2x)-x(1-x)}=\frac{1-2x}{1-3x+x^2}.$$

係数の計算. $F_3(x)=\sum b_n{x}^n$ とおくと $(1-3x+x^2)\sum b_n{x}^n=1-2x$ より
$$b_0=1,b_1-3b_0=-2,b_n=3b_{n-1}-b_{n-2}(n\ge 2).$$
よって $b_1=1$ で、
$$b_2=2,b_3=5,b_4=13,b_5=34,b_6=89,b_7=3\cdot 89-34=233.$$

確認: $n=3$ では正しい括弧列はカタラン数 $C_3=5$ 個で、深さは最大でも 3 なので $b_3=5$。$n=4$ では $C_4=14$ 個のうち深さ 4 のものは「(((())))」の 1 個だけなので $b_4=13$。いずれも一致する。

深さが 3 以下の長さ $2n$ のディック路の個数を $a_n$ とする。高さ制限 $h$ 以下のディック路の母関数は連分数で得られ、深さ 3 以下では $a_n$ はフィボナッチ数 $F_{2n-1}$ になる（$F_1=F_2=1$）。直接導出: 深さ $\le k$ の路の個数の母関数を $C_k(x)$ とすると $C_0=1$、$C_k=1/(1-x{C}_{k-1})$。$C_1=1/(1-x)$、$C_2=\frac{1-x}{1-2x}$、$C_3=\frac{1}{1-x\frac{1-x}{1-2x}}=\frac{1-2x}{1-3x+x^2}$。分母から $a_n=3a_{n-1}-a_{n-2}$（$n\ge 3$）で、$a_0=1,a_1=1,a_2=2$ より $a_3=5,a_4=13,a_5=34,a_6=89,a_7=233$。検算: $a_2=2$（()() と (())）、$a_3=5$（カタラン数 $C_3=5$ で全部深さ 3 以下）、$a_4=14-1=13$（深さ 4 は ((())) () でなく (((()))) の 1 個のみ）。よって答えは 233。