前提知識

数え上げの話

前書き

皆さまお元気ですか？自分はそんなに元気ではありません。今回は、折角面白いトピックに出会い、証明を追ったので、数え上げとLagrangeの反転公式の話をしようと思います。あまり難しい話ではなく、既に結構知られているかもしれませんが、なんとなく説明します。関数方程式の扱いとか、色々なところで出てくるでしょう。少しでも参考になる人がいたらいいなぁ。

Lagrangeの反転公式

色々な反転公式が知られています。2項反転公式や、stirlingの反転公式が有名かもしれません。Lagrangeの反転公式も、たぶん有名です。まず、それの証明を簡単に与えていきたいと思います。

Theorem (Lagrangeの反転公式)

まず、記号の導入で、 $[x^n]$は作用素で、多項式の$x^n$の係数を取り出すものとします。たとえば、$[x^n](\sum a_kx^k)=a_n$です。また、$\mathbb{C}[x]:=\{ \sum_{k \geq 0} a_kx^k | a_k \in \mathbb{C} \}$とします。

$f(x)$,$g(x) \in \mathbb{C}[x]$で、$f(g(x))=x$を満たしているとします。
このとき、

$$[x^n]g(x)=\frac{1}{n}[x^{-1}]\frac{1}{f(x)^n}$$

が成立します。

$f$と$g$が反転の関係になっているわけですね。

Lemma

$f(x) \in x \mathbb{C}[x]$で、$[x^{-1}]f'(x)\neq0$とします。このとき、
$i \in \mathbb{Z}$について、

$$[x^{-1}]f(x)^if'(x)= \begin{cases} 1 \ (i=-1) \\ 0 \ (その他) \end{cases}$$

が成立しています。

（Lemma の証明）
まず、$i \neq -1$では、$f(x)^if'(x)=\frac{1}{i+1}(f(x)^{i+1})'$になります。一般にローラン展開された関数について、つまり、$h(x)=\cdots+a_{-1}x^{-1}+a_0+a_1x+\cdots$なら、$[x^{-1}]h'(x)=0$です。よって、$f(x)^if'(x)$の$x^{-1}$の係数は$0$です。
次に$i=-1$のときは、$f(x)=\sum_{k\geq1} a_kx^k$とすると、

$$\begin{aligned} \frac{f'(x)}{f(x)}&=\frac{a_1+2a_2x+3a_3x^2+\cdots}{a_1x+a_2x^2+a_3x^3+\cdots}\\ &=\frac{a_1+2a_2x+3a_3x^2+\cdots}{a_1x}\cdot\frac{1}{1+2a_2/a_1x+3a_3/a_1x^2+\cdots}\\ &=(x^{-1}+2a_2/a_1+3a_3/a_1x+\cdots) \cdot (1-2a_2/a_1x-3a_3/a_1x^2-\cdots) \end{aligned}$$

より、$x^{-1}$の係数は$1$になります。

(Theoremの証明)
Lagrangeの反転公式を示します。
$g(x)=\sum_{i\geq0}b_ix^i$とします。いま、

$$x=g(f(x))=\sum_{i\geq0}b_i(f(x))^i$$

が成り立っています。両辺を$x$で微分すると、

$$1=\sum_{i\geq1}b_iif(x)^{i-1}f'(x)$$

となります。さらに、両辺$f(x)^n$で割ると

$$\frac{1}{f(x)^n}=\sum_{i\geq1}b_ii\frac{f(x)^{i-1}}{f(x)^n}f'(x)$$

を得ます。ここで、先ほどの補題を使うことができます。つまり、うえの右辺は、
$i=n$以外では消えます:

$$\begin{aligned} \frac{1}{f(x)^n}&=\sum_{i=1}^{n-1}b_ii\frac{f(x)^{i-1}}{f(x)^n}f'(x) +b_nn\frac{f(x)^{n-1}}{f(x)^n}f'(x) +\sum_{i\geq n+1}b_ii\frac{f(x)^{i-1}}{f(x)^n}f'(x)\\ &=\sum_{i=1}^{n-1}b_iif(x)^{-n+i-1}f'(x) +b_nn(f(x))^{-1}f'(x) +\sum_{i\geq n+1}b_iif(x)^{-n+i-1}f'(x). \end{aligned}$$

ゆえに、$[x^{-1}]\frac{1}{f(x)^n}=b_nn$で、結局、 $b_n=\frac{1}{n}[x^{-1}]\frac{1}{f(x)^n}$です。
証明完了です。

Lagrangeの反転公式の一例

ここでは、今回使う形に限定して考えます。Theoremの$f(x),g(x)$を、$f(x)=\frac{x}{\phi(x)}$,$g(x)=x\phi(g(x))$にします。まずこれは、$f(g(x))=x$を満たします。なぜなら、
$f(g(x))=\frac{g(x)}{\phi(g(x))}=x$だからです。さらに、この$g$の係数について、Lagrangeの反転公式を使えば、

$$[x^n]g(x)=\frac{1}{n}[x^{n-1}]\phi(x)^n$$

となっていることがわかります。
なぜなら、

$$[x^n]g(x)=\frac{1}{n}[x^{-1}]\frac{1}{f(x)^n}=\frac{1}{n}[x^{-1}]\frac{\phi(x)^n}{x^n}=\frac{1}{n}[x^{n-1}]\phi(x)^n$$

が成り立つからです。
さて、これは結構使えそうな予感がします。これは、関数$g$が$g(x)=x\phi(g(x))$という関数方程式を満たしているなら、それをテイラー展開などで多項式表示したときの、係数が分かることを意味しています。まあ、両辺展開して、比較したら良いだけだろうと思うかもしれませんし、収束半径も当然気にする必要があります。

今回説明したいのは、数え上げを計算する際、母関数を考えると思いますが、その母関数に対して、このLagrangeの反転公式を応用できる場面が多いですよ、というものです。母関数は、形式的なものなので、収束半径などの議論は全く考えないものとします。

カタラン数

カタラン数は、様々なものの数え上げに登場します。例えば、順序積の数え上げ、また、分岐が$n$個の2分木の数え上げなどがあります。カタラン数$C_n$は、$C_0=1$,$C_1=1$を満たしています。また、漸化式、

$$C_n=\sum_{k=1}^nC_{k-1}C_{n-k}$$

を満たします。これから、$C_2=2$,$C_3=5$になります。これの一般項は、色々な方法で計算できると思います。帰納法とか簡単そうです。ここでは、違う方法で頑張ります。
母関数$c(x)=\sum_{n=0}^{\infty}C_nx^n$を考えます。いきなり、$1+xc(x)^2$を計算します。すると、

$$\begin{aligned} 1+xc(x)^2&=1+x(C_0+C_1x+C_2x^2+\cdots)^2\\ &=1+x(C_0^2+(C_0C_1+C_1C_0)x+(C_0C_2+C_1^2+C_2C_0)x^2+\cdots \\ &=1+C_0^2x+(\sum_{k=1}^2C_{k-1}C_{n-k})x^2+(\sum_{k=1}^3C_{k-1}C_{n-k})x^3+\cdots \\ &=c(x) \end{aligned}$$

が得られます。$c$が満たす、関数方程式が得られました。Lagrangeの反転公式を使うため、$g(x)=c(x)-1$と置きます。そのとき、$c$に関する等式から、$g$に関する等式

$$ g(x)=x(1+g(x))^2$$

が得られます。よって、$\phi(x)=(1+x)^2$とすると、反転公式から、$g$の係数が得られます。それは、母関数の定義からカタラン数に一致します。つまり、

$$\begin{aligned} C_n&=[x^n]g(x)\\ &=\frac{1}{n} [x^{n-1}] \phi(x)^n\\ &=\frac{1}{n} [x^{n-1}] (1+x)^{2n}\\ &=\frac{1}{n} {}_{2n}C_{n-1} \\ &=\frac{1}{n+1} {}_{2n}C_{n} \end{aligned}$$

となります。最後は書き直す意味は微妙ですが、$n=0$も一緒にしたい気持ちです。
とりあえず、カタラン数の一般項が計算されました。正直、面倒くさかったかもしれません。しかし、一般的な公式から計算できるのは、やはり嬉しさがあります。ただし、関数方程式が急に得られたのは謎です。

ラベル付き根付き木の数え上げ

$n$個の頂点をもつ、ラベル付きの根付き木の総数を$R_n$と書きます。因みに、$n$個の頂点をもつ、ラベル付き木の総数を$T_n$とすると、これらについて、根の選び方は$n$通りあるので、$R_n=nT_n$という等式が成立しています。
$T_n=n^{n-2}$であるというのは、Cayleyの定理と呼ばれていますが、$R_n$の計算は、実質的にこれを示していることに対応します。何が言いたいかと言うと、そんなに簡単な問題ではないと言いたいだけです。

$R_n$は次の漸化式を満たします:

$$R_n=n \sum_{m=0}^{\infty}\frac{1}{m!}\sum_{k_1+\cdots+k_m=n-1}\frac{(n-1)!}{k_1!\cdots k_m!}R_{k_1}\cdots R_{k_m}.$$

結構複雑な見た目をしていますが、根の子にあたる頂点が$m$個あったとして、それらの下にある部分木のサイズが$k_1,...,k_m$である場合から、帰納的に計算できるといった視点から、満たされている等式です。
ちなみに、すべての頂点数は$n$個だったので、$k_1+\cdots+k_m=n-1$は常に成立しています。階乗は、重複を除いており、最初の$n$はそもそもの根の選び方です。

$R_n$の指数型母関数、つまり、$g(x)=\sum_{n=0}^{\infty}\frac{R_n}{n!}x^n$を考えることにします。先ほどと同様に$g$に関する関数方程式を求めたいです。今回も天から降ってきたものを使います。$xe^{g(x)}$を計算します。

$$\begin{aligned} xe^{g(x)}&=x\sum_{m=0}^{\infty}\frac{1}{m!}g(x)^m \\ &=x\sum_{m=0}^{\infty}\frac{1}{m!} \left(\sum_{k_1=0}^{\infty}\frac{R_{k_1}}{k_1!}x^{k_1} \right) \cdots \left(\sum_{k_m=0}^{\infty}\frac{R_{k_m}}{k_m!}x^{k_m} \right)\\ &=x\sum_{m=0}^{\infty}\frac{1}{m!} \sum_{k_1=0}^{\infty}\cdots \sum_{k_m=0}^{\infty} \left( \frac{R_{k_1}}{k_1!}x^{k_1} \cdots \frac{R_{k_m}}{k_m!}x^{k_m} \right). \\ \end{aligned}$$

ここで、$k_1+\cdots +k_m=n-1$として、$k_i:0 \rightarrow \infty$を$n:0\rightarrow \infty$にまとめます。つまり、

$$\begin{aligned} xe^{g(x)}&=\sum_{m=0}^{\infty}\frac{1}{m!} \sum_{n=0}^{\infty} \sum_{k_1+\cdots+ k_m=n-1} \left( \frac{n!}{k_1!\cdots k_m!}R_{k_1}\cdots R_{k_m} \frac{x^n}{n!} \right)\\ &=\sum_{n=0}^{\infty}\frac{R_n}{n!}x^n\\ &=g(x) \end{aligned}$$

となります。面倒な計算をしてきましたが、結局、$g$は$xe^{g(x)}=g(x)$を満たすということがわかりました。
この見た目からわかるように、Lagrangeの反転公式が使えます。$\phi(x)=e^x$とします。

$$\begin{aligned} \frac{R_n}{n!}&=[x^n]g(x)\\ &=\frac{1}{n} [x^{n-1}] \phi(x)^n\\ &=\frac{1}{n} [x^{n-1}] e^{nx}\\ &=\frac{1}{n!}n^{n-1}.\\ \end{aligned}$$

結局、$R_n=n^{n-1}$であることがわかりました。

まとめ

なんかよくわからないけど、面白いトピックを扱いました。数え上げを行いたいときに、いちいち関数方程式を発見して、そこから、Lagrangeの反転公式を用いて計算するという手法が一般的にどれくらい使われているのかはわかりません。ですが、数え上げやその数を、ある関数方程式を満たすものと定義すると、別の見方もできるんじゃないかなとか思っています。あとは、やばそうな数え上げの近似解を計算できるかもしれません。また、調べてみます。今回の記事はなぜかあまり疲れませんでした。それでは。