ISEGORIA / 数学百科事典
組合せ論：組み立てて数える
二つの集まりが同じ大きさであることを示す最もすっきりした方法は、一方を他方へ一つずつ作り替えることです。奇数の部分への分割は、等しい部分を合わせることで相異なる部分への分割になります。上りと下りの歩みでできた山並みは木になり、さらに三角形分割した多角形になります。そして個数を母関数に詰め込めば、複素平面でその関数に最も近い特異点が、個数の増え方を教えてくれます。
前提知識: 初歩的な数え上げ、数論、べき級数
予想してから操作し、計算例と問いで理解を確かめてください。グラフは数式の図示であり、証明ではありません。
1. 奇数の部分と相異なる部分
n の分割とは、順序を無視して n を正の整数の和に書くことです。オイラーは、n の奇数の部分への分割と相異なる部分への分割がちょうど同じ数だけあることを証明しました。n = 6 では、5+1、3+3、3+1+1+1、1+1+1+1+1+1 と、6、5+1、4+2、3+2+1 がそれぞれ四つずつあります。グレイシャーの全単射はこれを目に見える形にします。奇数の部分への分割をとり、等しい部分が二つあればそれを長さが二倍の一つの部分に合わせます。合わせても和も行の奇数の部分も変わらないので、最後は相異なる部分への分割に行き着き、そこでは各奇数 o がその個数を 2 のべきに分けています。再生を押して合併を見て、スライダーで分割を順に選び、個数のグラフで n をドラッグしてください。
計算例. \(n=12\) と奇数への分割 \(3+3+3+1+1+1\) をとります。1 が二つ合わさって 2 になり \(3+3+3+2+1\)、3 が二つ合わさって 6 になり \(6+3+2+1\) となって、部分は相異なります。二進法で見ると、三つの 3 は \(3=2+1\) 個、つまり \(3\cdot2+3\cdot1\) に、三つの 1 は \(1\cdot2+1\cdot1\) になりました。逆に読むと \(6=3\cdot2^1\) は二つの 3 に、\(2=1\cdot2^1\) は二つの 1 に分かれ、最初に戻ります。12 の分割はどちらの種類も 15 個あり、分割全体では \(p(12)=77\) 個です。
注意点. 等しい部分を合わせる順序は結果に影響しません。どの順序でも各奇数の個数は最後に二進法で書かれ、二進展開は一通りだからです。そもそもこの手続きが関数になるのはそのためです。式の行にある母関数による証明は短いですが、説明する内容は少なく、全単射はどの分割がどの分割に移るかを教えてくれます。個数のグラフが 24 で止まっているのは、それより大きな n ですべての分割を並べると遅いからで、何かが変わるからではありません。
なぜ相異なる部分への分割はどれも、ちょうど一つの奇数の部分への分割から来るのですか？
正の整数はどれも、\(o\) を奇数として \(o\cdot2^j\) と一通りに書けます。相異なる部分 \(o\cdot2^j\) をそれぞれ \(2^j\) 個の \(o\) に分けると、和が同じ奇数の部分への分割が得られます。それを合わせ直すと元の相異なる部分に戻ります。同じ奇数の類の中で相異なる 2 のべきは、ちょうど個数の二進法の各桁だからです。互いに打ち消し合う二つの写像は全単射です。
2. そろって動くカタラン対象
カタラン数 1, 1, 2, 5, 14, 42, 132, 429 は二百種類を超える対象を数えますが、その理由はいつも、同じ種類の二つの小さな対象への分解です。ディック経路は、上り n 回と下り n 回からなり、出発点より下へ決して行かない歩みです。軸へ最初に戻る所で U A D B と分かれ、A と B はより小さなディック経路です。A を根の左部分木、B を右部分木にすると、経路は節点が n 個の二分木になります。n + 2 個の角をもつ多角形の底辺に三角形を立て、その左の辺に左部分木の三角形分割を、右の辺に右部分木の三角形分割を置くと、木は三角形分割になります。n を選び、対象を順にたどり、対応する組を選んで、三つの中の同じ部品を見てください。
計算例. \(n=3\) ではディック経路は \(\binom63-\binom64=20-15=5\) 本で、UDUDUD、UDUUDD、UUDDUD、UUDUDD、UUUDDD です。UUDUDD をとると、最後の歩みで初めて軸に戻るので U A D の形で、\(A=\) UDUD、\(B\) は空です。したがって根には左部分木だけがあり、それは右の子をもつ節点です。頂点 0 から 4 の五角形では、根の三角形が辺 (0, 4) の上に頂点 3 で立ち、左部分木が四角形 0, 1, 2, 3 を三角形 (0, 1, 3) と (1, 2, 3) で埋め、対角線は 0–3 と 1–3 です。
注意点. カタラン族どうしの全単射は数多くあり、すべてが一致するわけではありません。ここでの全単射は最初の帰還による分解から作っているので、根の三角形は最初の上りとそれに対応する下りに当たります。たとえば最後の帰還を使う別の約束では、数は同じでも対象の組み合わせ方が変わります。折り返しによる数え方は、高さ 0 で始まり 0 で終わる経路を前提にしています。
なぜ折り返しの技法で、悪い経路の数が C(2n, n+1) になるのですか？
悪い経路は、ある歩みで初めて高さ \(-1\) に触れます。その歩みより後をすべて折り返し、上りと下りを入れ替えます。すると経路は 0 ではなく \(-2\) で終わり、上りが \(n-1\) 回、下りが \(n+1\) 回になります。そのような歩数の経路はどれも \(-1\) を横切るはずで、最初に触れた後を折り返し直すと元に戻るので、悪い経路と下りが \(n+1\) 回の経路は一対一に対応し、後者は \(\binom{2n}{n+1}\) 本あります。
3. 特異点が増え方を予言する
数列をべき級数 A(z) = Σ aₙ zⁿ に詰め込みます。この級数は、最も近い特異点までの距離を半径 ρ とする円板の内側で収束するので、係数は (1/ρ)ⁿ のように増えます。そして特異点の型が補正を決めます。単純極なら定数、平方根型の分岐点なら n^{−3/2} です。これが特異点解析で、複素平面上の関数の図を数え上げの公式に変えます。左の図は各 z を A(z) の偏角で色づけし、絶対値の 2 のべきごとに縞を入れているので、極や分岐点はすべての色が集まる場所として目立ちます。数列を選び、n をドラッグして本当の係数と予言を比べてください。
計算例. カタラン数では \(C(z)=(1-\sqrt{1-4z})/2z\) で、最も近い特異点は分岐点 \(z=1/4\) です。そこで \(C(z)=2-2\sqrt{1-4z}+O(1-4z)\) です。\(\alpha=-1/2\)、\(c=-2\)、\(\Gamma(-1/2)=-2\sqrt\pi\) なので \(C_n\sim4^n/(\sqrt\pi\,n^{3/2})\) です。\(n=10\) ではこれは 18 708 を予言し、本当の値は \(C_{10}=16\,796\) で比は 0.898 です。\(n=100\) では比は 0.9889 で、次の次数の見積もり \(1-9/8n\) に近い値です。
注意点. 移行定理には最も近い特異点だけでは足りません。関数が \(\rho\) の近く以外では円の少し外まで、いわゆるデルタ領域に延長できなければならず、円周上の特異点はすべて寄与します。分割数はこれをまったく満たしません。その母関数は単位円全体を自然境界としてもつからで、漸近形は代わりに鞍点法から得られます。代数関数の色の図は平方根の主値を使っているので、描かれた切断は約束事であり、関数そのものの一部ではありません。
なぜ完全順列の割合は、カタラン数の比よりもずっと速く収束するのですか？
\(e^{-z}/(1-z)\) には 1 での単純極しかないからです。\(e^{-1}/(1-z)\) を引くと整関数が残り、その係数はどんな幾何級数的な速さよりも速く縮むので、\(D_n/n!-1/e\) はおよそ \(1/(n+1)!\) です。カタラン数の関数は分岐点をもち、その展開 \((1-4z)^{1/2},(1-4z)^{3/2},\dots\) は \(1/n\) のべきの補正を与え、それはゆっくりとしか消えません。