ラベルなし木の数え上げ - Shirotsume の日記

最終目標
ラベル付きの場合
根付き木の場合
- ラベルなし根付き木と多重集合の対応関係
- 根付き木の集合を特徴づける
根なし木の場合
あとがき

最終目標

整数 $N$ が与えられるので、 $N$ 頂点の木の個数 mod 998244353 を数えよ。ただし頂点は互いに区別されないとする（同型な木の個数を数える）

↓これです

oeis.org

この問題は ABC230Hの解説で発展問題として提示されています。この記事ではABC230Hの理解は前提としませんが、解説を事前に読んでおくとわかりやすいかもしれません。

Editorial - AtCoder Beginner Contest 230

ラベル付きの場合

もしかして：Prüfer Sequence, ケイリーの公式

この記事では説明しないので、↑でググってみるといいかも

根付き木の場合

整数 $N$ が与えられるので、 $N$ 頂点の根付き木の個数 mod 998244353 を数えよ。ただし頂点は互いに区別されないとする（同型な根付き木の個数を数える）

oeis.org

ラベルなし根付き木と多重集合の対応関係

めちゃくちゃ唐突ですが、ラベルなし根付き木と各要素が多重集合である多重集合との一対一対応が取れるので、それを考えます。

頂点数1の根付き木（根だけです）を空の多重集合 $\{ \}$ と対応付けます。一般の根付き木に対しては次の要領で再帰的に多重集合を対応付けます：

根である頂点の（直接の）子それぞれについて、子の部分木に対応する多重集合を $S_1, S_2, \dots, S_k$ とする。このとき、この根付き木と対応する多重集合は $\{S_1, S_2, S_3, \dots, S_k \}$ とする。

というわけで、多重集合の多重集合とラベルなし根付き木の対応関係を作れました。ラベルなし根付き木なので、子の順序などは考えません。

これは言い換えると、根付き木とは、「根付き木の多重集合に根を加えた構造」という再帰的な性質を持つといえます。

根付き木の集合を特徴づける

FPS（形式的べき級数）をやります。頑張って頭をFPSにしてもう一回ここに来てください。FPSになりましたか？

FPS は、何らかの組合せ的構造をもつオブジェクトを数えるときによく使われます。ここで、「オブジェクトを並べた列」や「オブジェクトの多重集合」も、うまくやれば数えることができます。

例題：6面さいころを5回振る。振って出た目を順に並べてできる長さ5、総和 i の数列の個数を $A_i$ とする。 $A$ の母関数を求めよ。

答え： $(x + x ^ 2 + x ^ 3 + x ^ 4 + x ^ 5 + x ^ 6) ^ 5$

もうちょっと一般的にいうと、母関数が $F(x)$ であるものを $K$ 個並べてできる列の母関数は $\{ F (x) \} ^ K$ になります。

このテクニックを使えば、母関数がわかっているとき、それを並べてできる列の母関数もわかるということになります。やったね！

さて、根付き木の話に戻ります。頂点数 $i$ のラベルなし根付き木の個数を $A_i$ とします。 $A$ の母関数 $\displaystyle F(x) = \sum _ {i=0} ^ {\infty} A_i x ^ i$ を求めたいです。

ここで、前提知識として次を使います：

母関数が $F(x)$ であるオブジェクトからなる多重集合の母関数は $\displaystyle \exp \left ( \sum _ {k > 0} ^ {\infty} \frac{F(x ^ k)}{k} \right )$

いきなりゴツイ式が出てびっくりさせたかもしれませんが、このまま突き進みます。

根付き木は、「根付き木の多重集合に、根を加えた構造」としてみなすことができます。よって、 $F(x)$ は次の関係式を満たします。

$\displaystyle F(x) = x \exp \left ( \sum _ {k > 0} ^ {\infty} \frac{F(x ^ k)}{k} \right )$

手前の $x$ が根を表し、後ろの部分が根付き木の多重集合を表します。あとはこの $F(x)$ の先頭 $N$ 項を求められれば良いです。

両辺を微分してみます。積の微分公式を思い出すと、

$\displaystyle F'(x) = \exp \left ( \sum _ {k > 0} ^ {\infty} \frac{F(x ^ k)}{k} \right ) + x \left ( \sum _ {k > 0} ^ {\infty} \frac{F(x ^ k)}{k} \right )' \exp \left ( \sum _ {k > 0} ^ {\infty} \frac{F(x ^ k)}{k} \right )$

となります。両辺に $x$ をかけると、

$\displaystyle xF'(x) = x \exp \left ( \sum _ {k > 0} ^ {\infty} \frac{F(x ^ k)}{k} \right ) + x \left ( \sum _ {k > 0} ^ {\infty} \frac{F(x ^ k)}{k} \right )' {\times} x \exp \left ( \sum _ {k > 0} ^ {\infty} \frac{F(x ^ k)}{k} \right )$

$\displaystyle xF'(x) = F(x) + x \left ( \sum _ {k > 0} ^ {\infty} \frac{F(x ^ k)}{k} \right )' {\times} F(x)$

$\displaystyle xF'(x) = F(x) \left \{ 1 + x \left ( \sum _ {k > 0} ^ {\infty} F ' (x ^ k ) \right ) \right \}$

ここで、 $F(x) = \sum _ {i = 0} ^ {\infty}f_i x ^ i$ 、 $G(x) = 1 + x \left ( \sum _ {k > 0} ^ {\infty} F ' (x ^ k ) \right ) = \sum _ {i = 0} ^ {\infty}g_i x ^ i$ とおきます。

このとき、 $x F ' (x) = \sum _ {i = 0} ^ {\infty} i f_i x ^ i$ であることから、

$\displaystyle n f_n = \sum_{i = 0} ^ {n - 1} f_i g _ { n - 1 - i }$

が成り立つことがわかります。 $g_i$ の値については、 $k$ を全通り試して $i$ 番目までの寄与を求めれば、いわゆる調和級数のやつでできます。

よって、 $f_1 = 1$ から順番に $f, g$ を漸化式に従って求めればよいので、 $f, g$ の $N$ 項めまでを分割統治FFTやオンライン畳み込みを用いることによって $O(N \log ^ 2 N)$ で求めることができます。

実際に実装しましょう。オンライン畳み込みはkiriさんからお借りしたコードを使用します。

↓kiriさんによるオンライン畳み込みの記事

qiita.com

実際に実装したものが下のリンク先のコードとなります。Nを標準入力で与えるとN以下についての結果を出力します。実際にN = 20 などで試してみると、A000081と一致する結果が得られます。（それより大きくなるとmod998244353をとっているので一致しなくなります）

wandbox.org

ということで、 $N$ 頂点のラベルなし根付き木の個数を数えることができました。

根なし木の場合

ラベルなし根なし木の母関数 $U(x)$ とラベルなし根付き木の母関数 $F(x)$ について、

$\displaystyle U(x) = 1 + F(x) - \frac { \{ F(x) \} ^ 2 - F(x ^ 2)} {2}$

という関係が成り立ちます。

これを証明するために、根なし木の重心を定義しましょう。頂点数 $N$ の木の重心とは、以下の条件を満たす頂点です。

重心 $v$ を根としたとき、 $v$ のどの子の部分木のサイズも $\displaystyle \frac{N} {2}$ 以下である。

ここでは証明しませんが、木の重心について以下の事実が成り立ちます。

木の重心の個数は 1 個または 2 個。木の重心が 2 個存在するとき、それらは隣接している。

$N$ の偶奇で場合分けをします。また、以下では頂点数 $i$ の根付き木の個数を $f _ i$ とおきます。

N が奇数の場合

根付き木をとったとき、その根が（根なし木における）重心と ならない 場合を考えましょう。これは、根の（直接の）子の部分木であって、サイズが $\frac{N} {2}$ より大きいものが存在することと同値です。

よって、根が重心とならない木は、 $i + j = n, i > j$ なる $i, j$ をとってきて、頂点数 $j$ の根付き木の根に頂点数 $i$ の根付き木を付けたものとして構成できます。よって、根が唯一の重心となる $n$ 頂点の木の個数は、

$\displaystyle f _ n - \sum _ { i + j = n, i > j \geq 0 } f _ i f _ j$

$= \displaystyle f _ n - \frac {1} {2} \sum _ { i + j = n } f _ i f _ j$

として求めることができます。また、 $n$ が奇数のとき、重心は必ず 1 個です。よって、根なし木の個数もこれと等しくなることがわかります。

N が偶数の場合

奇数の場合と同様に、根が唯一の重心となる $n$ 頂点の木の個数は $\displaystyle f _ n - \sum _ { i + j = n, i > j \geq 0 } f _ i f _ j$ です。頂点数が偶数の場合、これに加えて、重心が 2 つある木の個数を追加で数えます。

頂点数が $n$ で重心が 2 つある木は、頂点数 $\frac { n } {2}$ の根付き木を 2 つ取ってきて、それらの根同士をつないで作ることができます。よって、この個数は

$\displaystyle \frac { f _ {n/2} ( f _ {n/2} + 1) } {2}$

として計算することができます。

よって、根なし木の個数は

$\displaystyle f _ n - \sum _ { i + j = n, i > j \geq 0 } f _ i f _ j - \frac { f ^ 2 _ {n/2} } {2} + \frac { f _ {n/2} } {2}$

$\displaystyle = f _ n - \frac{1} {2} \sum _ { i + j = n} f _ i f _ j + \frac { f _ {n/2} } {2}$

として計算できます。

根なし木　実装

以上の偶数の場合、奇数の場合を合わせて、FPSで書き直すと上記の式

$\displaystyle U(x) = 1 + F(x) - \frac { \{ F(x) \} ^ 2 - F(x ^ 2)} {2}$

が得られます。

$\{ F(x) \} ^ 2$ の部分は畳み込みで計算できるので、 $F(x)$ から $U(x)$ を $O( N \log N)$ で求めることができます。

よって、ラベルなし根なし木の個数を数えることができました。

実際にコードを書いたものが以下です。