解析的組合せ論(analytic combinatorics)とは、組合せ構造の個数の列を母関数で表し、母関数を複素関数として調べて個数の漸近挙動を求める分野である。構造の定義を母関数の式へ翻訳する記号的方法と、原点に最も近い特異点の位置と型から係数の増え方を読む特異点解析が 2 つの段である。たとえば Catalan 数の母関数は $z=1/4$ に平方根の特異点をもち、これだけから $C_n\sim4^n/(\sqrt{\pi}\,n^{3/2})$ が従う。特異点から読めない場合には鞍点法を使う。
解析的組合せ論(analytic combinatorics)とは、組合せ構造の個数の列を 母関数 で表し、その母関数を複素平面の上の関数として調べて、個数の漸近挙動を求める分野である。中心の問いは「$n$ が大きいとき、大きさ $n$ の構造はおよそ何個あるか」である。
方法は 2 段からなる。第 1 段の 記号的方法 は、構造の定義を母関数の式へ機械的に翻訳する。第 2 段の 特異点解析 は、原点に最も近い特異点の位置と型から係数の増え方を読む。閉じた式がない列にも使え、閉じた式がある列では Stirling の公式を使わずに同じ漸近形が出る。
この記事は分野の地図である。個別の定理の証明はそれぞれの記事と文献にあり、ここでは主張の形と、どの場合にどの方法を使うかをまとめる。
組合せクラス(combinatorial class)とは、集合 $\mathcal A$ と写像 $\lvert\cdot\rvert\colon\mathcal A\to\mathbb N$ の組であって、各 $n\in\mathbb N$ について $\lvert\alpha\rvert=n$ となる $\alpha\in\mathcal A$ の個数 $a_n$ が有限であるものをいう。$\lvert\alpha\rvert$ を $\alpha$ の 大きさ といい、$(a_n)_{n\ge0}$ を $\mathcal A$ の 個数の列 という。
大きさ $n$ の構造が $n$ 個の頂点や文字からなり、それらが $1,\dots,n$ のラベルで区別されているとき、そのクラスを ラベル付き という。ラベルなしのクラスには 母関数 の通常母関数 $A(z)=\sum_{n\ge0}a_nz^n$、ラベル付きのクラスには指数型母関数 $\sum_{n\ge0}a_nz^n/n!$ を使う(FS09 Definition I.1, p. 16、Definition II.2, p. 97)。階乗で増える列も、指数型にすれば収束半径が正になることが多い。
複素数列 $(f_n)$ と $K\ge0$ について、$\limsup_{n\to\infty}\lvert f_n\rvert^{1/n}=K$ であることを $f_n\bowtie K^n$ と書き、$f_n$ の 指数的な位数 は $K^n$ であるという(FS09 p. 243)。
$K>0$ のとき、$f_n\bowtie K^n$ は「$f_n=K^n\theta(n)$、$\limsup\lvert\theta(n)\rvert^{1/n}=1$」と同じである。$K$ の部分を指数の底、$\theta(n)$ を指数より遅い因子とよぶ。解析的組合せ論の 2 つの原理は、特異点の 位置 が $K$ を決め、特異点の 型 が $\theta(n)$ を決める、というものである(FS09 p. 227)。
組合せクラスを基本の構成で組み立てると、母関数は次の表の規則で決まる(FS09 Theorem I.1, p. 27、Theorem II.1, p. 103)。$\mathcal Z$ は大きさ $1$ の元が 1 つだけのクラスで、$z$ に対応する。列・集合・巡回を作るクラス $\mathcal B$ には大きさ $0$ の元がないとする。表の $\varphi$ は Eulerのφ関数、$b_m$ は $\mathcal B$ の個数の列である。
| 構成 | 何を作るか | 通常母関数(ラベルなし) | 指数型母関数(ラベル付き) |
|---|---|---|---|
| 和 $\mathcal B+\mathcal C$ | 交わらない和 | $B+C$ | $B+C$ |
| 積 $\mathcal B\times\mathcal C$ | 組(ラベル付きでは両方へラベルを分ける) | $BC$ | $BC$ |
| 列 $\mathrm{SEQ}(\mathcal B)$ | 有限列 | $\dfrac1{1-B}$ | $\dfrac1{1-B}$ |
| 集合 $\mathrm{SET}(\mathcal B)$ | 順序のない集まり(重複なし) | $\prod_{m\ge1}(1+z^m)^{b_m}$ | $\exp B$ |
| 多重集合 $\mathrm{MSET}(\mathcal B)$ | 順序のない集まり(重複あり) | $\prod_{m\ge1}(1-z^m)^{-b_m}$ | 集合と同じ構成になるので使わない |
| 巡回 $\mathrm{CYC}(\mathcal B)$ | 回転で同一視した列 | $\sum_{k\ge1}\dfrac{\varphi(k)}k\log\dfrac1{1-B(z^k)}$ | $\log\dfrac1{1-B}$ |
| 問い | 代表的な結果 | 入る記事 |
|---|---|---|
| 定義から母関数の式が得られるか | 上の表。再帰的な定義は母関数の連立方程式になる | 母関数, Pólyaの数え上げ定理, 分割の母関数 |
| 指数の底は何か | thm-ac-exp:底は最も近い特異点までの距離の逆数 | 収束半径 |
| 極だけが効くとき | 有理関数・有理型関数は部分分数で係数が決まる(下の ex-ac-surjection) | 母関数, 留数定理, Fibonacci数 |
| 冪の型の特異点のとき | thm-ac-transfer:$(1-z)^{-\alpha}$ の係数は $n^{\alpha-1}/\Gamma(\alpha)$ | ガンマ関数, Catalan数 |
| 木のように陰関数で定まるとき | rem-ac-trees:平方根の特異点から $n^{-3/2}$ | Cayleyの公式 |
| 特異点から読めないとき | 鞍点法:Cauchy の積分を鞍点の近くで評価する(rem-ac-saddle) | Bell数, 分割数, Stirlingの公式, 漸近解析 |
| 大きな構造のパラメータはどう分布するか | 二変数の母関数の特異点の動きが条件をみたすとき Gauss 型の極限法則が出る(FS09 Theorem IX.8, p. 645、Theorem IX.9, p. 656) | 確率母関数, 中心極限定理 |
$f$ が原点で解析的で、$R:=\sup\{r\ge0:f\text{ は }\lvert z\rvert< r\text{ で解析的}\}$ が正の実数のとき、$[z^n]f(z)\bowtie(1/R)^n$ である。係数がすべて非負なら $z=R$ は $f$ の特異点である(Pringsheim の定理)。
この記事では証明しない(FS09 Theorem IV.6, p. 240、Theorem IV.7, p. 244)。前半は Cauchy–Hadamardの公式 を言い換えたものである。組合せクラスの母関数の係数は非負なので、特異点は正の実軸の上で探せばよい。
$\Delta$ 領域 とは、$R>1$、$0<\theta<\pi/2$ について $\Delta(\theta,R)=\{z:\lvert z\rvert< R,\ z\ne1,\ \lvert\arg(z-1)\rvert>\theta\}$ の形の領域である(FS09 Definition VI.1, p. 389)。単位円板を $z=1$ の近くだけ切り欠いて外へ広げた形をしている。
$f$ が $\Delta$ 領域で解析的で、$\alpha$ は $0,-1,-2,\dots$ のどれでもない実数とする。$z\to1$($z$ は $\Delta$ 領域の中)で $f(z)\sim(1-z)^{-\alpha}$ なら
$$
[z^n]f(z)\sim\frac{n^{\alpha-1}}{\Gamma(\alpha)}\qquad(n\to\infty)
$$
である。また、任意の実数 $\alpha$ について、$f(z)=O((1-z)^{-\alpha})$ なら $[z^n]f(z)=O(n^{\alpha-1})$ である。
この記事では証明しない(FS09 Theorem VI.1, p. 381、Theorem VI.3, p. 390、Corollary VI.1, p. 392)。証明は Cauchy の積分公式の積分路を $\Delta$ 領域の中へ押し広げ、$\lvert z-1\rvert$ が $1/n$ 程度の部分を Hankel の積分で評価する。
$\rho$ が絶対値の最小の特異点でほかに同じ絶対値の特異点がなく、$f(\rho z)$ が $\Delta$ 領域で解析的なときは、$f(\rho z)$ に当てて $\rho^{-n}$ を掛ける。標準形の係数は次のとおりである。
| 関数 | 特異点の型 | $[z^n]$ の主要項 |
|---|---|---|
| $(1-z/\rho)^{-1}$ | 単純極 | $\rho^{-n}$ |
| $(1-z/\rho)^{-m}$($m\ge1$ は整数) | 位数 $m$ の極 | $\rho^{-n}n^{m-1}/(m-1)!$ |
| $(1-z/\rho)^{1/2}$ | 平方根 | $-\rho^{-n}n^{-3/2}/(2\sqrt\pi)$ |
| $(1-z/\rho)^{-1/2}$ | 平方根の逆数 | $\rho^{-n}n^{-1/2}/\sqrt\pi$ |
| $\log\dfrac1{1-z/\rho}$ | 対数 | $\rho^{-n}/n$(ちょうどこの値) |
特異点解析は、支配的な特異点が孤立していて、その外まで解析接続できることを使う。次の例は、それが欠けると主要項の形が変わることを示す。
| 満たす性質 | 欠ける条件 | 例 | 起こること |
|---|---|---|---|
| 指数の底が定まる | 支配的な特異点が 1 つ | $\dfrac1{1-z^2}$($\pm1$ に極) | 係数は $1,0,1,0,\dots$ で、$[z^n]f\sim c$ の形に書けない |
| 係数が非負、$R=1$ | $\Delta$ 領域への接続 | $\prod_{m\ge1}(1-z^m)^{-1}$ | 単位円が自然境界(FS09 Note IV.17, p. 249)で、thm-ac-transfer は使えない |
| 通常母関数が定義できる | $R>0$ | $\sum_{n\ge0}n!\,z^n$ | $R=0$ で複素関数にならない。指数型にすると $\dfrac1{1-z}$ である |
形式的な級数としては正しくても収束しない母関数の扱いは 母関数に数を代入してよいとき にある。
$\varphi$ は原点で解析的で係数が非負、$\varphi(0)\ne0$、1 次以下の多項式でなく、$p\ge2$ について $u^p$ の冪級数でないとする。$\varphi$ の収束円の中に $\varphi(\tau)=\tau\varphi'(\tau)$ となる $\tau>0$ があれば、$y=z\varphi(y)$、$y(0)=0$ の解は
$$
[z^n]y(z)\sim\sqrt{\frac{\varphi(\tau)}{2\varphi''(\tau)}}\,\frac{\rho^{-n}}{\sqrt{\pi n^3}},\qquad\rho=\frac{\tau}{\varphi(\tau)}
$$
をみたす(FS09 Theorem VI.6, p. 404。この記事では証明しない)。$\varphi(u)=e^u$ では $\tau=1$、$\rho=1/e$ で、$n^{n-1}/n!\sim e^n/\sqrt{2\pi n^3}$ を与える。これは Stirlingの公式 から直接出る形と一致する。
$n^{-3/2}$ は $\varphi$ によらない。方程式 $z=y/\varphi(y)$ が $y=\tau$ で 2 次の極値をもつので、解 $y(z)$ に平方根の特異点が必ず現れるからである。より一般の方程式 $y=G(z,y)$ でも、滑らかな陰関数の図式とよばれる条件のもとで同じことが成り立つ(FS09 Theorem VII.3, p. 468)。
整関数や自然境界をもつ関数では、Cauchy の積分公式の積分路を、被積分関数 $f(z)z^{-n-1}$ の鞍点を通る円にとって評価する(FS09 Theorem VIII.4, p. 565)。集合の分割の数 Bell数 の指数型母関数 $e^{e^z-1}$ は整関数で、$e^{e^z-1}z^{-n-1}$ の正の鞍点は $re^r=n+1$ の解 $r$ である(FS09 Proposition VIII.3, p. 562)。分割数は同じ方法で $p(n)\sim e^{\pi\sqrt{2n/3}}/(4\sqrt3\,n)$ となる(FS09 Proposition VIII.6, p. 578、分割数)。
ex-ac-symbolic の 1 の $T(z)=1+zT(z)^2$ を解く。原点で値 $1$ をとる枝は
$$
T(z)=\frac{1-\sqrt{1-4z}}{2z}
$$
である。分子は $z=0$ で $0$ になるので原点は特異点でなく、有限の特異点は $z=1/4$ だけで、そこは平方根の型である。したがって指数の底は $4$ である。係数は $C_n=[z^n]T(z)=-\frac12[z^{n+1}](1-4z)^{1/2}$ で与えられる。$\Gamma(-1/2)=-2\sqrt\pi$ を thm-ac-transfer に $\alpha=-1/2$、$\rho=1/4$ として使うと
$$
C_n\sim\frac12\cdot\frac{4^{n+1}(n+1)^{-3/2}}{2\sqrt\pi}\sim\frac{4^n}{\sqrt\pi\,n^{3/2}}
$$
を得る。$n=10$ で $C_{10}=16796$、右辺は約 $18708$ で比は約 $0.898$ である。$n=100$ で比は約 $0.989$ になる。閉じた式 $C_n=\frac1{n+1}\binom{2n}n$ と Stirlingの公式 の系からも同じ形が出るが、ここでは閉じた式を使っていない。
$R(z)=\sum_{n\ge0}r_nz^n/n!=1/(2-e^z)$ の極は $z=\log2+2\pi ik$($k\in\mathbb Z$)である。最も近い極は $\rho=\log2$ で、次に近い極の絶対値は $\sqrt{(\log2)^2+4\pi^2}=6.32\ldots$ である。$\rho$ の近くでは $2-e^z=-2(z-\rho)(1+O(z-\rho))$ なので、留数を計算すると
$$
R(z)-\frac1{2(\rho-z)}
$$
は $\lvert z\rvert\le6$ で解析的である。この関数の係数は Cauchy の評価で $O(6^{-n})$ であり、$\dfrac1{2(\rho-z)}=\dfrac1{2\rho}\sum_{n\ge0}(z/\rho)^n$ なので
$$
\frac{r_n}{n!}=\frac12(\log2)^{-n-1}+O(6^{-n})
$$
が成り立つ。$n=5$ では $r_5/5!=541/120=4.50833\ldots$、主要項は $4.50834\ldots$ である。これは閉じた式を経由しない完全な計算である(FS09 Example IV.7, p. 259)。
| 段階 | 読む記事 | ここで得るもの |
|---|---|---|
| 1 | 数え上げ組合せ論, 母関数 | 個数の列と形式的な母関数の扱い |
| 2 | Catalan数, 分割数, Stirlingの公式 | 閉じた式や初等的な評価で得られる漸近形の実例 |
| 3 | 収束半径, 留数定理, 解析接続, ガンマ関数 | 特異点解析に使う複素解析 |
| 4 | この記事の第 1 段と thm-ac-transfer | 定義から漸近形までの手順 |
| 5 | 漸近解析, Laplaceの方法 | 積分の漸近評価と鞍点法 |
| 6 | 確率母関数, 中心極限定理 | パラメータの分布の極限法則 |
全体の体系は FS09 が記号的方法(第 I–III 章)、複素解析による漸近(第 IV–VIII 章)、極限法則(第 IX 章)の順に述べている。数え上げの答えの形としての漸近公式の位置づけと、分割数の公式の出典は Sta12 §1.1、§1.8 にある。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する