# 数え上げと母関数：exp 公式・Lagrange 反転・Cayley の木の公式・Fekete の補題、二項定理・鳩の巣原理・van der Waerden

> 形式的冪級数から exp 公式と Lagrange 反転を証明し Cayley の公式を導く。Fekete の補題、二項定理と鳩の巣原理、二項係数の単峰性（Newton の不等式）、van der Waerden の定理も扱う。
> https://rikai.mugen-giken.com/mathematics/combinatorics/enumeration-generating-functions

## 0. この記事の要点

この記事は、ものの個数を数える作業を、数列を一つの式にまとめて計算で扱う方法として整理します。たとえば、1 から $n$ までの番号をつけた $n$ 個の点を辺で結んで「輪のない一つながりの図形」をつくる方法は何通りか、という素朴な疑問に、$n$ 点なら $n^{n-2}$ 通りという一行の答えが出せます。読み終えると、複雑な数え上げを式の計算に置き換える見通しと、数の増える速さを不等式で押さえる方法がわかります。

- **形式的冪級数**は、収束を一切考えずに係数の列を一つの対象として扱う道具です。可逆性・合成・微分・$\exp$ がすべて係数の有限和で定義でき、解析学の公式がそのまま代数的に成り立ちます。
- **exp 公式**: 「集合を分割し、各ブロックに"連結な構造"を載せる」という数え上げの指数型母関数は $\exp(\text{連結構造の母関数})$ です。逆に、全体の母関数の $\log$ が連結構造の母関数になります。
- **Lagrange 反転公式**: $f=x\phi(f)$ を満たす冪級数 $f$ の係数は $[x^n]f^k=\frac kn[t^{n-k}]\phi(t)^n$ で与えられます。証明は形式的留数の変数変換だけで済みます。
- この二つから **Cayley の公式**（$n$ 点上のラベル付き木は $n^{n-2}$ 個）が数行で出ます。
- **Fekete の補題**（劣加法的な列では $a_n/n$ の極限が存在して下限に等しい）から、格子動物の数 $a_n$ について $a_n^{1/n}$ が極限 $\lambda$ に収束し、しかも $a_n\le\lambda^n$ が全ての $n$ で成り立つことが従います。
- 補遺（§7・§8）として、**二項定理**と**鳩の巣原理**を定理として証明し、実根だけをもつ多項式の係数が対数凹で**単峰**になること（Newton の不等式）を二項係数・Stirling 数に使います。最後に、有限彩色で単色の等差数列が必ず現れる **van der Waerden の定理**を、色焦点の議論で一般の $k,r$ について証明します。

<Aside type="tip" title="この記事で使う事前知識">

- **可換環・多項式環**: 足し算と掛け算ができ、掛け算の順序によらない集合が可換環で、文字 $x$ の多項式の全体はその例です。→ [可換環](/mathematics/algebra/rings-and-fields#def-commutative-ring)、[多項式環](/mathematics/algebra/rings-and-fields#def-polynomial-ring)
- **整域**: 0 でない二つの元の積が 0 にならない可換環のこと。→ [整域](/mathematics/algebra/rings-and-fields#def-integral-domain)
- **環準同型**: 和と積を保つ、環から環への写像のこと。→ [環準同型](/mathematics/algebra/rings-and-fields#def-ring-hom)
- **級数と収束**: 無限和を部分和の極限として考えること。→ [級数と収束判定](/mathematics/calculus/series-and-convergence)
- **集合の分割**: 集合を、空でない互いに共通部分のない部分集合に分けること。→ [集合の分割](/mathematics/foundations/equivalence-relations#def-partition)
- **辞書式順序**: 座標を先頭から順に比べて大小を決める順序。→ [辞書式順序](/mathematics/foundations/axiom-of-choice-zorn#def-lexicographic)

</Aside>

## 1. 動機

「$n$ 個のものを数える」とき、答えが $n$ の閉じた式で書けることは稀です。しかし数列 $(a_n)$ を一つの冪級数 $\sum a_nx^n$ にまとめると、場合分けや漸化式の構造が、級数の間の等式として見えるようになります。たとえばコイン投げの列を長さごとに数える作業は、$\frac1{1-2x}$ という一つの式に畳み込まれます。

この記事は組合せ論のテーマ全体（数え上げと母関数、半順序集合と Möbius 反転、グラフと行列式）の最初の章です。テーマ全体の見通しは次のとおりです。

- **この章**: 数列を冪級数に載せて操作する技術。特に「連結なものの母関数と全体の母関数は $\exp$/$\log$ で結ばれる」という事実が主役です。
- **次の章**（[半順序集合と Möbius 反転](/mathematics/combinatorics/posets-mobius)）: 包除原理を半順序集合の言葉で一般化し、分割束の上の Möbius 関数から、モーメントとキュムラントの関係式を導きます。
- **三つ目の章**（グラフと行列式）: 行列木定理や Pfaffian など、数え上げを行列式に変換する技術です。

この三つは、統計力学の**クラスター展開**を支える組合せ論的な基礎になっています。分配関数 $Z$ の $\log$ が連結なクラスターの和になること、その各項が木の数え上げで評価できること、収束半径の下限が成長率で決まることは、それぞれこの章の exp 公式、Cayley の公式、Fekete の補題の応用場面です。

## 2. 形式的冪級数

以下、$K$ は標数 $0$ の体（$\mathbb{Q}$ や $\mathbb{C}$）とします。

<Definition id="def-fps" title="形式的冪級数環">
$K$ の元の列 $(f_n)_{n\ge0}$ を $f=\sum_{n\ge0}f_nx^n$ と書き、**形式的冪級数**と呼ぶ。$f_n$ を $f$ の $x^n$ の**係数**といい、$[x^n]f$ とも書く。和と積を
$$
(f+g)_n=f_n+g_n,\qquad (fg)_n=\sum_{i=0}^nf_ig_{n-i}
$$
で定める。この演算で形式的冪級数全体は可換環をなす。これを $K[[x]]$ と書く。$f\neq0$ に対し、$f_n\neq0$ となる最小の $n$ を $f$ の**位数** $\operatorname{ord}f$ という。
</Definition>

[多項式環](/mathematics/algebra/rings-and-fields#def-polynomial-ring) $K[x]$ はこの環の部分環です。積の定義に現れる和は有限和なので、収束の問題は起こりません。結合法則・分配法則は多項式の場合と同じ計算で確かめられます。位数については $\operatorname{ord}(fg)=\operatorname{ord}f+\operatorname{ord}g$ が成り立ちます（最低次の係数どうしの積が $f_{a}g_{b}\neq0$ だからです）。とくに $K[[x]]$ は[整域](/mathematics/algebra/rings-and-fields#def-integral-domain)です。

<Proposition id="prop-fps-inverse" title="逆元の存在">
$f\in K[[x]]$ が $K[[x]]$ で可逆であるための必要十分条件は $f_0\neq0$ である。
</Proposition>

<Proof of="prop-fps-inverse">
可逆なら $fg=1$ の定数項から $f_0g_0=1$ なので $f_0\neq0$ です。逆に $f_0\neq0$ とします。$g$ を $fg=1$ となるよう係数を順に決めます。$n=0$ では $g_0=1/f_0$。$n\ge1$ では $(fg)_n=0$ より
$$
g_n=-\frac1{f_0}\sum_{i=1}^nf_ig_{n-i}
$$
で、右辺は $g_0,\dots,g_{n-1}$ だけで決まります。これで $fg=1$ を満たす $g$ が一意に定まります。
</Proof>

たとえば $\frac1{1-x}=\sum_{n\ge0}x^n$ です（$(1-x)\sum x^n=1$ が望遠鏡和で確かめられます）。

収束は次のように定義します。

<Definition id="def-fps-convergence" title="形式的な収束と合成">
$(f^{(k)})_{k\ge0}$ を $K[[x]]$ の列とする。各 $n$ について $[x^n]f^{(k)}$ が $k$ に関して十分大きいところで一定になるとき、その一定値を係数とする級数を $(f^{(k)})$ の**極限**という。$\operatorname{ord}f^{(k)}\to\infty$ なら $\sum_kf^{(k)}$ は（各係数が有限和なので）この意味で収束する。

$g\in K[[x]]$ が $g_0=0$ を満たすとき、$f=\sum f_nx^n$ との**合成**を
$$
f\circ g=f(g)=\sum_{n\ge0}f_ng^n
$$
と定める。$\operatorname{ord}(g^n)\ge n$ なので右辺は収束する。形式的**微分**を $f'=\sum_{n\ge1}nf_nx^{n-1}$ で定める。
</Definition>

微分は積の規則 $(fg)'=f'g+fg'$ を満たします（$x^i$ と $x^j$ の積について確かめれば、双線形性と極限の連続性で一般の級数に拡がります）。標数 $0$ なので、$f'=0$ なら $f$ は定数です。合成と微分の関係は次のとおりです。

<Proposition id="prop-chain-rule" title="形式的な連鎖律">
$g_0=0$ のとき $(f\circ g)'=(f'\circ g)\,g'$ である。
</Proposition>

<Proof of="prop-chain-rule">
$f=x^k$ のとき $(g^k)'=kg^{k-1}g'$ は積の規則から従います。一般の $f$ は $f=\sum f_kx^k$ で、両辺は $f_k$ について線形で、$\operatorname{ord}$ の評価から各係数は有限和にしか関わらないので、項別に微分してよいことがわかります。
</Proof>

指数関数と対数関数も係数だけで定義できます。

<Definition id="def-fps-exp" title="形式的な exp と log">
$f_0=0$ のとき $\exp(f)=\sum_{k\ge0}\frac{f^k}{k!}$ とする（<Ref to="def-fps-convergence" /> の意味で収束する）。また $\log(1+x)=\sum_{n\ge1}\frac{(-1)^{n-1}}{n}x^n$ と定める。
</Definition>

<Proposition id="prop-fps-exp" title="exp の基本性質">
$f_0=g_0=0$ とする。

1. $\exp(f)'=f'\exp(f)$。
2. $\exp(f+g)=\exp(f)\exp(g)$。とくに $\exp(f)\exp(-f)=1$ で、$\exp(f)$ は可逆である。
3. $F\in K[[x]]$ が $F'=f'F$ かつ $F_0=1$ を満たすなら $F=\exp(f)$ である。
4. $M_0=0$ かつ $\exp(M)=1+x$ なら $M=\log(1+x)$ である。
</Proposition>

<Proof of="prop-fps-exp">
1: $\exp(x)=\sum x^k/k!$ について $\exp(x)'=\exp(x)$ は項別の微分で明らかです。$\exp(f)=\exp(x)\circ f$ なので、連鎖律（<Ref to="prop-chain-rule" />）から 1 が出ます。

2: 二項定理（$K[[x]]$ は可換）から $\frac{(f+g)^k}{k!}=\sum_{i+j=k}\frac{f^i}{i!}\frac{g^j}{j!}$。両辺を $k$ について足すと右辺は $\exp(f)\exp(g)$ です（各係数は有限和）。

3: $E=\exp(f)$ は可逆（定数項 $1$）で、$(F/E)'=\frac{F'E-FE'}{E^2}=\frac{f'FE-Ff'E}{E^2}=0$ なので $F/E$ は定数、定数項を見て $F/E=1$ です。

4: 1 より $1=(1+x)'=M'\exp(M)=M'(1+x)$ なので $M'=\frac1{1+x}=\sum_{k\ge0}(-1)^kx^k$。両辺の係数を比べて $nM_n=(-1)^{n-1}$、つまり $M_n=\frac{(-1)^{n-1}}n$ です。
</Proof>

## 3. 通常型の母関数

数列 $(a_n)_{n\ge0}$ に対し $A(x)=\sum a_nx^n$ を**通常型[母関数](/mathematics/hs-algebra/recurrences-generating-functions#def-generating-function)**といいます。漸化式や構造の分解を、冪級数の方程式に書き換えるのが基本の手順です。

<Example id="ex-compositions" title="合成の個数">
正の整数 $n$ を、順序を区別して正の整数の和に分ける方法（合成）の個数 $c_n$ を数えます。「空でない合成」は 1 個以上の「部分」（正の整数）の並びで、一つの部分の母関数は $\frac x{1-x}=x+x^2+\cdots$ です。部分の並びの母関数は $\sum_{m\ge0}\left(\frac x{1-x}\right)^m=\frac1{1-\frac x{1-x}}=\frac{1-x}{1-2x}$（$m=0$ が $n=0$ の空の合成）です。これを展開すると $1+\sum_{n\ge1}2^{n-1}x^n$ なので $c_n=2^{n-1}$ です。「$n-1$ 個の隙間のそれぞれに仕切りを入れるか入れないか」という直接の数え方と一致します。
</Example>

<Example id="ex-binary-trees" title="二分木と Catalan 数">
**二分木**を、空であるか、根に左の二分木と右の二分木をつけたものと再帰的に定めます。$n$ 頂点の二分木の個数を $b_n$ とすると、根の左右に振り分ける頂点数で場合分けして
$$
b_0=1,\qquad b_{n}=\sum_{i=0}^{n-1}b_ib_{n-1-i}\quad(n\ge1)
$$
です。$B(x)=\sum b_nx^n$ とおくと、この漸化式は $B=1+xB^2$ と同値です。この方程式を Lagrange 反転（<Ref to="thm-lagrange" />）で解くと、$b_n=\frac1{n+1}\binom{2n}n$（Catalan 数）が得られます（<Ref to="ex-catalan-lagrange" />）。
</Example>

## 4. 指数型母関数と exp 公式

ラベル付きの対象（頂点に $1,\dots,n$ の番号がついたもの）を数えるときは、積の規則がうまく働く**指数型母関数** $A(x)=\sum_{n\ge0}a_n\frac{x^n}{n!}$ を使います。

$\Pi_n$ で集合 $[n]=\{1,\dots,n\}$ の**集合分割**（空でない互いに素な部分集合＝ブロックへの分解。[集合の分割](/mathematics/foundations/equivalence-relations#def-partition)）の全体を表します。$\Pi_0$ は空の分割だけからなる（要素数 $1$）とします。

次の定理のねらいは、分割ごとに「各ブロックの重みの積」を足し上げた数 $a_n$ を、$\exp$ という一つの式にまとめることです。たとえば $n=3$ では、分割は $\{1,2,3\}$ の 1 個、$\{1,2\},\{3\}$ のような 2 ブロックのもの 3 個、$\{1\},\{2\},\{3\}$ の 1 個の計 5 個で、$a_3=c_3+3c_1c_2+c_1^3$ となります。この和が母関数の上では $\exp$ の展開に対応する、というのが主張です。

<Theorem id="thm-exp-formula" title="exp 公式">
$c_1,c_2,\dots\in K$ を任意の数とし、$a_0=1$、$n\ge1$ に対し
$$
a_n=\sum_{\pi\in\Pi_n}\prod_{B\in\pi}c_{|B|}
$$
と定める。$A(x)=\sum_{n\ge0}a_n\frac{x^n}{n!}$、$C(x)=\sum_{n\ge1}c_n\frac{x^n}{n!}$ とすると
$$
A(x)=\exp\bigl(C(x)\bigr).
$$
</Theorem>

<Proof of="thm-exp-formula">
$n+1$ を含むブロックの大きさを $k+1$（$0\le k\le n$）とします。そのブロックの残り $k$ 個の元を $[n]$ から選ぶ方法が $\binom nk$ 通り、このブロックの重みが $c_{k+1}$、残りの $n-k$ 個の元の分割の重みの総和が $a_{n-k}$ です（$n-k=0$ のときは $a_0=1$）。よって
$$
a_{n+1}=\sum_{k=0}^n\binom nkc_{k+1}a_{n-k}.
$$
両辺を $n!$ で割って $x^n$ の係数と見ると、左辺は $A'$ の係数、右辺は $\sum_k\frac{c_{k+1}}{k!}\cdot\frac{a_{n-k}}{(n-k)!}$ で $C'A$ の係数です。したがって $A'=C'A$ かつ $A_0=1$ で、<Ref to="prop-fps-exp" /> の 3 から $A=\exp(C)$ です。
</Proof>

「連結な構造」の個数を $c_n$、「連結とは限らない構造」の個数を $a_n$ とすれば、$c_n$ を「ブロックの大きさだけに依る重み」とみなして、この定理を使えます。次の三つの例が典型です。

<Example id="ex-bell-derangement" title="Bell 数・置換・乱列">
**Bell 数** $B_n=|\Pi_n|$ は全ての $c_k=1$ の場合です。$C(x)=e^x-1$ なので
$$
\sum_{n\ge0}B_n\frac{x^n}{n!}=\exp(e^x-1).
$$
**置換**は、巡回置換（サイクル）の集合への分割と見なせます。$k$ 個の元の上の巡回置換は $(k-1)!$ 個なので $c_k=(k-1)!$、$C(x)=\sum_{k\ge1}\frac{x^k}k=-\log(1-x)$ です。ここでの $-\log(1-x)$ は $-\log(1+(-x))$ の意味です。すると $A(x)=\exp(-\log(1-x))=\frac1{1-x}$ で、$a_n=n!$ と置換の総数に一致します（確認になっています）。**乱列**（不動点をもたない置換）は長さ $1$ のサイクルを禁止するので $c_1=0$、$c_k=(k-1)!$（$k\ge2$）で、$C(x)=-\log(1-x)-x$ です。したがって
$$
\sum_{n\ge0}d_n\frac{x^n}{n!}=\frac{e^{-x}}{1-x},\qquad d_n=n!\sum_{k=0}^n\frac{(-1)^k}{k!}.
$$
右の式は $e^{-x}=\sum(-x)^k/k!$ と $\frac1{1-x}=\sum x^m$ の積の係数を取ったものです。
</Example>

<Example id="ex-connected-graphs" title="連結グラフと全グラフ">
$[n]$ 上のラベル付きグラフ（辺の有無を自由に選んだもの）は $g_n=2^{\binom n2}$ 個です。グラフは連結成分への分割と、各成分の連結グラフの選択で決まるので、連結グラフの個数を $c_n$ とすると $g_n=\sum_{\pi}\prod_{B\in\pi}c_{|B|}$ です。<Ref to="thm-exp-formula" /> より
$$
\sum_{n\ge0}2^{\binom n2}\frac{x^n}{n!}=\exp\Bigl(\sum_{n\ge1}c_n\frac{x^n}{n!}\Bigr).
$$
証明中の漸化式 $g_{n+1}=\sum_k\binom nkc_{k+1}g_{n-k}$ から $c_n$ を順に求めると、$g=(1,1,2,8,64)$ に対して $c_1=1$、$c_2=1$、$g_3=8=2+2+c_3$ より $c_3=4$、$g_4=64=8+6+12+c_4$ より $c_4=38$ です。$n=3$ の連結グラフは、3 本の道（辺 2 本）と三角形の 4 個で、確かに $4$ です。

全体の母関数の $\log$ が連結なものの母関数になる、というのがクラスター展開（分配関数の $\log$ を連結なクラスターの和に展開する手法）の組合せ論的な原型です。
</Example>

## 5. Lagrange 反転公式

暗黙に定義された冪級数 $f=x\phi(f)$ の係数を、$\phi$ だけで書くのがこの節の目標です。準備として、Laurent 級数と形式的留数を導入します。

$K((x))$ を、有限個の負冪を許す級数 $\sum_{n\ge-N}f_nx^n$ の全体とします（$K[[x]]$ の商体です）。$f\in K((x))$ の**留数**を $\operatorname{res}f=f_{-1}$（$x^{-1}$ の係数）と定め、微分は項別に定めます。

次の補題は、後の Lagrange 反転の証明で、$x^n$ の係数を取り出す操作を変数の置き換えの下で扱えるようにするための道具です。性質 1 は「微分した形の級数には $x^{-1}$ の項が出ない」、性質 2 は「変数を $x$ から $F(t)$ に置き換えても、$F'(t)$ を掛けておけば $x^{-1}$ の係数は変わらない」という内容です。

<Lemma id="lem-residue" title="形式的留数の二つの性質">
1. 任意の $h\in K((x))$ について $\operatorname{res}(h')=0$。
2. $F\in K[[t]]$ が $F_0=0$、$F_1\neq0$ を満たすとき、任意の $G\in K((x))$ について
$$
\operatorname{res}_t\bigl(G(F(t))\,F'(t)\bigr)=\operatorname{res}_xG(x).
$$
ここで $F(t)=tu(t)$（$u$ は定数項が $F_1\ne0$ の級数で可逆）なので $F(t)^{-1}=t^{-1}u(t)^{-1}\in K((t))$ であり、$G(F(t))$ は意味をもつ。
</Lemma>

<Proof of="lem-residue">
1: $h=\sum h_nx^n$ の導関数に $x^{-1}$ は現れません（$x^{-1}$ は $x^0$ の微分でしか出ませんが、$x^0$ の微分は $0$ です）。

2: 両辺は $G$ について線形です。$G=\sum_{m\ge-N}g_mx^m$ のとき $G(F)F'=\sum g_mF^mF'$ で、$\operatorname{ord}(F^mF')=m$ が $m\to\infty$ で大きくなるので、$t^{-1}$ の係数に効くのは有限個の項だけです。したがって $G=x^m$ の場合に示せば十分です。$m\neq-1$ のとき $F^mF'=\frac1{m+1}(F^{m+1})'$ で、1 により留数は $0$ です。$m=-1$ のとき $F'/F=\frac{(tu)'}{tu}=\frac1t+\frac{u'}u$ で、$u'/u$ は冪級数なので留数は $1$ です。どちらも $\operatorname{res}_xx^m=\delta_{m,-1}$ と一致します。
</Proof>

<Theorem id="thm-lagrange" title="Lagrange 反転公式">
$\phi\in K[[t]]$ で $\phi_0\neq0$ とする。

1. $f_0=0$ かつ $f=x\,\phi(f)$ を満たす $f\in K[[x]]$ がただ一つ存在する。
2. 整数 $n,k\ge1$ について $[x^n]f^k=\dfrac kn[t^{n-k}]\phi(t)^n$（$n\lt k$ のときは $0$）。
3. 任意の $H\in K[[t]]$ と $n\ge1$ について $[x^n]H(f)=\dfrac1n[t^{n-1}]H'(t)\phi(t)^n$。
</Theorem>

<Proof of="thm-lagrange">
1: $f_0=0$ とすると $\phi(f)$ の $x^{n-1}$ の係数は $f_1,\dots,f_{n-1}$ だけで決まります。そこで $f_n=[x^{n-1}]\phi(f)$ と順に定めればよく（$f_1=\phi_0$）、別の解も同じ漸化式を満たすので一意です。とくに $f_1=\phi_0\neq0$ です。

2: $F(t)=t/\phi(t)\in K[[t]]$ とおくと $F_0=0$、$F_1=1/\phi_0\neq0$ です。合成 $g\mapsto g\circ f$ は[環準同型](/mathematics/algebra/rings-and-fields#def-ring-hom)なので、$f=x\phi(f)$ より $F(f(x))=f/\phi(f)=x$ です。逆向きの $f(F(t))=t$ も成り立ちます。実際、係数を順に解けば $f_0=0,f_1\neq0$ の級数 $f$ には $f\circ h=x$ となる $h$ が存在し（$[x^n](f\circ h)$ は $f_1h_n$ と $h_1,\dots,h_{n-1}$ だけの式の和で、$h_n$ について解けるからです）、すると $F=F\circ(f\circ h)=(F\circ f)\circ h=h$ なので $f\circ F=f\circ h=x$ です。

さて $n[x^n]f^k=n\operatorname{res}_x\bigl(x^{-n-1}f(x)^k\bigr)$ です。<Ref to="lem-residue" /> の 2 を $G(x)=x^{-n-1}f(x)^k$ と $F$ に適用します。$G(F(t))=F(t)^{-n-1}t^k$ なので
$$
n[x^n]f^k=n\operatorname{res}_t\bigl(t^kF^{-n-1}F'\bigr)=-\operatorname{res}_t\bigl(t^k(F^{-n})'\bigr)
$$
です（$(F^{-n})'=-nF^{-n-1}F'$ を使いました）。$(t^kF^{-n})'=kt^{k-1}F^{-n}+t^k(F^{-n})'$ の留数は <Ref to="lem-residue" /> の 1 により $0$ なので
$$
n[x^n]f^k=k\operatorname{res}_t\bigl(t^{k-1}F^{-n}\bigr)=k\operatorname{res}_t\bigl(t^{k-1-n}\phi(t)^n\bigr)=k[t^{n-k}]\phi^n.
$$

3: $H=\sum h_kt^k$ について 2 を $k$ ごとに足し合わせます。$h_0$ の項は $n\ge1$ で寄与しません。$[x^n]H(f)=\sum_{k\ge1}h_k\frac kn[t^{n-k}]\phi^n=\frac1n[t^{n-1}]\Bigl(\sum_kkh_kt^{k-1}\Bigr)\phi^n$ で、括弧の中は $H'$ です。
</Proof>

<Example id="ex-catalan-lagrange" title="Catalan 数">
<Ref to="ex-binary-trees" /> の $B$ について $g=B-1$ とおくと、$B=1+xB^2$ は $g=x(1+g)^2$ となります。$\phi(t)=(1+t)^2$ として <Ref to="thm-lagrange" /> の 2（$k=1$）を使うと、$n\ge1$ で
$$
b_n=[x^n]g=\frac1n[t^{n-1}](1+t)^{2n}=\frac1n\binom{2n}{n-1}=\frac1{n+1}\binom{2n}n
$$
です。最後の等号は $\frac1n\binom{2n}{n-1}=\frac{(2n)!}{n\,(n-1)!\,(n+1)!}=\frac{(2n)!}{n!\,(n+1)!}$ から従います。$b_1,b_2,b_3,b_4=1,2,5,14$ です。
</Example>

### 5.1. Cayley の木の公式

**木**は、閉路をもたない連結グラフです。頂点集合 $[n]$ のラベル付き木の個数を求めます。

証明の方針は、木に根を一つ選んだ「根付き木」を数えることです。根付き木から根を取り除くと、残りは根付き森（根付き木の集まり）になります。この対応を exp 公式で母関数の式 $T=x\exp(T)$ にし、Lagrange 反転で係数を読み取ります。$n+1$ 点の根付き木が「根の選び方 $n+1$ 通り」と「残り $n$ 点の根付き森」の組で決まる、というのが鍵です。

<Theorem id="thm-cayley" title="Cayley の公式">
$n\ge1$ のとき、頂点集合 $[n]$ 上の木の個数は $n^{n-2}$ である。
</Theorem>

<Proof of="thm-cayley">
$t_n$ を $[n]$ 上の**根付き木**（木と、その頂点の一つ＝根の組）の個数とします。木には根の選び方が $n$ 通りあるので、木の個数は $t_n/n$ です。

まず $T(x)=\sum_{n\ge1}t_n\frac{x^n}{n!}$ が $T=x\exp(T)$ を満たすことを示します。$[n]$ 上の**根付き森**（各連結成分に根を一つ指定したもの）の個数を $a_n$（$a_0=1$）とします。根付き森は、集合の分割と各ブロック上の根付き木の選択で決まるので、$a_n=\sum_\pi\prod_Bt_{|B|}$ です。<Ref to="thm-exp-formula" /> より $A=\sum a_n\frac{x^n}{n!}=\exp(T)$ です。一方、$[n+1]$ 上の根付き木は、根の選び方 $n+1$ 通りと、根を除いた残り $n$ 個の頂点上の根付き森（各成分の根は、元の根に隣接していた頂点）の組と一対一に対応するので、$t_{n+1}=(n+1)a_n$ です。したがって
$$
T'=\sum_{n\ge0}t_{n+1}\frac{x^n}{n!}=\sum_{n\ge0}(n+1)a_n\frac{x^n}{n!}=(xA)'.
$$
$T_0=0=(xA)_0$ なので $T=xA=x\exp(T)$ です。

これは $\phi=\exp$（$\phi_0=1\neq0$）に対する <Ref to="thm-lagrange" /> の 1 の方程式です。2 を $k=1$ で使うと
$$
\frac{t_n}{n!}=[x^n]T=\frac1n[s^{n-1}]e^{ns}=\frac1n\cdot\frac{n^{n-1}}{(n-1)!}=\frac{n^{n-1}}{n!}.
$$
したがって $t_n=n^{n-1}$ で、木の個数は $t_n/n=n^{n-2}$ です。
</Proof>

$n=3$ では $3$ 個（道が三つの中心の選び方）、$n=4$ では $16$ 個（道が 12 個、星が 4 個）です。同じ式から、根付き森の個数 $a_n=(n+1)^{n-1}$ も得られます（<Ref to="exr-forests" />）。クラスター展開では、このような木に関する数え上げが収束の評価に直接効いてきます。

## 6. Fekete の補題と格子動物の成長率

数え上げでは、$a_n$ の閉じた式が得られなくても、**指数的な成長率** $\lim a_n^{1/n}$ の存在だけは確実に言える場合があります。その標準的な道具が Fekete の補題です。

<Lemma id="lem-fekete" title="Fekete の補題">
実数列 $(\alpha_n)_{n\ge1}$ が劣加法的、すなわち全ての $m,n\ge1$ について $\alpha_{m+n}\le\alpha_m+\alpha_n$ を満たすとする。このとき $\lim_{n\to\infty}\dfrac{\alpha_n}n$ が $[-\infty,\infty)$ の中に存在し、$\inf_{n\ge1}\dfrac{\alpha_n}n$ に等しい。
</Lemma>

<Proof of="lem-fekete">
$m\ge1$ を固定します。$n\ge m$ を $n=qm+r$（$q\ge1$、$0\le r\lt m$）と書くと、劣加法性を繰り返して $\alpha_n\le q\alpha_m+\alpha_r$（$r=0$ のときは $\alpha_r$ を $0$ とする）です。したがって
$$
\frac{\alpha_n}n\le\frac{qm}n\cdot\frac{\alpha_m}m+\frac{\alpha_r}n.
$$
$n\to\infty$ のとき $qm/n\to1$ で、$\alpha_r$ は $r\lt m$ について高々 $m-1$ 個の値しかとらないので $\alpha_r/n\to0$ です。よって $\limsup_n\alpha_n/n\le\alpha_m/m$ で、$m$ は任意なので $\limsup_n\alpha_n/n\le\inf_m\alpha_m/m\le\liminf_n\alpha_n/n$ です。これは極限の存在と $\inf$ との一致を意味します。
</Proof>

**格子動物**を定義します。$\mathbb{Z}^d$ の有限部分集合 $A$ が**連結**であるとは、隣接（座標がちょうど一つだけ $1$ 違う）する点の列で $A$ の任意の 2 点が結ばれることをいいます。連結な $n$ 点集合を平行移動で同一視した類の個数を $a_n=a_n^{(d)}$ とします。$d=2$ ではこれは固定されたポリオミノ（回転・鏡映を区別する）の個数で、$a_1,\dots,a_4=1,2,6,19$ です（$a_3=6$ は直線 2 通りと L 字 4 通り）。

<Lemma id="lem-animal-supermult" title="動物の数の優乗法性">
$a_{m+n}\ge a_m\,a_n$ である。
</Lemma>

<Proof of="lem-animal-supermult">
$\mathbb{Z}^d$ に[辞書式順序](/mathematics/foundations/axiom-of-choice-zorn#def-lexicographic)を入れます。$x\lt y$ とは、$y-x$ の最初の非零座標が正であることとします。これは全順序で、平行移動と両立し（$x\lt y\Rightarrow x+z\lt y+z$）、$e_1=(1,0,\dots,0)>0$ です。

$m$ 点の動物 $A$ と $n$ 点の動物 $B$ に対し、$A$ の最大点 $\max A$ と $B$ の最小点 $\min B$ をとり、$s=\max A+e_1-\min B$ として $A\oplus B=A\cup(B+s)$ を作ります。$b\in B$ なら $b\ge\min B$ より $b+s\ge\max A+e_1>\max A$ なので、$B+s$ の全ての点は $A$ の全ての点より真に大きく、特に $A\cap(B+s)=\varnothing$ です。$\max A$ と $\min B+s=\max A+e_1$ は隣接するので $A\oplus B$ は連結な $(m+n)$ 点集合です。また $A$ や $B$ を平行移動しても $A\oplus B$ は平行移動されるだけなので、類の組から類への写像が定まります。

この写像は単射です。$C=A\oplus B$ から、$A$ は $C$ の辞書式順序で小さい方から $m$ 個の点、$B+s$ は残りの点として復元でき、$A$ と $B$ の類が決まるからです。よって $a_ma_n\le a_{m+n}$ です。
</Proof>

<Figure caption="動物 A と B の連結 A ⊕ B（d = 2、横が第 1 座標）。A の最大点（右上の格子）の右隣に B の最小点を置く。">
<svg viewBox="0 0 300 220" width="100%" role="img" aria-label="三つの格子点からなる動物 A の最大点の右隣に、二つの格子点からなる動物 B の最小点を置いて連結する様子">
  <g stroke="currentColor" stroke-opacity="0.25" stroke-width="1">
    <line x1="40" y1="40" x2="40" y2="200" /><line x1="80" y1="40" x2="80" y2="200" /><line x1="120" y1="40" x2="120" y2="200" />
    <line x1="160" y1="40" x2="160" y2="200" /><line x1="200" y1="40" x2="200" y2="200" /><line x1="240" y1="40" x2="240" y2="200" />
    <line x1="40" y1="40" x2="240" y2="40" /><line x1="40" y1="80" x2="240" y2="80" /><line x1="40" y1="120" x2="240" y2="120" />
    <line x1="40" y1="160" x2="240" y2="160" /><line x1="40" y1="200" x2="240" y2="200" />
  </g>
  <rect x="40" y="160" width="40" height="40" fill="var(--sl-color-accent)" fill-opacity="0.35" stroke="currentColor" stroke-width="1.5" />
  <rect x="40" y="120" width="40" height="40" fill="var(--sl-color-accent)" fill-opacity="0.35" stroke="currentColor" stroke-width="1.5" />
  <rect x="80" y="120" width="40" height="40" fill="var(--sl-color-accent)" fill-opacity="0.35" stroke="currentColor" stroke-width="1.5" />
  <rect x="120" y="120" width="40" height="40" fill="currentColor" fill-opacity="0.15" stroke="currentColor" stroke-width="1.5" stroke-dasharray="5 3" />
  <rect x="120" y="80" width="40" height="40" fill="currentColor" fill-opacity="0.15" stroke="currentColor" stroke-width="1.5" stroke-dasharray="5 3" />
  <text x="100" y="146" text-anchor="middle" font-size="11" fill="currentColor">max A</text>
  <text x="140" y="146" text-anchor="middle" font-size="11" fill="currentColor">min B</text>
  <text x="60" y="190" text-anchor="middle" font-size="12" fill="currentColor">A</text>
  <text x="140" y="104" text-anchor="middle" font-size="12" fill="currentColor">B</text>
  <text x="270" y="130" text-anchor="middle" font-size="11" fill="currentColor">e1</text>
  <line x1="250" y1="140" x2="290" y2="140" stroke="currentColor" stroke-width="1.5" />
  <polygon points="290,140 283,136 283,144" fill="currentColor" />
</svg>
</Figure>

<Theorem id="thm-animal-growth" title="格子動物の成長率">
極限 $\lambda_d=\lim_{n\to\infty}a_n^{1/n}$ が存在し、$\lambda_d=\sup_na_n^{1/n}$ である。したがって全ての $n$ について $a_n\le\lambda_d^{\,n}$。さらに $a_n^{1/n}\le\lambda_d\le(2d)^2$。
</Theorem>

<Proof of="thm-animal-growth">
$a_n\ge1$（直線）なので $\alpha_n=-\log a_n$ が定義でき、<Ref to="lem-animal-supermult" /> により劣加法的です。<Ref to="lem-fekete" /> より $\lim\alpha_n/n=\inf\alpha_n/n$ が存在します。符号を戻すと $\lim\frac1n\log a_n=\sup_n\frac1n\log a_n$ です。これが有限であることを上から評価します。

動物 $A$ の類は原点を含む代表をもつので、$a_n$ は原点を含む $n$ 点の動物の個数以下です。そのような $A$ の生成木（$A$ の隣接関係がなすグラフの全域木）を深さ優先で辿ると、原点から出発し、各辺を往復する長さ $2(n-1)$ の歩行で $A$ の全ての点を訪れます。各ステップは $2d$ 方向のどれかなので、$A$ はこの歩行の方向の列から復元できます。よって $a_n\le(2d)^{2(n-1)}$ で、$\frac1n\log a_n\le2\log(2d)$、すなわち $\lambda_d\le(2d)^2$ です。
</Proof>

たとえば $d=2$ では $a_3=6$ から $\lambda_2\ge6^{1/3}>1.8$ がすぐにわかります。$a_n^{1/n}$ が下からの厳密な評価を与える点が、優乗法性の利点です。（既知の数値では $\lambda_2$ は 4 より少し大きな値です。）統計力学では、このような成長率の逆数が展開の収束半径の下限を与える、という形で現れます。

## 7. 二項定理・鳩の巣原理・単峰性

母関数の議論の土台になっている、最も基本的な数え上げの道具を、改めて定理として押さえます。

### 7.1. 二項定理

<Definition id="def-binomial-coefficient" title="二項係数">
$n\ge0$ と整数 $k$ に対し、$[n]=\{1,\dots,n\}$ の $k$ 元部分集合の個数を $\binom nk$ と書き、**二項係数**という。$k<0$ または $k>n$ では $\binom nk=0$ である（$[0]=\varnothing$ とする）。
</Definition>

<Proposition id="prop-pascal" title="Pascal の漸化式と閉じた式">
$n\ge1$ のとき $\binom nk=\binom{n-1}{k-1}+\binom{n-1}k$ で、$\binom n0=1$ である。また $0\le k\le n$ で $\binom nk=\dfrac{n!}{k!\,(n-k)!}$、とくに $\binom nk=\binom n{n-k}$ である。
</Proposition>

<Proof of="prop-pascal">
$[n]$ の $k$ 元部分集合を、元 $n$ を含むものと含まないものに分けます。含むものは $n$ を除くと $[n-1]$ の $(k-1)$ 元部分集合に、含まないものは $[n-1]$ の $k$ 元部分集合そのものに、一対一に対応します。$\binom n0$ は空集合の 1 個です。閉じた式は $n$ についての帰納法で、$\frac{(n-1)!}{(k-1)!(n-k)!}+\frac{(n-1)!}{k!(n-1-k)!}=\frac{(n-1)!\,(k+(n-k))}{k!(n-k)!}=\frac{n!}{k!(n-k)!}$ です（端の $k=0,n$ は直接）。$\binom nk=\binom n{n-k}$ は、部分集合をその補集合に移す全単射、または閉じた式の対称性から従います。
</Proof>

<Theorem id="thm-binomial" title="二項定理">
$x,y$ を可換環の元とするとき、すべての $n\ge0$ について
$$
(x+y)^n=\sum_{k=0}^n\binom nk\,x^ky^{n-k}.
$$
</Theorem>

<Proof of="thm-binomial">
まず、可換環の元 $x_i,y_i$ について
$$
\prod_{i=1}^n(x_i+y_i)=\sum_{S\subseteq[n]}\ \prod_{i\in S}x_i\prod_{i\notin S}y_i
$$
を $n$ についての帰納法で示します。$n=0$ は両辺 $1$ です。$n$ で成り立つとして $(x_{n+1}+y_{n+1})$ をかけると、右辺は $x_{n+1}$ をかけた分と $y_{n+1}$ をかけた分の和で、前者は $n+1\in S$ の部分集合 $S\cup\{n+1\}$ の項、後者は $n+1\notin S$ の項になり、$[n+1]$ のすべての部分集合が 1 回ずつ現れます。ここで $x_i=x$、$y_i=y$ とおくと、$|S|=k$ の項はすべて $x^ky^{n-k}$ で、そのような $S$ は <Ref to="def-binomial-coefficient" /> により $\binom nk$ 個です。
</Proof>

<Corollary id="cor-binomial-sums" title="二項係数の和">
$\sum_{k=0}^n\binom nk=2^n$、$n\ge1$ なら $\sum_{k=0}^n(-1)^k\binom nk=0$ である。また $\sum_{i}\binom mi\binom n{k-i}=\binom{m+n}k$（Vandermonde の恒等式）である。
</Corollary>

<Proof of="cor-binomial-sums">
<Ref to="thm-binomial" /> で $(x,y)=(1,1)$、$(-1,1)$ とします。Vandermonde：多項式の等式 $(1+t)^{m+n}=(1+t)^m(1+t)^n$ の両辺の $t^k$ の係数を比べると、左辺は <Ref to="thm-binomial" /> から $\binom{m+n}k$、右辺は $\sum_i\binom mi\binom n{k-i}$ です。
</Proof>

### 7.2. 鳩の巣原理

<Theorem id="thm-pigeonhole" title="鳩の巣原理">
1. $A,B$ を有限集合、$f:A\to B$ を写像、$k\ge1$ とする。$|A|>k|B|$ ならば、ある $b\in B$ について $|f^{-1}(b)|\ge k+1$ である。とくに $k=1$ では、$|A|>|B|$ ならば $f$ は単射でない。
2. $A$ が無限集合、$B$ が有限集合なら、任意の写像 $f:A\to B$ について、ある $b\in B$ の逆像 $f^{-1}(b)$ は無限集合である。
</Theorem>

<Proof of="thm-pigeonhole">
1: $|B|$ についての帰納法です。$|B|=0$ なら $B=\varnothing$ で、写像 $A\to\varnothing$ があるのは $A=\varnothing$ のときだけですが、$|A|>0$ なので仮定に反し、主張は空虚に成り立ちます。$|B|\ge1$ とし $b_0\in B$ を取ります。$|f^{-1}(b_0)|\ge k+1$ なら終わりです。そうでなければ $|f^{-1}(b_0)|\le k$ で、$A'=A\setminus f^{-1}(b_0)$ は $|A'|\ge|A|-k>k|B|-k=k(|B|-1)$ を満たし、$f$ は $A'$ を $B\setminus\{b_0\}$ に写すので、帰納法の仮定から $b\ne b_0$ で $|f^{-1}(b)\cap A'|\ge k+1$ となるものがあります。

2: すべての $b$ について $f^{-1}(b)$ が有限だと仮定して矛盾を導きます。$A=\bigsqcup_{b\in B}f^{-1}(b)$（<Ref to="mathematics/foundations/sets-and-logic#prop-disjoint-union" />）で、有限個の有限集合の和は有限（$|B|$ についての帰納法：$A=f^{-1}(b_0)\cup A'$）なので $A$ が有限になり、矛盾です。
</Proof>

<Example id="ex-pigeonhole-sums" title="連続する項の和が n の倍数になる">
$n$ 個の整数 $a_1,\dots,a_n$ には、連続するいくつかの項の和が $n$ の倍数になる並びがあります。$S_0=0$、$S_j=a_1+\cdots+a_j$ とおくと、$n+1$ 個の整数 $S_0,\dots,S_n$ を $n$ で割った余り（$n$ 通り）に振り分ける写像は <Ref to="thm-pigeonhole" /> の 1（$k=1$）により単射でなく、$S_i\equiv S_j$（$i<j$）となる組があります。このとき $a_{i+1}+\cdots+a_j=S_j-S_i$ は $n$ の倍数です。
</Example>

<Example id="ex-dirichlet-approximation" title="Dirichlet の近似定理">
実数 $\alpha$ と正の整数 $N$ に対し、整数 $p$ と $1\le q\le N$ の整数 $q$ が存在して $|q\alpha-p|<\frac1N$ となります。実際、$N+1$ 個の数 $\{k\alpha\}$（$\{\cdot\}$ は小数部分、$k=0,\dots,N$）は $[0,1)$ にあり、これを $N$ 個の区間 $[\frac{j}{N},\frac{j+1}N)$ に振り分ける写像は <Ref to="thm-pigeonhole" /> により単射でなく、$\{i\alpha\}$ と $\{j\alpha\}$（$i<j$）が同じ区間に入ります。$q=j-i$、$p=\lfloor j\alpha\rfloor-\lfloor i\alpha\rfloor$ とすると $|q\alpha-p|=|\{j\alpha\}-\{i\alpha\}|<\frac1N$ です。
</Example>

### 7.3. 単峰性と対数凹性

<Definition id="def-unimodal" title="単峰列・対数凹列">
実数列 $a_0,\dots,a_n\ge0$ が**単峰**であるとは、ある $m$ について $a_0\le a_1\le\cdots\le a_m\ge a_{m+1}\ge\cdots\ge a_n$ が成り立つことをいう。$1\le k\le n-1$ について $a_k^2\ge a_{k-1}a_{k+1}$ が成り立つとき**対数凹**という。
</Definition>

二項係数 $\binom nk$ は、$k$ について増加してから減少します（真ん中で最大）。この形の一般的な理由を、根の位置で説明します。

<Proposition id="prop-logconcave-unimodal" title="正の対数凹列は単峰">
$a_0,\dots,a_n>0$ が対数凹ならば単峰である。
</Proposition>

<Proof of="prop-logconcave-unimodal">
$r_k=a_k/a_{k-1}$（$1\le k\le n$）とおくと、対数凹性は $a_k/a_{k-1}\ge a_{k+1}/a_k$、すなわち $r_k\ge r_{k+1}$（$r$ は非増加）です。$m$ を $r_m\ge1$ となる最大の $k$（なければ $m=0$）とします。$k\le m$ では $r_k\ge r_m\ge1$ なので $a_k\ge a_{k-1}$、$k>m$ では $r_k<1$ なので $a_k<a_{k-1}$ です。
</Proof>

<Lemma id="lem-real-rooted-derivative" title="実根だけをもつ多項式の導関数">
$P$ を実係数の $n\ge1$ 次多項式で、複素数の範囲の根（重複度を込めて $n$ 個）がすべて実数であるとする。このとき $P'$ の根（$n-1$ 個）もすべて実数である。
</Lemma>

<Proof of="lem-real-rooted-derivative">
相異なる根を $\rho_1<\cdots<\rho_s$、重複度を $m_1,\dots,m_s$（$\sum m_i=n$）とします。$\rho_i$ は $P'$ の重複度 $m_i-1$ の根です。また $P(\rho_i)=P(\rho_{i+1})=0$ なので、<Ref to="mathematics/calculus/mean-value-and-taylor#thm-rolle" /> により $P'$ は $(\rho_i,\rho_{i+1})$ に根をもちます。これらの根は $\rho_j$ と異なるので、実根の個数（重複度込み）は少なくとも $\sum(m_i-1)+(s-1)=n-1=\deg P'$ です。$P'$ の根は重複度込みでちょうど $n-1$ 個なので、すべて実数です。
</Proof>

<Theorem id="thm-newton-unimodal" title="Newton の不等式と実根多項式の単峰性">
$P(x)=\sum_{k=0}^na_kx^k$ を実係数の $n$ 次多項式（$a_n\ne0$）で、すべての根が実数であるものとする。

1. すべての $1\le k\le n-1$ について $a_k^2\ge\left(1+\dfrac1k\right)\left(1+\dfrac1{n-k}\right)a_{k-1}a_{k+1}$ である。とくに $a_k^2\ge a_{k-1}a_{k+1}$（対数凹）。
2. さらにすべての $a_k\ge0$ ならば、係数列 $a_0,\dots,a_n$ は単峰である。
</Theorem>

<Proof of="thm-newton-unimodal">
1: $a_{k-1}=0$ のときは、右辺が $0$ で左辺は $a_k^2\ge0$ なので自明です。以下 $a_{k-1}\ne0$ とします。$R(x)=P^{(k-1)}(x)=\sum_{j=k-1}^n c_jx^{j-k+1}$（$c_j=a_j\frac{j!}{(j-k+1)!}$）とおきます。$R$ は $n-k+1$ 次で、<Ref to="lem-real-rooted-derivative" /> を $k-1$ 回使うと $R$ の根 $\rho_1,\dots,\rho_{n-k+1}$ はすべて実数です。$R(0)=c_{k-1}\ne0$ なので $\rho_i\ne0$ です。次に $S(x)=x^{n-k+1}R(1/x)=\sum_{j=k-1}^nc_jx^{n-j}$ を考えます。$R(x)=c_n\prod_i(x-\rho_i)$ から $S(x)=c_n\prod_i(1-\rho_ix)$ で、$S$ は $x^{n-k+1}$ の係数が $c_{k-1}\ne0$ の $n-k+1$ 次多項式、根 $1/\rho_i$ はすべて実数です。$S$ を $n-k-1$ 回微分すると（各段の次数は $2$ 以上）、再び <Ref to="lem-real-rooted-derivative" /> により、根がすべて実数の多項式
$$
T(x)=\frac{(n-k+1)!}{2}\,c_{k-1}\,x^2+(n-k)!\,c_k\,x+(n-k-1)!\,c_{k+1}
$$
が残ります（$x^{n-j}$ の項のうち $j\le k+1$ のものだけが生き残る）。$c_{k-1}\ne0$ なので $T$ は 2 次式で、実根をもつので判別式は $0$ 以上です。$c_{k-1}=(k-1)!\,a_{k-1}$、$c_k=k!\,a_k$、$c_{k+1}=\frac{(k+1)!}2a_{k+1}$ を代入して整理すると
$$
\bigl(k!\,(n-k)!\,a_k\bigr)^2\ge(k-1)!\,(k+1)!\,(n-k+1)!\,(n-k-1)!\;a_{k-1}a_{k+1}
$$
で、両辺を $(k-1)!\,k!\,(n-k)!\,(n-k-1)!$ で割ると $k(n-k)\,a_k^2\ge(k+1)(n-k+1)\,a_{k-1}a_{k+1}$ です。これが主張の不等式です。

2: $P$ は $a_k\ge0$ で $P(x)>0$（$x>0$）なので正の根をもたず、$0$ でない根はすべて負です。$P=a_nx^\mu\prod_{i}(x+r_i)$（$r_i>0$）と書くと、$\prod_i(x+r_i)$ の係数は正の数 $r_i$ の基本対称式で、すべて正です。したがって $a_j>0$（$\mu\le j\le n$）、$a_j=0$（$j<\mu$）です。1 により $a_\mu,\dots,a_n$ は正の対数凹列なので、<Ref to="prop-logconcave-unimodal" /> から単峰で、前に $0$ が並ぶだけなので全体も単峰です。
</Proof>

<Corollary id="cor-binomial-unimodal" title="二項係数の単峰性">
$\binom n0,\binom n1,\dots,\binom nn$ は対数凹で単峰であり、$k=\lfloor n/2\rfloor$ で最大になる。
</Corollary>

<Proof of="cor-binomial-unimodal">
<Ref to="thm-binomial" /> により $\sum_k\binom nkx^k=(1+x)^n$ で、根は $-1$（$n$ 重根）のみ、係数は正です。<Ref to="thm-newton-unimodal" /> の 1 と 2 から対数凹で単峰です。左右対称（<Ref to="prop-pascal" />）なので、最大は中央、すなわち $k=\lfloor n/2\rfloor$（と $n-k$）でとります（頂点 $m$ が $m\le n/2$ なら、$m\le\lfloor n/2\rfloor\le n-m$ で、減少側の $\binom n{\lfloor n/2\rfloor}\ge\binom n{n-m}=\binom nm$ です。$m>n/2$ なら左右を入れ替える）。
</Proof>

<Example id="ex-stirling-unimodal" title="Stirling 数の単峰性">
符号なし第 1 種 Stirling 数 $c(n,m)$ の母関数は $\sum_mc(n,m)x^m=x(x+1)\cdots(x+n-1)$ で（[半順序集合と Möbius 反転](/mathematics/combinatorics/posets-mobius) の <Ref to="mathematics/combinatorics/posets-mobius#prop-stirling-first-gf" />）、根 $0,-1,\dots,-(n-1)$ はすべて実数です。したがって <Ref to="thm-newton-unimodal" /> により $c(n,1),\dots,c(n,n)$ は対数凹で単峰です。たとえば $n=4$ では $c(4,1),\dots,c(4,4)=6,11,6,1$ で、$11$ を頂点とする山形です。
</Example>

## 8. Ramsey 型の定理：van der Waerden の定理

鳩の巣原理の「構造つき」版が Ramsey 理論です。有限個の色で塗り分けたとき、必ずどこかに単色の整った構造が現れる、という形の定理で、その最初の例の一つが van der Waerden の定理です。以下、$k$ 項の**等差数列**とは、$a,a+d,\dots,a+(k-1)d$（$d\ge1$）の形の $k$ 個の整数のことです。$[N]$ の**$r$ 色塗り**は写像 $c:[N]\to\{1,\dots,r\}$ で、等差数列が**単色**であるとは、その全項で $c$ が同じ値をとることです。

<Theorem id="thm-van-der-waerden" title="van der Waerden の定理">
任意の正の整数 $k,r$ に対し、正の整数 $N=W(k,r)$ が存在して、$[N]=\{1,\dots,N\}$ のどんな $r$ 色塗りにも、単色の $k$ 項等差数列が含まれる。
</Theorem>

証明の全体像は次のとおりです。$k-1$ 項の場合を既知として $k$ 項の場合を示します。数直線を同じ長さのブロックに区切ると、ブロック内の色の並びが同じブロックが等間隔に並びます。その中で、$(k-1)$ 項の単色数列が、同じ「焦点」（$k$ 項目になるはずの位置）を指すように、色の違うものを一つずつ増やしていきます。色が $r$ 種類しかないので、$r$ 個そろったところで焦点の色が行き場を失い、$k$ 項の単色数列ができる、という流れです。

<Proof of="thm-van-der-waerden">
$k$ についての帰納法で、すべての $r$ に対して主張を示します。$k=1$ では $N=1$ です。$k=2$ では $N=r+1$ がよい：$r+1$ 個の数の色への写像は <Ref to="thm-pigeonhole" /> により単射でなく、同じ色の 2 数 $a<a'$ が $d=a'-a$ の 2 項等差数列をなします。

$k\ge3$ とし、$k-1$ について（すべての色数で）主張が成り立つと仮定して $W(k-1,r')$ を使います。$k,r$ を固定し、「色焦点」の概念を導入します。$[n]$ の $r$ 色塗り $c$ において、$s$ 個の $(k-1)$ 項等差数列 $(a_i,d_i)$（$1\le i\le s$、項は $a_i+jd_i$、$0\le j\le k-2$）が**焦点 $f$ をもつ色焦点列**であるとは、(a) 各数列が単色で、その色 $c_1,\dots,c_s$ が互いに異なり、(b) すべての $i$ で $a_i+(k-1)d_i=f$（共通の焦点）で、$f\le n$ であることをいう。

**主張.** 各 $s=1,\dots,r$ に対し、$n(s)$ が存在して、$[n(s)]$ の任意の $r$ 色塗りは、単色の $k$ 項等差数列を含むか、$s$ 個の色焦点列をもつ。

主張から定理が従います。$s=r$ として $N=n(r)$ とします。単色の $k$ 項等差数列がなければ、色の異なる $r$ 個の色焦点列があり、その色 $c_1,\dots,c_r$ は $r$ 色すべてです。焦点 $f$ の色は、ある $c_i$ と等しく、このとき $a_i,a_i+d_i,\dots,a_i+(k-1)d_i=f$ は単色の $k$ 項等差数列で矛盾です。

**主張の証明（$s$ についての帰納法）.** $s=1$：$n(1)=2W(k-1,r)$ とします。$[n(1)]$ の $r$ 色塗りの前半 $\{1,\dots,W(k-1,r)\}$ に、帰納法の仮定（$k-1$ について）から単色の $(k-1)$ 項等差数列 $(a,d)$ があり、$a+(k-2)d\le W(k-1,r)$ から $d\le W(k-1,r)$（$k-2\ge1$）、よって焦点 $a+(k-1)d\le2W(k-1,r)=n(1)$ です。これは 1 個の色焦点列です。

$s\to s+1$（$s<r$）：$m=n(s)$、$M=W(k-1,r^m)$ とし、$n(s+1)=2mM$ とします。$[2mM]$ の $r$ 色塗り $c$ を考え、これを長さ $m$ のブロック $B_t=\{(t-1)m+1,\dots,tm\}$（$1\le t\le2M$）に分けます。各ブロック $B_t$ の色の並び $\vartheta(t)=(c((t-1)m+1),\dots,c(tm))\in\{1,\dots,r\}^m$ は $r^m$ 通りで、$t\mapsto\vartheta(t)$ は $[M]$ の $r^m$ 色塗りです。$M=W(k-1,r^m)$ の定義により、$a+(k-2)d\le M$ を満たす $a,d\ge1$ で $\vartheta(a)=\vartheta(a+d)=\cdots=\vartheta(a+(k-2)d)$ となるものがあります。$d\le M$ に注意します。

ブロック $B_a$ を、位置 $1,\dots,m$ の $r$ 色塗りと見ます。帰納法の仮定（$s$ について）により、$B_a$ に単色の $k$ 項等差数列があれば終わりです。そうでなければ、$B_a$ に $s$ 個の色焦点列 $(x_i,e_i)$（位置で数える。色 $c_1,\dots,c_s$ は互いに異なり、共通の焦点位置 $f_0\le m$）があります。ブロック $B_{a+jd}$ は $B_a$ と同じ色の並びをもつので、各ブロックの同じ位置は同じ色です。

新しい $s+1$ 個の等差数列を定義します。$i\le s$ には、第 $j$ 項（$0\le j\le k-2$）を、ブロック $B_{a+jd}$ の位置 $x_i+je_i$ の数 $(a+jd-1)m+x_i+je_i$ とします。これは初項 $(a-1)m+x_i$、公差 $e_i+dm$ の等差数列で、全項の色は $c_i$ です。$i=s+1$ には、ブロック $B_{a+jd}$ の位置 $f_0$ の数 $(a+jd-1)m+f_0$ を第 $j$ 項とします。初項 $(a-1)m+f_0$、公差 $dm$ で、全項の色は $B_a$ の位置 $f_0$ の色 $c_0$ です。どの数列の第 $k-1$ 項（$j=k-1$）も、ブロック $B_{a+(k-1)d}$ の位置 $f_0$ の数 $f'=(a+(k-1)d-1)m+f_0$ で、焦点は共通です。$a+(k-1)d\le M+d\le2M$ なので $f'\le2mM=n(s+1)$ です。

色 $c_0$ は $c_1,\dots,c_s$ と異なります：$c_0=c_i$ なら、$B_a$ の中で $x_i+je_i$（$0\le j\le k-2$）と焦点位置 $f_0=x_i+(k-1)e_i$ はすべて色 $c_i$ で、単色の $k$ 項等差数列になり、場合分けの前提（$B_a$ には単色の $k$ 項等差数列がない）に反します。よって $s+1$ 個の色焦点列が得られました。
</Proof>

<Example id="ex-w32" title="W(3, 2) = 9">
$W(3,2)>8$：$[8]$ を赤赤青青赤赤青青と塗ると（赤は $\{1,2,5,6\}$、青は $\{3,4,7,8\}$）、どの色にも 3 項等差数列がありません。3 項等差数列 $a<b<c$ では $b=\frac{a+c}2$ なので $a+c$ は偶数で、赤の $\{1,2,5,6\}$ から和が偶数になる 2 数を選ぶと $(1,5)$ と $(2,6)$ だけで、中点 $3,4$ は赤ではありません。青の $\{3,4,7,8\}$ でも $(3,7)$、$(4,8)$ の中点 $5,6$ は青ではありません。

$W(3,2)\le9$：$[9]$ の 2 色塗りに単色の 3 項等差数列がないと仮定し、$5$ が赤とします。$4$ が赤なら、$(4,5,6)$ から $6$ は青、$(3,4,5)$ から $3$ は青、$(3,6,9)$ から $9$ は赤、$(1,5,9)$ から $1$ は青、$(1,2,3)$ から $2$ は赤、$(2,5,8)$ から $8$ は青、$(6,7,8)$ から $7$ は赤となり、$(5,7,9)$ がすべて赤で矛盾します。$6$ が赤の場合は、反転 $x\mapsto10-x$ で同じ議論です。したがって $4,6$ はどちらも青で、$(2,4,6)$ から $2$ は赤、$(4,6,8)$ から $8$ は赤となり、$(2,5,8)$ がすべて赤で矛盾します。
</Example>

<Corollary id="cor-vdw-infinite" title="自然数の有限彩色">
自然数全体 $\mathbb{N}$ を有限個の色で塗ると、ある色について、その色の数の集合は任意の長さの等差数列を含む。
</Corollary>

<Proof of="cor-vdw-infinite">
$r$ 色塗りとする。各 $k$ について、<Ref to="thm-van-der-waerden" /> を $[W(k,r)]$ に使うと、単色の $k$ 項等差数列があり、その色を $\gamma(k)\in\{1,\dots,r\}$ とする。$\gamma:\mathbb{N}\to\{1,\dots,r\}$ に <Ref to="thm-pigeonhole" /> の 2 を使うと、ある色 $\gamma_0$ について $\gamma(k)=\gamma_0$ となる $k$ が無限個ある。任意の長さ $L$ に対し、$\gamma(k)=\gamma_0$ となる $k\ge L$ を取ると、色 $\gamma_0$ の単色の $k$ 項等差数列の最初の $L$ 項は、色 $\gamma_0$ の $L$ 項等差数列である。よって色 $\gamma_0$ の数の集合は任意の長さの等差数列を含む。
</Proof>

van der Waerden 数 $W(k,r)$ の上界は、この証明の構成からは極端に大きく（Ackermann 関数程度）、Shelah による原始再帰的な評価、Gowers による塔型の評価が知られています。$W(3,2)=9$ のように値が決まっているのはごくわずかです。「密度が正の部分集合は単色でなくても等差数列を含む」という強い形が Szemerédi の定理です。

## 9. 演習

<Exercise id="exr-bell" difficulty="易">
<Ref to="thm-exp-formula" /> の証明中の漸化式から $B_{n+1}=\sum_{k=0}^n\binom nkB_k$ を導き、$B_5$ を求めよ。
<Solution>
Bell 数は全ての $c_k=1$ の場合なので、漸化式 $a_{n+1}=\sum_k\binom nkc_{k+1}a_{n-k}$ は $B_{n+1}=\sum_{k=0}^n\binom nkB_{n-k}=\sum_{k=0}^n\binom nkB_k$ です（$\binom nk=\binom n{n-k}$ による添字の入れ替え）。$B_0=1$ から順に $B_1=1$、$B_2=1+1=2$、$B_3=1+2\cdot1+2=5$、$B_4=1+3\cdot1+3\cdot2+5=15$、$B_5=1+4\cdot1+6\cdot2+4\cdot5+15=52$ です。
</Solution>
</Exercise>

<Exercise id="exr-ternary" difficulty="標準">
$f=x(1+f)^3$ を満たす $f$ の係数を求めよ。$[x^n]f=\frac1{2n+1}\binom{3n}n$ を示し、$n=3$ の値を計算せよ。
<Solution>
$\phi(t)=(1+t)^3$ として <Ref to="thm-lagrange" /> の 2（$k=1$）より $[x^n]f=\frac1n[t^{n-1}](1+t)^{3n}=\frac1n\binom{3n}{n-1}$ です。$\frac1n\binom{3n}{n-1}=\frac{(3n)!}{n\,(n-1)!\,(2n+1)!}=\frac{(3n)!}{n!\,(2n+1)!}=\frac1{2n+1}\binom{3n}n$ です。$n=3$ では $\frac17\binom93=\frac{84}7=12$ です。
</Solution>
</Exercise>

<Exercise id="exr-forests" difficulty="標準">
$[n]$ 上の根付き森の個数が $(n+1)^{n-1}$ であることを示せ。
<Solution>
<Ref to="thm-cayley" /> の証明で $A=\exp(T)$、$T=xA$ を示しました。よって $A=T/x$ で、$[x^n]A=[x^{n+1}]T=\frac{t_{n+1}}{(n+1)!}=\frac{(n+1)^n}{(n+1)!}$ です。したがって $a_n=n!\cdot\frac{(n+1)^n}{(n+1)!}=(n+1)^{n-1}$ です。$n=2$ では、辺なし（2 頂点がともに根）が 1 個、辺が 1 本で根が 2 通りなので合わせて $3$ 個で、確かに $(2+1)^{1}=3$ と一致します。
</Solution>
</Exercise>

<Exercise id="exr-fekete-super" difficulty="標準">
正の数列 $(a_n)$ が $a_{m+n}\ge a_ma_n$ を満たし、かつ $a_n\le C^n$（$C$ は定数）とする。このとき $\lim a_n^{1/n}=\sup a_n^{1/n}$ を示せ。さらに $d=2$ の格子動物について、$a_2=2$ と $a_4=19$ から得られる $\lambda_2$ の下界をそれぞれ求めよ。
<Solution>
$\alpha_n=-\log a_n$ は劣加法的なので <Ref to="lem-fekete" /> より $\alpha_n/n$ の極限が存在して $\inf$ に等しく、$a_n\le C^n$ より $\alpha_n/n\ge-\log C$ なので極限は有限です。符号と $\exp$ を戻せば結論が出ます。後半は $\lambda_2\ge a_n^{1/n}$ を使います。$a_2=2$ からは $\lambda_2\ge\sqrt2\approx1.41$、$a_4=19$ からは $\lambda_2\ge19^{1/4}\approx2.09$ です。$n$ を大きくするほど、より良い下界が得られます。
</Solution>
</Exercise>

<Exercise id="exr-pigeon-square" difficulty="易">
一辺 $1$ の正方形（周と内部）に 5 点をとると、そのうちの 2 点で距離が $\frac{\sqrt2}2$ 以下のものがあることを示せ。
<Solution>
正方形を一辺 $\frac12$ の 4 個の正方形（辺は共有してよい）に分け、各点を、それを含む小正方形（複数あれば 1 つ決めて）に振り分けます。5 点を 4 個に振り分ける写像は、<Ref to="thm-pigeonhole" /> の 1（$k=1$）により単射でないので、同じ小正方形に 2 点が入ります。小正方形の 2 点の距離は対角線の長さ $\frac{\sqrt2}2$ 以下です。
</Solution>
</Exercise>

<Exercise id="exr-newton-binomial" difficulty="標準">
$P(x)=(1+x)^n$ では <Ref to="thm-newton-unimodal" /> の 1 の不等式が、すべての $1\le k\le n-1$ で等号になることを示せ。
<Solution>
$\binom n{k-1}=\binom nk\frac k{n-k+1}$、$\binom n{k+1}=\binom nk\frac{n-k}{k+1}$ なので（<Ref to="prop-pascal" /> の閉じた式）、$\binom n{k-1}\binom n{k+1}=\binom nk^2\frac{k(n-k)}{(k+1)(n-k+1)}$ です。したがって $\binom nk^2=\bigl(1+\frac1k\bigr)\bigl(1+\frac1{n-k}\bigr)\binom n{k-1}\binom n{k+1}$ で、等号です。根が $-1$ の 1 点（$n$ 重根）に集中している場合、判別式が $0$ になっています。
</Solution>
</Exercise>

<Exercise id="exr-vdw-extend" difficulty="易">
<Ref to="ex-w32" /> の $[8]$ の塗り方（赤赤青青赤赤青青）に $9$ を赤または青で加えると、どちらの場合にも単色の 3 項等差数列ができることを、具体的な数列を挙げて確かめよ。
<Solution>
$9$ が赤なら、赤は $\{1,2,5,6,9\}$ で $(1,5,9)$ が公差 $4$ の単色等差数列です。$9$ が青なら、青は $\{3,4,7,8,9\}$ で $(7,8,9)$ が公差 $1$ の単色等差数列です。このことは $W(3,2)\le9$ の一部の確認にもなっていますが、他の塗り方では別の数列が現れます（<Ref to="ex-w32" /> の議論）。
</Solution>
</Exercise>

## 参考文献

- Richard P. Stanley, *Enumerative Combinatorics, Volume 1*, 2nd edition, Cambridge University Press, 2012 — 第 1 章（母関数）、第 5 章（指数型母関数）。
- Ronald L. Graham, Bruce L. Rothschild, Joel H. Spencer, *Ramsey Theory*, 2nd edition, Wiley, 1990 — 第 2 章（van der Waerden の定理）。
- B. L. van der Waerden, "Beweis einer Baudetschen Vermutung", *Nieuw Archief voor Wiskunde* 15 (1927), 212–216.
- Richard P. Stanley, "Log-concave and unimodal sequences in algebra, combinatorics, and geometry", *Annals of the New York Academy of Sciences* 576 (1989), 500–535.
- Herbert S. Wilf, *generatingfunctionology*, 3rd edition, A K Peters, 2006 — 第 1 章・第 2 章。
- Philippe Flajolet, Robert Sedgewick, *Analytic Combinatorics*, Cambridge University Press, 2009 — 第 I 部（記号的方法）。
- Martin Aigner, Günter M. Ziegler, *Proofs from THE BOOK* — 「Cayley の公式」の章。
- M. Fekete, "Über die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit ganzzahligen Koeffizienten", *Mathematische Zeitschrift* 17 (1923), 228–249.
- D. A. Klarner, "Cell growth problems", *Canadian Journal of Mathematics* 19 (1967), 851–863.