問題
正しい括弧列 $T$ に対して、$f(T)$ を以下のように定義します。
- $T_{i} =$
(を満たす全ての $i$ に対する以下の値の総和- $T_{i} =$
(に対応する)を $T_{j}$ としたとき、$T[i + 1:j] ( = T_{i+1}T_{i+2}\cdots T_{j - 1})$ に含まれる連続部分列()の数
- $T_{i} =$
$N$ が与えられるので、長さ $N$ の全ての正しい括弧列 $S$ に対する $f(S)$ の総和を $998244353$ で割ったあまりを求めてください。
解説
$N$ は偶数であることを仮定します。
$N = 2n$ とします。
$T$ の連続部分列として、 () が含まれているとき、その () の $f(T)$ に対する寄与は () の高さになります。つまり、 () の前にある ( の数から ) の数を引いた値です。
この「( の数から ) の数を引いた値」が $K$ であるとき、$T$ は以下のように分解できます。
- 「正しい括弧列 +
(」が $(K + 1)$ 個 + 「)+ 正しい括弧列」が $(K + 1)$ 個
これは以下の形で表せる長さ $2n - 1$ の文字列と一対一対応します。
- 「正しい括弧列 +
(」が $(2K + 1)$ 個 + 「正しい括弧列」
このような文字列は、鏡像法を用いると、$\binom{2n - 1}{n + K} - \binom{2n - 1}{n + K + 1}$ になります。
この鏡像法の使い方がわからない人は以下のブログを参照してください。もしくは、カタラン数の母関数の pow だと思っても良いです。$[x^{n - K - 1}]C^{2K + 2}(x)$ と同じ値です。
よって、答えは以下のようになります。
$$\sum_{K = 0}^{n - 1}K\left(\binom{2n - 1}{n + K} - \binom{2n - 1}{n + K + 1}\right) = \sum_{K = 1}^{n - 1}\binom{2n - 1}{n + K}$$
ここからは以下のように式変形すると、解説にもある一般項が導出できます。
$$\sum_{K = 1}^{n - 1}\binom{2n - 1}{n + K} = \frac{1}{2}\left(\sum_{k = 0}^{2n - 1}\binom{2n - 1}{k}\right) - \binom{2n - 1}{n} = 2^{2n - 2} - \binom{2n - 1}{n}$$
冪級数を用いる方針
以上の話をまとめると、$N = 2n$ のときの答えが $[x^{n}]f(x)$ で表されるような冪級数 $f$ は以下のように表されます。
$$f(x) = \sum_{K = 0}^{\infty}K(xC^{2}(x))^{K + 1} = \left(\frac{xC^{2}(x)}{1 - xC^{2}(x)}\right)^{2}$$
ここで、$s = \sqrt{1 - 4x}$ とすると、以下の変形が成り立ちます。
$$xC^{2}(x) = x\left(\dfrac{1 - s}{2x}\right)^{2} = \dfrac{(1 - s)^{2}}{4x}$$
$$1 - xC^{2}(x) = \dfrac{4x - (1 - s)^{2}}{4x} = \dfrac{1 - s^{2} - (1 - s)^{2}}{4x} = \dfrac{s(1 - s)}{2x}$$
よって、答えについて以下が成り立ちます。
$$f(x) = \left(\dfrac{(1 - s)}{2s}\right)^{2} = \dfrac{1 - 2s + s^{2}}{4s^{2}} = \frac{1}{4(1 - 4x)} + \frac{1}{2\sqrt{1 - 4x}} + \frac{1}{4}$$
中心二項係数と呼ばれているものから、以下が成り立ちます。
$$[x^{a}]\frac{1}{\sqrt{1 - 4x}} = \binom{2a}{a}$$
参考
よって任意の正整数 $n$ について、以下が成り立ちます。
$$[x^{n}]f(x) = [x^{n}]\left(\frac{1}{4(1 - 4x)} + \frac{1}{2\sqrt{1 - 4x}} + \frac{1}{4}\right) = 4^{n - 1} + \frac{1}{2}\binom{2n}{n} = 4^{n - 1} + \binom{2n - 1}{n - 1}$$
