label付き連結成分分解・exponential formula

概要

最小ラベルを含む連結成分を一意に切り出し、全構造と連結な構造の個数を結び付ける。ラベル集合をサイズだけで扱えるなら指数型母関数へ、扱えないなら部分集合DPへ進む。

考え方

全体を直接数えにくくても、「一つの連結成分」と「残り」を独立に選べるなら、成分ごとの数え上げへ分解できる。ただし、どの成分を最初に選ぶか自由にすると同じ構造を何度も数えてしまう。最小ラベルを含む成分に固定すると、切り出す成分が一つに決まる。

以下では固定された nn 個のラベル上の全構造数を ana_n、連結な構造数を cnc_n とする。同じサイズならラベル集合によらず同じ個数であり、各構造が連結成分の集合へ一意に分かれ、成分間の制約なく合成できる場合を扱う。空構造は一通りなので a0=1a_0=1、空の連結成分は存在しないので c0=0c_0=0 とする。

最小ラベルのある成分を固定する

独自の小例として、ラベル {1,2,3}\{1,2,3\} 上の全単純無向グラフを数える。辺の候補は {1,2},{1,3},{2,3}\{1,2\},\{1,3\},\{2,3\} の三つで、それぞれ使うか使わないか選べるから a3=23=8a_3=2^3=8。連結にするには辺が2本以上必要であり、2本を選ぶ三通りと、3本すべてを使う一通りから c3=4c_3=4 となる。単頂点は辺がなくても連結なので c1=1c_1=1、二頂点ではその間の辺が必要なので c2=1c_2=1 である。

8個をラベル1の属する成分で分類する。その成分の頂点集合を TT、サイズを kk とすると、次の表になる。成分から外へ出る辺はすべて使わず、残りの頂点間の辺だけを自由に選ぶ。

kkTT の候補ckc_ka3−ka_{3-k}合計
1{1}\{1\}122
2{1,2}\{1,2\} または {1,3}\{1,3\}各1各12
3{1,2,3}\{1,2,3\}414

一行目では、残りの辺 {2,3}\{2,3\} を使っても使わなくてもよい。残り全体が連結である必要はないため、ここに使うのは c2=1c_2=1 でなく a2=2a_2=2 である。二行目では成分のラベル集合が二通りある。三行目の残りは空集合だが、何も作らない一通りとして a0=1a_0=1 を掛ける。こうして a3=2+2+4=8a_3=2+2+4=8 となり、逆に c3=8−2−2=4c_3=8-2-2=4 とも求められる。

一般に、ラベル1を含む成分のサイズを kk とすると、残りの k−1k-1 ラベルの選び方は (n−1k−1)\binom{n-1}{k-1} 通りである。その集合上で ckc_k 通りの成分を作り、残ったラベル上で an−ka_{n-k} 通りの構造を作るので、

an=∑k=1n(n−1k−1)ckan−ka_n=\sum_{k=1}^n\binom{n-1}{k-1}c_k a_{n-k}

を得る。各構造のラベル1の成分は一意であり、逆に選んだ成分と残りを合わせれば元の構造を復元できる。この対応により漏れも重複もない。小例のサイズ2の係数は (21)=2\binom{2}{1}=2 に当たる。

全構造数が先に分かる場合、k=nk=n の項が cna0=cnc_n a_0=c_n なので、

cn=an−∑k=1n−1(n−1k−1)ckan−kc_n=a_n-\sum_{k=1}^{n-1}\binom{n-1}{k-1}c_k a_{n-k}

として n=1,2,…n=1,2,\ldots の順に復元できる。

指数型生成関数とsubset再帰

このラベル分配を階乗で正規化すると、前単元のEGFの積へつながる。

A(x)=∑n≥0anxnn!,C(x)=∑n≥1cnxnn!A(x)=\sum_{n\geq 0}a_n\frac{x^n}{n!},\qquad C(x)=\sum_{n\geq 1}c_n\frac{x^n}{n!}

と置く。漸化式を (n−1)!(n-1)! で割ると、各項は ck/(k−1)!c_k/(k-1)! と an−k/(n−k)!a_{n-k}/(n-k)! の積になる。これは形式微分した級数の xn−1x^{n-1} 係数の比較であり、A′=C′AA'=C'A を表す。初期値 A(0)=1,C(0)=0A(0)=1,C(0)=0 と合わせて A=exp⁡CA=\exp C、逆に C=log⁡AC=\log A となる。

同じ式を成分の集合からも導ける。jj 個の成分を順序付きで並べるとEGFは C(x)jC(x)^j となる。それぞれの成分は非空で互いに異なるラベル集合を持つため、同じ成分集合に対応する並べ方はちょうど j!j! 通りある。順序を忘れて全成分数を足すと

A(x)=∑j≥0C(x)jj!=exp⁡C(x)A(x)=\sum_{j\geq 0}\frac{C(x)^j}{j!}=\exp C(x)

を得る。j=0j=0 の項は空構造の1である。

先ほどのグラフでは、低次の項は

C(x)=x+x22!+4x33!+O(x4)C(x)=x+\frac{x^2}{2!}+4\frac{x^3}{3!}+O(x^4)

となる。x3x^3 へ寄与するのは成分数1、2、3の項だけである。2成分の場合、サイズ1と2を並べる順序は二通りある。従って [x3]C(x)2=2⋅1⋅(1/2!)=1[x^3]C(x)^2=2\cdot 1\cdot(1/2!)=1 となり、順序を忘れるため 2!2! で割ると 1/21/2 を得る。三つの成分数からの寄与を足すと、

[x3]exp⁡C(x)=43!+12!+13!=23+12+16=43.\begin{aligned} [x^3]\exp C(x) &=\frac{4}{3!}+\frac{1}{2!}+\frac{1}{3!}\\ &=\frac{2}{3}+\frac{1}{2}+\frac{1}{6}=\frac{4}{3}. \end{aligned}

これは通常の係数であり、個数へ戻すには 3!3! を掛ける。各項はそれぞれ、連結グラフ4個、辺が1本だけのグラフ3個、辺のないグラフ1個に対応し、合計は 3!⋅(4/3)=83!\cdot(4/3)=8 となる。ここでの分類は成分数による 4+3+14+3+1 であり、前の表のラベル1の成分サイズによる 2+2+42+2+4 とは分類の軸が違う。同じ8個を二通りの一意な分解で数えている。

成分数を変数 uu の次数でも記録すれば A(x,u)=exp⁡(uC(x))A(x,u)=\exp(uC(x))、成分数がちょうど jj の構造のEGFは C(x)j/j!C(x)^j/j! である。個数を取り出すときは、ここでも n![xn]n![x^n] を使う。

一方、使える辺がラベルごとに違うと、サイズだけでは情報を失う。例えば、辺を {1,2},{2,3}\{1,2\},\{2,3\} だけに制限したパスの部分グラフを考える。同じ二頂点集合でも、{1,2}\{1,2\} 上の連結グラフは1個、{1,3}\{1,3\} 上では0個であり、全グラフ数もそれぞれ2個と1個になる。サイズ2の共通の値 c2,a2c_2,a_2 は定められない。

この場合は、頂点集合そのものを状態に持つ。集合 SS 上の全構造数を a[S]a[S]、連結構造数を c[S]c[S] とする。a[∅]=1,c[∅]=0a[\emptyset]=1,c[\emptyset]=0 とし、非空集合について

a[S]=∑T⊆Smin⁡(S)∈Tc[T]a[S∖T]a[S]=\sum_{\substack{T\subseteq S\\ \min(S)\in T}} c[T]a[S\setminus T]

と分解する。二項係数でラベル集合の選択をまとめる代わりに、各 TT を直接列挙して、それぞれの内部構造数を使う。パスの全体集合では、ラベル1の成分が {1},{1,2},{1,3},{1,2,3}\{1\},\{1,2\},\{1,3\},\{1,2,3\} となる場合が順に 2,1,0,12,1,0,1 通りなので、合計は 4=224=2^2 となる。

a[S]a[S] が既知なら、T=ST=S の項を移して c[S]c[S] を求める。真部分集合の値だけを参照するので、集合サイズの昇順で計算すればよい。ABC213 Gでは、入力グラフで使える辺が頂点集合ごとに違うため、この部分集合DPが必要になる。

符号付きの連結グラフへ特殊化する

上の分解は個数だけでなく、成分ごとに積となる重み和にも使える。単純グラフの重みを (−1)辺数(-1)^{\text{辺数}} とすると、全グラフの重み和 ana_n は a0=a1=1a_0=a_1=1、n≥2n\geq 2 では0になる。一つの辺の候補を固定し、その有無を反転すると、グラフが逆符号の対になって相殺するためである。

連結グラフの符号和を h(n)h(n) とすれば、最小ラベルの成分を固定した式は、n≥2n\geq 2 について

0=∑k=1n(n−1k−1)h(k)an−k0=\sum_{k=1}^n\binom{n-1}{k-1}h(k)a_{n-k}

となる。補集合サイズが2以上の項は消え、0=h(n)+(n−1)h(n−1)0=h(n)+(n-1)h(n-1) だけが残る。h(1)=1h(1)=1 から

h(n)=(−1)n−1(n−1)!h(n)=(-1)^{n-1}(n-1)!

を得る。

ABC236 Exでは、等値条件として選んだ辺の成分 TT ごとに、共通値を g(T)g(T) 通り選べる。そこで c[T]=g(T)h(∣T∣)c[T]=g(T)h(|T|) を集合分割の重みとして使う。空分割の重みを dp[∅]=1dp[\emptyset]=1 とし、非空集合では最小ラベルを含む T⊆ST\subseteq S を列挙して

dp[S]=∑T⊆Smin⁡(S)∈Tc[T]dp[S∖T]dp[S]=\sum_{\substack{T\subseteq S\\ \min(S)\in T}} c[T]dp[S\setminus T]

とする。T=ST=S も含めるので、全体が一成分の項も空集合の基底から生成できる。成分内部の相殺を導くことと、分割を重複なく合成することは別々に確認する。

成立条件と計算量

サイズだけの漸化式は、必要な二項係数と全構造数が得られていれば、次数 NN まで O(N2)O(N^2) 時間で計算できる。二項係数を表で前計算する場合は、その構築も O(N2)O(N^2) 時間・空間である。階乗と逆階乗を使える場合は、係数を必要時に求め、配列を O(N)O(N) 空間にできる。

部分集合の再帰をすべての SS について直接評価すると、O(3N)O(3^N) 時間・O(2N)O(2^N) 空間になる。各ラベルの所属は「TT 内・S∖TS\setminus T 内・SS 外」の三通りであり、最小ラベルの制限を付けてもこの上界に収まる。いずれも ana_n や a[S]a[S]、成分重みを用意する費用は別途加える。exp⁡,log⁡\exp,\log で高速化する場合の費用はFPS演算に依存する。

EGFによる計算では階乗や整数による除算が必要なので、素数法 pp なら必要な次数が pp 未満か確認する。n!n! が可逆でない法でも、二項係数を用いた整数の漸化式自体は成立する。空集合は一通りの構造として扱う一方、連結成分にはしない。

また、成分間の辺・順序・相互制約を別に選ぶ必要がある場合は、A=exp⁡CA=\exp C をそのまま使えない。グラフの例では異なる成分間の辺はすべて「使わない」と一意に決まっていた。成分数制約なら uu を追加するように、何を独立に選べるのかを先に確認する。復習では、最小ラベルで切り出す成分を一意にし、同サイズのラベル集合を同じ個数として扱えるか確かめることを核にする。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 黄色(2000–2399)。根を含む成分や成分集合の一意な分解から、指数型母関数やsubset再帰を立てる。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 組合せ・多項式・線形代数。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-labeled-component-decomposition

label付き連結成分分解・exponential formula

習得する技能

  • 最小labelを含む成分を一意に切り出し、全構造とconnected構造の関係をsubset DPまたは指数型母関数で解ける。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: 組合せを生成関数へ符号化する。

このUnitを直接前提とする単元: なし。

生成関数による組合せ構造の符号化で得た考え方と実装を再利用し、label付き連結成分分解・exponential formulaの発動条件・正当化・境界を重複なく学ぶ。

このUnitでは扱わないもの

  • label付き連結成分分解・exponential formulaの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠

3ラベル上の全単純グラフの分類、EGFの低次展開、パスとの比較は本単元の独自例である。部分集合による成分分解はABC213 G、符号和の利用はABC236 Exの公式解説と照合した。