ラグランジュ反転公式の組合せ論からの導出

こんにちは。こめだわらと申します。普段は競技プログラミングをやっています。

皆さんは、(形式的冪級数における) ラグランジュの反転公式 というものをご存じでしょうか。競プロの数え上げ問題にもよく使われる、非常に強力な公式です。代表的な使用例は ABC 222-H などです。 https://atcoder.jp/contests/abc222/tasks/abc222_h

この公式の証明は、形式留数を用いたものがよく知られているようです(上述のABCの公式解説もその一つです)。しかし私は、この証明があまり直感的に納得できませんでした。そこでGeminiに相談してみると、形式留数などの操作を経由せず、組合せ論からアプローチする方法を紹介されました。それが個人的にはかなり直感的な導出・証明に感じたので、本記事で紹介しようと思います。似たような境遇の方の理解の助けになれば幸いです。

ラグランジュの反転公式とは

形式的冪級数におけるラグランジュの反転公式とは、以下のような主張です。

【定理】

$F (x), G (x)$ を、逆関数の関係にあるFPSとする(すなわち、 $F (G (x)) = x, G (F (x)) = x$ が成り立つ)。このとき、以下の等式が成り立つ。
$[x^{n}] F (x) = \frac{1}{n} [x^{n - 1}] (\frac{x}{G ( x )})^{n}$

これを証明していくのですが、このままの形では少し扱いづらいので、少々変形を行います。

まず、 $G (x)$ の定数項は $0$ であり、 $1$ 次の項は $0$ ではありません(この条件を満たさない場合、逆関数が存在しません)。したがって、 $\frac{x}{G ( x )} = \frac{1}{\frac{G ( x )}{x}}$ の分母は定数項が $0$ でないFPSであるので、 $\frac{x}{G ( x )}$ はFPSとなります。これにより $\frac{x}{G ( x )} = Φ (x)$ とおくことができます。変形すると、結局ラグランジュの反転公式を示すには、以下の主張を示せば十分であることになります。

【主張】

$F (x), Φ (x)$ をFPSとし、次の等式を満たしているとする。
$F (x) = x Φ (F (x))$
このとき、以下の等式が成り立つ。
$[x^{n}] F (x) = \frac{1}{n} [x^{n - 1}] Φ (x)^{n}$

ラグランジュの反転公式をこの形で覚えている人も多いかもしれません。以降はこれを示すことを目標にします。

別の問題への言い換え

突然ですが、次の問題を考えます。

【問題1】

無限数列 $A = (A_{0}, A_{1}, A_{2}, \dots)$ がある。根付き木であって、各頂点の子供に左から順番がついているようなものを考える。根付き木 $T$ の スコア $S (T)$ を、以下のように定める。

根付き木の根を $r$ とする。 $r$ の子の個数を $c$ とし、 $r$ の子を左から順に $v_{1}, v_{2}, \dots, v_{c}$ とする。頂点 $v_{i}$ を根とする部分木を $T_{i}$ として、以下の式により $S (T)$ を定義する。

$S (T) := A_{c} i = 1 \prod c S (T_{i})$
正整数 $N$ が与えられる。 $N$ 頂点の根付き木全てに対するスコアの総和を求めよ。

この問題を解いてみましょう。問題の答えの母関数を $F (x)$ とします。 $F$ が満たすべき特徴を考えましょう。根の子の個数 $c$ により場合分けをすると、以下の等式が成り立つことが分かります。

F (x) = x c = 0 \sum \infty A_{c} F (x)^{c}

ここで、 $Φ (x) = \sum_{c = 0}^{\infty} A_{c} x^{c}$ とおくと、

F (x) = x Φ (F (x))

となります。上のほうで見た式が現れましたね。この問題の答えは $[x^{N}] F (x)$ だったので、この値を求めれば答えが求まります。この類の問題はラグランジュの反転公式の例題のような問題で、この形から今までの変形を逆走し、ラグランジュの反転公式を適用して答えを求める、というのが典型の流れです。

この問題において、数列 $A$ には特に制限を設けておらず、したがって $Φ$ は任意のFPSをとることができます。また、 $F$ は $Φ$ との関係式から一意に定まります。したがって、この問題の答えが $\frac{1}{N} [x^{N - 1}] Φ (x)^{N}$ に等しいことを示せれば、それでラグランジュの反転公式が示せたことになります。

実際に解いていく

では、上の問題を解いていきましょう。

まず、根付き木 $T$ のスコアについてもう少し考えます。定義式では、根の子を親とする部分木のスコアから再帰的に定義されていましたが、よく見てみると再帰的な定義は全く必要ないことが分かります。具体的には、木 $T$ の頂点 $v$ の子の数を $c_{v}$ とすると、 $S (T)$ は以下のようになっていることが分かります。

S (T) = v は T の頂点 \prod A_{c_{v}}

つまり、各頂点の子の個数だけに着目すれば、 $T$ のスコアが求まります。

ここで、 $N$ 頂点の根付き木 $T$ に対して、長さ $N$ の非負整数列 $C$ を以下の手順により生成します。

根から DFS を行う。頂点の子が複数ある場合、訪れたことがない子のうち最も左にあるものに優先的に訪れることにする。頂点を行きがけ順に並べた列 $(v_{1}, v_{2} \dots, v_{N})$ に対し、整数列 $C$ を $C = (c_{v_{1}}, c_{v_{2}}, \dots, c_{v_{N}})$ とする。

子の数の合計は $N - 1$ なので、 $C$ の総和は $N - 1$ です。またもう一つの条件として、 $1 \leq j \leq N - 1$ に対して $\sum_{i = 1}^{j} C_{i} \geq j$ が成り立っています。逆に、これら $2$ つの条件を満たす整数列 $C$ に対し、 $C$ を生成する木 $T$ を一意に復元できます(DFS順に子の数を決めていけばよいです)。木 $T$ が数列 $C$ を生成するとき、木 $T$ のスコアは $\prod_{i = 1}^{N} A_{C_{i}}$ であるので、結局元の問題は、以下の問題を解けばよいことになります。

【問題2】

以下の $2$ つの条件を満たす長さ $N$ の非負整数列 $C$ を いい整数列 と呼ぶ。

$\sum_{i = 1}^{N} C_{i} = N - 1$

$\sum_{i = 1}^{j} C_{i} \geq j (1 \leq j \leq N - 1)$

全てのいい整数列に対する $\prod_{i = 1}^{N} A_{C_{i}}$ の総和を求めよ。

もし $2$ つ目の条件がなければ話は簡単で、答えは $[x^{N - 1}] Φ (x)^{N}$ です。ここから、 $2$ つ目の条件を処理します。

Cycle Lemma の利用

ちょうど最近、 AtCoder Algorithm Lectures でも紹介されていたテクニックです。 Cycle Lemma とは、以下のような主張です。AtCoder Algorithm Lectures のものを引用します。(本記事を書いている途中で気づきましたが、この記事でラグランジュの反転公式の組合せ論からの導出について軽く触れられています。) https://info.atcoder.jp/entry/algorithm_lectures/cycle_lemma

【定理】

整数列 $A = (A_{0}, A_{1}, \dots, A_{N - 1})$ が、以下の条件を満たすとする。

任意の $i$ について $A_{i} \leq 1$

総和を $K$ とすると、 $K$ は非負である。

このとき、 $A$ の巡回シフトであって、累積和が初項を除きすべて正であるものが、ちょうど $K$ 個存在する。ただし、巡回シフトについては、要素のインデックスを区別する。

この主張の証明や具体例などは引用元の記事を参照するとよいです。今回はこの定理を使います。

数列 $D$ を、 $D_{i} = 1 - C_{N + 1 - i}$ によって定めます。数列 $C$ における $2$ つの条件を $D$ の条件に書き直します。

$1$ つ目の総和に関する条件は、 $\sum_{i = 1}^{N} D_{i} = 1$ となります。

$2$ つ目の条件は、以下のように変形できます。

i = 1 \sum j (1 - C_{i}) \leq 0

i = 1 \sum j D_{N + 1 - i} \leq 0

i = N + 1 - j \sum N D_{i} \leq 0

$1$ つ目の条件と合わせると、

i = 1 \sum N D_{i} - i = N + 1 - j \sum N D_{i} \geq 1

i = 1 \sum N - j D_{i} \geq 1

よって、 $\sum_{i = 1}^{j} D_{i} \geq 1 (1 \leq j \leq N)$ となります。明らかに $D_{i} \leq 1$ であるため、これで定理を適用できる形になりました。定理により、 $D$ の巡回シフトであって、上の $2$ つの条件を満たすものがちょうど $1$ つあり、元の数列 $C$ にも同じことが言えます。

まとめると、 $\sum_{i = 1}^{N} C_{i} = N - 1$ を満たす整数列 $C$ について、互いに巡回シフトして重なるもののうちちょうど $\frac{1}{N}$ だけが、いい整数列となることが分かりました。互いにシフトして重なる数列について $\prod_{i = 1}^{N} A_{C_{i}}$ は等しいので、結局答えを求めるには、 $1$ つ目の条件を満たすもの全体の結果を $\frac{1}{N}$ 倍すればよいです。よって答えは $\frac{1}{N} [x^{N - 1}] Φ (x)^{N}$ となります。

結論

言い換え後の問題1について、答え $[x^{n}] F (x)$ を別の形で表すことに成功しました。したがって、等式

[x^{N}] F (x) = \frac{1}{N} [x^{N - 1}] Φ (x)^{N}

が成り立ちます。以上でラグランジュの反転公式が証明されました。

余談

余談その1:FPS係数の元について

今回の証明において、 $F$ や $Φ$ の係数の元は明示的に示していませんでした。係数について利用した性質は、「可換環であること」「 $N$ で割れること」です。したがって、体上の代数、例えば体を係数とする多項式などが係数になっていても、同様の議論を行うことができます。

可換性については、 Cyclic Lemma を利用する過程でどうしても必要になってくるので、ここは外せなさそうです( $C$ の巡回シフトにより木のスコアが変わらない必要があるため)。

余談その2:一般化公式の導出

今回の手法を応用することで、一般化された公式を導くこともできます。

次の問題を考えます。

【問題1'】

子に左から順番がついた根付き木に対するスコアを、問題1と同様に定める。

正整数 $N, K$ が与えられる。根付き木 $K$ 個が左から順に並んでおり、頂点数の合計が $N$ であるような状況を よい状況 と呼ぶ。よい状況のスコアを、 $K$ 個の部分木のスコアの積で定める。すべてのよい状況に対するスコアの総和を求めよ。

この問題の答えは $[x^{N}] F (x)^{K}$ であり、また同様の議論を進めると $\frac{K}{N} [x^{N - K}] Φ (x)^{N}$ であることが示せます(Cyclic Lemma の部分が少し変わります)。したがって、以下の等式が成り立ちます。

[x^{N}] F (x)^{K} = \frac{K}{N} [x^{N - K}] Φ (x)^{N}

ここで、 $[x^{N - K}]$ の $N - K$ の部分は、議論の流れを考えると、森の辺の本数という解釈をすることができます。解析学に由来する留数などの概念と、組合せ論におけるグラフの辺の本数がこのような形で結びつくのは、なかなか面白いと個人的に思います。

また、上の結果から、以下の等式が成り立ちます。

[x^{N}] H (F (x)) = \frac{1}{N} [x^{N - 1}] H^{'} (x) Φ (x)^{N}

こちらもよく知られた形の式です。

余談その3:多変数バージョン

ラグランジュの反転公式には多変数バージョンのものもあり、これも頑張ると組合せ論から証明できるようです。

https://lipn.univ-paris13.fr/~bacher/lagrange.pdf

上記の論文では、Cycle Lemma をうまいこと拡張し、Prüfer code なども活用することで、多変数の公式を証明しているようです。しかしながら、 $1$ 変数の時ほど簡単な議論はできないようで、普通に難しいです。私はまだ内容を理解できていません。

おわりに

この証明を知った当初、個人的には結構面白い証明だと思ったのですが、探したところこの方法による証明はあまり出回っていないらしく、周知させるべく記事を書くに至りました。皆様の新たな知見・理解の助けになれば幸いです。

本記事を最後まで読んで下さり、ありがとうございました。

参考文献

Cycle Lemma - AtCoder Algorithm Lectures

Axel Bacher and Gilles Schaeffer. "Multivariate Lagrange inversion formula and the cycle lemma". 2013.