解析的組合せ論

同義語:analytic combinatorics

概要

解析的組合せ論(analytic combinatorics)とは、組合せ構造の個数の列を母関数で表し、母関数を複素関数として調べて個数の漸近挙動を求める分野である。構造の定義を母関数の式へ翻訳する記号的方法と、原点に最も近い特異点の位置と型から係数の増え方を読む特異点解析が 2 つの段である。たとえば Catalan 数の母関数は $z=1/4$ に平方根の特異点をもち、これだけから $C_n\sim4^n/(\sqrt{\pi}\,n^{3/2})$ が従う。特異点から読めない場合には鞍点法を使う。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 母関数, 収束半径, 留数定理

解析的組合せ論(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)。

第 1 段:記号的方法

組合せクラスを基本の構成で組み立てると、母関数は次の表の規則で決まる(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}$
定義から母関数へ
  1. 二分木:葉だけの木、または根と左右の 2 本の部分木からなる。内部の頂点の個数を大きさとすると $\mathcal T=1+\mathcal Z\times\mathcal T\times\mathcal T$ なので $T(z)=1+zT(z)^2$ である。個数の列は Catalan数 である。
  2. 整数の分割:正の整数のクラス($b_m=1$)の多重集合なので $\prod_{m\ge1}(1-z^m)^{-1}$ であり、分割の母関数 と一致する。
  3. 順序付きの集合分割:$\{1,\dots,n\}$ を空でない部分の列に分ける方法の数 $r_n$ は $1,1,3,13,75,541,\dots$ で、空でない集合の列なので指数型母関数は $\dfrac1{1-(e^z-1)}=\dfrac1{2-e^z}$ である。
  4. ラベル付きの根付き木:根と、根付き木の集合の組なので、指数型母関数は $T(z)=z\exp T(z)$ をみたす。個数は $n^{n-1}$ である(Cayleyの公式 の木に根を選ぶと $n\cdot n^{n-2}$)。

主な問題と結果の一覧

問い代表的な結果入る記事
定義から母関数の式が得られるか上の表。再帰的な定義は母関数の連立方程式になる母関数, 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、分割数)。

具体例

Catalan 数の漸近形

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数え上げ組合せ論, 母関数個数の列と形式的な母関数の扱い
2Catalan数, 分割数, Stirlingの公式閉じた式や初等的な評価で得られる漸近形の実例
3収束半径, 留数定理, 解析接続, ガンマ関数特異点解析に使う複素解析
4この記事の第 1 段と thm-ac-transfer定義から漸近形までの手順
5漸近解析, Laplaceの方法積分の漸近評価と鞍点法
6確率母関数, 中心極限定理パラメータの分布の極限法則

全体の体系は FS09 が記号的方法(第 I–III 章)、複素解析による漸近(第 IV–VIII 章)、極限法則(第 IX 章)の順に述べている。数え上げの答えの形としての漸近公式の位置づけと、分割数の公式の出典は Sta12 §1.1、§1.8 にある。

関連項目

参考文献

[1]
Philippe Flajolet, Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009, Definition I.1(p. 16)、Theorem I.1(p. 27)、Definition II.2(p. 97)、Theorem II.1(p. 103)、第 IV 章 p. 227・p. 243、Theorem IV.6(p. 240)、Theorem IV.7(p. 244)、Note IV.17(p. 249)、Example IV.7(p. 259)、Theorem VI.1(p. 381)、Definition VI.1(p. 389)、Theorem VI.3(p. 390)、Corollary VI.1(p. 392)、Theorem VI.6(p. 404)、Theorem VII.3(p. 468)、Proposition VIII.3(p. 562)、Theorem VIII.4(p. 565)、Proposition VIII.6(p. 578)、Theorem IX.8(p. 645)、Theorem IX.9(p. 656)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する