↓ メインコンテンツへスキップ
組合せ論、楽しい！

【月刊組合せ論 Natori】森の数え上げとカタラン数の畳み込み【2023 年 4 月号】

·
数え上げ 競プロ
箱星
著者
箱星
のんびり暮らしたい。
目次

月刊組合せ論 Natori は面白そうな組合せ論のトピックを紹介していく企画です。今回はカタラン数と畳み込みについて考えます。

木の数え上げ
#

木は根付き木で子の順序を区別します。次の 2 つの木は異なるものと考えます。

頂点数が n+1n+1 個の木の個数を CnC_n とおきます。

上の図は 7 頂点の木です。根から出る辺のうち最も左のものを削除すると、3 頂点の木と 4 頂点の木になります。このように、木は頂点数がより少ない木を組み合わせて作れると考えると次のような漸化式が成り立つことがわかります。

Cn+1=∑i=0nCiCn−i C_{n+1}=\sum_{i=0}^n C_iC_{n-i}

この漸化式と C0=1C_0=1 により数列 (Cn)(C_n) が計算できます。計算すると 1,1,2,5,14,42,…1,1,2,5,14,42,\ldots という数列になります。

CnC_n はカタラン数と呼ばれており、

  • 頂点数 n+1n+1 の木の個数
  • 頂点数 2n+12n+1 の二分木の個数
  • 長さ 2n2n の正しい括弧列の個数
  • 正 n+2n+2 角形の三角形分割の個数

などに等しいです。個数がカタラン数に等しくなるオブジェクトはたくさん知られており、まさに数え上げ組合せ論の中心であると言えます。

森の数え上げ
#

頂点数が n+3n+3 で連結成分が 3 個の森を数え上げてみましょう。ただし連結成分の順序も区別します。連結成分の頂点数を a+1,b+1,c+1a+1, b+1, c+1 とすると、木の個数はそれぞれ Ca,Cb,CcC_a, C_b, C_c となります。よって

∑a+b+c=nCaCbCc \sum_{a+b+c=n}C_aC_bC_c

が答えとなります。一般にこのような形の式を畳み込みといいます。

ここで母関数を用います。カタラン数の母関数を

C(x)=∑i=0∞Cixi C(x)=\sum_{i=0}^{\infty}C_ix^i

とおくと、答えは C(x)3C(x)^3 における xnx^n の係数に等しくなります。この値を [xn]C(x)3[x^n]C(x)^3 と書きます。

同様に頂点数が n+kn+k で連結成分が kk 個の森の個数は [xn]C(x)k[x^n]C(x)^k となります。

ラグランジュ反転公式
#

[xn]C(x)k[x^n]C(x)^k を求めます。ラグランジュ反転公式を用います。

定理（ラグランジュ反転公式）

形式的冪級数 ϕ(u)=∑k≥0ϕkuk\phi(u)=\sum_{k\ge 0}\phi_ku^k は ϕ0≠0\phi_0\ne 0 をみたすとし、y=y(x)y=y(x) は y=xϕ(y)y=x\phi(y) をみたすとする。このとき

[xn]y(x)k=kn[un−k]ϕ(u)n [x^n]y(x)^k=\frac{k}{n}[u^{n-k}]\phi(u)^n

が成り立つ。

証明は [2] や [1] などを参照してください。

y(x)=xC(x)y(x)=xC(x) とおきます。カタラン数の漸化式

Cn+1=∑i=0nCiCn−i C_{n+1}=\sum_{i=0}^n C_iC_{n-i}

から、y−y2=xy-y^2=x が成り立ちます。よって、ϕ(u)=1/(1−u)\phi(u)=1/(1-u) とおくとラグランジュ反転公式の仮定をみたします。したがって

[xn](xC(x))k=kn[un−k](11−u)n [x^n](xC(x))^k=\frac{k}{n}[u^{n-k}]\left(\frac{1}{1-u}\right)^n

が得られます。右辺に負の二項定理を用いることで

[xn](xC(x))k=kn(2n−k−1n−k) [x^n](xC(x))^k=\frac{k}{n}\binom{2n-k-1}{n-k}

となります。よって

[xn]C(x)k=[xn+k](xC(x))k=kn+k(2n+k−1n) [x^n]C(x)^k=[x^{n+k}](xC(x))^k=\frac{k}{n+k}\binom{2n+k-1}{n}

が得られました。

特に k=1k=1 とすれば、カタラン数が

Cn=1n+1(2nn) C_n=\frac{1}{n+1}\binom{2n}{n}

という閉じた式で表せることがわかります。

問題
#

競技プログラミングでは [xn]C(x)k[x^n]C(x)^k の計算を用いる問題がたまに出題されます。そのような問題を一部紹介します。

解法のネタバレを含むのでご注意ください。

yukicoder No.1662 (ox) Alternative
#

問題リンク：https://yukicoder.me/problems/no/1662

正しい括弧列の個数もカタラン数です。)( を挿入できない箇所が kk 個あるような括弧列の個数を数える必要がありますが、森の数え上げと同様にできます。

京都大学プログラミングコンテスト 2020 M - Many Parentheses
#

問題リンク：https://atcoder.jp/contests/kupc2020/tasks/kupc2020_m

長さが 2×K2\times K でない括弧列の母関数が C(x)−CKxKC(x)-C_Kx^K であることから、答えは [xM](C(x)−CKxK)N[x^M] (C(x)-C_Kx^K)^N です。二項定理を用いて展開すると

[xM]C(x)N−(N1)CK[xM−K]C(x)N−1+(N2)CK2[xM−2K]C(x)N−2−⋯ [x^M]C(x)^N-\binom{N}{1}C_K[x^{M-K}]C(x)^{N-1}+\binom{N}{2}C_K^2[x^{M-2K}]C(x)^{N-2}-\cdots

となります。各項を具体的に計算できます。

Xmas Contest 2022 D - Dichotomy
#

問題リンク：https://atcoder.jp/contests/xmascon22/tasks/xmascon22_d

これも [xn]C(x)k[x^n]C(x)^k の計算に帰着されるそうです。（筆者は解いていません）

おわりに
#

カタラン数の畳み込みについて解説しました。競技プログラミングでたまに見かけるテクニックなので、覚えておくとよいことがあるかもしれません。

今後も月刊組合せ論 Natori では様々な組合せ論のトピックを扱っていきます。

参考文献
#

  1. Dominik Beck, Piotr Maćkowiak. Non-external Proofs of Lagrange Inversion Formula, https://arxiv.org/abs/2605.04319
  2. Flajolet, Philippe; Sedgewick, Robert. Analytic combinatorics. Cambridge University Press (2009).
  3. [Tutorial] Catalan Numbers and Catalan Convolution, https://codeforces.com/blog/entry/87585
  4. グリッドの最短経路の数え上げまとめ - かんプリンの学習記録, https://kanpurin.hatenablog.com/entry/2021/09/15/220913