組合せを生成関数へ符号化する

概要

生成関数による組合せ構造の符号化

組合せの和・積、順序付きの列、集合、巡回順序などを係数列の演算へ翻訳し、欲しい個数を係数として抽出する。

まず組合せ構造を和・積へ翻訳し、何の係数を求めるのかを定める。ABC385 Gなどの局所多項式の積はこの基本操作の例である。得られた式が暗黙方程式や巨大な積なら、高度な係数抽出の節で、式から計算可能な係数列を取り出す。

考え方

先に「サイズ」と「同じ構造とみなす条件」を決める。サイズ nn の構造数を ana_n とすると、通常型生成関数(OGF)は

A(x)=∑n≥0anxnA(x)=\sum_{n\geq 0}a_nx^n

である。xx はサイズを記録する記号で、[xn]A(x)[x^n]A(x) は xnx^n の係数を表す。係数が個数、次数がサイズという役割を分けて読む。

和・積・列から式を作る

サイズ1の部品とサイズ2の部品が一つずつあり、それぞれを使うか使わないか選ぶ独自の小例を考える。サイズ1側の選択肢は 1+x1+x、サイズ2側は 1+x21+x^2 で表せる。定数項の1は「使わない一通り」、残りの項は「使う一通り」である。両側の選択を組み合わせるには、各因子から一項ずつ選んで掛ける。

(1+x)(1+x2)=1+x+x2+x3(1+x)(1+x^2)=1+x+x^2+x^3

右辺の四項は、何も使わない、サイズ1だけ、サイズ2だけ、両方を使う選択に対応する。例えば x⋅x2=x3x\cdot x^2=x^3 は、部品を二つ選んで合計サイズが3になることを表す。次数は部品数ではなく、先に定めたサイズの合計である。[x3](1+x)(1+x2)=1[x^3](1+x)(1+x^2)=1 なので、合計サイズ3の選び方は一通りと読める。

一般に、互いに重ならない選択肢の集まりのどちらかから選ぶなら、生成関数は A(x)+B(x)A(x)+B(x) となる。A側の構造とB側の構造を一つずつ選び、どちら側から選んだかを保った組を作るなら、サイズを足すので A(x)B(x)A(x)B(x) となる。両側のサイズ別個数を ai,bja_i,b_j とすると、合計サイズ nn の個数は

[xn](A(x)B(x))=∑i=0naibn−i[x^n](A(x)B(x))=\sum_{i=0}^n a_i b_{n-i}

である。この係数の畳み込みは、A側のサイズ ii で場合分けしてから、両側を独立に選ぶ操作に対応する。

空でない部品を順番に並べる列も同様に扱える。部品の生成関数を A(x)A(x) とすると、部品数が kk の列は A(x)kA(x)^k、空列も許せば

SEQ⁡(A)=∑k≥0A(x)k=11−A(x)\operatorname{SEQ}(A)=\sum_{k\geq 0}A(x)^k=\frac{1}{1-A(x)}

となる。ここで A(0)=0A(0)=0 が必要で、サイズ nn へ寄与する部品数は高々 nn となる。この条件がないと、サイズ0の部品を何個でも挿入でき、係数が有限の個数にならない。

この逆数は「同じ集まりから部品を任意個、順序付きで選ぶ」という構造を表す。一方、1/(1−xs)1/(1-x^s) はサイズ ss の一種類の部品を0個以上選ぶ構造である。サイズ ss の種類数が asa_s で、種類ごとの個数を独立に選べる非ラベル付き多重集合なら、生成関数は ∏s≥1(1−xs)−as\prod_{s\geq 1}(1-x^s)^{-a_s} となる。集合を常に指数関数へ写せるわけではない。

ラベルがあると積の意味が変わる

同じ小例で、今度は使った部品に異なるラベルを分配する。サイズ1の部品は一つのラベルを受け取り、サイズ2の部品は二つのラベルを順序なしで受け取るものとする。どのラベル集合を渡しても、各部品の内部構造は一通りである。

両方を使ってラベル {1,2,3}\{1,2,3\} を分配する場合、サイズ1側へ渡すラベルを選ぶ必要がある。両側のラベル集合の組は

({1},{2,3}),({2},{1,3}),({3},{1,2})(\{1\},\{2,3\}),\quad (\{2\},\{1,3\}),\quad (\{3\},\{1,2\})

の三通りとなる。先ほどの合計サイズ3の選び方一通りに、ラベル分配の (31)=3\binom{3}{1}=3 が加わった。

一般にも、固定された nn 個の異なるラベルをA側の ii 個とB側の n−in-i 個へ分けるなら、組の個数は

cn=∑i=0n(ni)aibn−ic_n=\sum_{i=0}^n\binom{n}{i}a_i b_{n-i}

となる。ここで ai,bn−ia_i,b_{n-i} は、それぞれ固定されたラベル集合上の構造数であり、ラベル集合の選択をまだ含まない。同じサイズならどのラベル集合でも同じ個数になることを前提としている。

この二項係数を級数の積で自然に扱うため、指数型生成関数(EGF)では個数を階乗で正規化し、ここからは A(x)=∑n≥0anxn/n!A(x)=\sum_{n\geq 0}a_nx^n/n! と定める。B側も同様に定めると、

n![xn](A(x)B(x))=∑i=0nn!i!(n−i)!aibn−i=cnn![x^n](A(x)B(x)) =\sum_{i=0}^n\frac{n!}{i!(n-i)!}a_i b_{n-i} =c_n

となる。小例では A(x)=1+xA(x)=1+x、B(x)=1+x2/2!B(x)=1+x^2/2! なので、x3x^3 の通常の係数は 1/21/2 である。求めたい個数へ戻すと

3![x3](1+x)(1+x22!)=3!⋅12!=33![x^3](1+x)\left(1+\frac{x^2}{2!}\right) =3!\cdot\frac{1}{2!}=3

となり、ラベル分配を直接列挙した結果に一致する。EGFの係数 an/n!a_n/n! は個数そのものではない。これはラベルを忘れた構造数でもなく、個数を取り出すには n!n! を掛ける。

非空のラベル付き部品の集合は SET⁡(A)=exp⁡A\operatorname{SET}(A)=\exp A、巡回順序を持つ部品列は CYC⁡(A)=∑k≥1Ak/k=−log⁡(1−A)\operatorname{CYC}(A)=\sum_{k\geq 1}A^k/k=-\log(1-A) となる。前者は部品の並べ替え k!k! を、後者は kk 通りの巡回開始位置を除く。ラベル集合が互いに素で部品が非空だから、これらの作用は重複なく割れる。ラベル付き連結成分分解では、3ラベル上のグラフを使い、成分の集合が exp⁡\exp に対応する理由を確かめる。

成立条件と計算量

形式級数は解析的な収束を必要としない。求める次数の上限を NN とすると、xN+1x^{N+1} 以上を捨てて計算すればよい。ただし級数の逆数には定数項の可逆性、EGFや exp⁡,log⁡\exp,\log には 1,…,N1,\ldots,N および階乗による除算が必要になる。素数法 pp なら N<pN<p を確認する。

二つの係数列の積を次数 NN まで直接求める費用は O(N2)O(N^2) 時間・O(N)O(N) 空間である。因子が多数あれば、その合成回数も全体の費用へ含める。ここでは構造の符号化を先に学び、高速な積・逆元・指数関数の計算は後続の畳み込み・FPS単元へ進む。最後に、答えが [xN]A(x)[x^N]A(x) なのか N![xN]A(x)N![x^N]A(x) なのかを構造の定義へ戻って確認する。ABC422 Gの二つの問題では、ボールを区別するかどうかによってこの違いが現れる。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 黄色(2000–2399)。組合せ構造の和・積を係数列の演算へ写し、求める係数を定める。

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

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

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-generating-functions

習得する技能

  • 組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。

前提と範囲

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

直接の前提単元: 組合せ係数と対称性で数える。

このUnitを直接前提とする単元: Bostan–Mori・有理生成関数の係数抽出、FPS基本演算と多項式の多点評価を行う、母関数方程式・高度な係数抽出、label付き連結成分分解・exponential formula。

高速畳み込みを前提にせず、係数の意味を定義して和・積・sequence・set・cycleが表す組合せ構造を欲しい係数へ翻訳する。

このUnitでは扱わないもの

  • 係数列同士を単に畳み込む相互相関、および係数の組合せ的意味を持たない信号処理。

根拠

部品選択と3ラベルへの分配の小例は、本単元のための独自例である。和・積とOGF/EGFの対応は、以下の公式解説と照合した。