博士

やあ、ロボ子。今日はちょっと難しいけど面白い話をするのじゃ。

ロボ子

はい、博士。どんなお話ですか？

博士

ノード数$n$の順序なし根付き3分木の同型を除いた数を求める問題じゃ。ちょっとややこしいかの？

ロボ子

3分木ですか。以前、順序付き3分木について学びましたね。葉または1,2,3個の子を持つ内部ノードからなる木で、子供の順序が重要でした。

博士

そうじゃ、ロボ子！順序付きの場合は、ノード数$n$の順序付き根付き3分木の数を$t_n$とすると、母関数は$T(z) = z + zT + zT^2 + zT^3$で表せるのじゃ。

ロボ子

なるほど。そして、漸近近似は$t_n \approx C \frac{(3.6107\ldots)^n}{n^{3/2}} \left (1 \pm O \left ( \frac{1}{n} \right ) \right )$で、$C = \frac{(0.8936\ldots)}{2 \sqrt{\pi}}$ですね。

博士

その通り！特異点解析を使うと、複素解析の留数定理を応用して、この漸近近似を導けるのじゃ。積分経路を特異点$omega$の周りの小円と大きな円に分割して評価するんじゃ。

ロボ子

特異点近傍でのPuiseux級数展開も利用するんでしたね。Sageで計算できるんでしたっけ。

博士

そうそう！Sageは便利じゃぞ。で、本題の順序なし3分木じゃが、これは根と3つの再帰的な子を持つんじゃ。子供の順列に関する$\mathfrak{S}_3$の作用を考慮する必要があるのじゃ。

ロボ子

順序なしだと、子供の並び順は区別しないんですね。母関数は$T(z) = 1 + \frac{z}{6} \left ( T(z)^3 + 3 T(z) T(z^2) + 2 T(z^3) \right )$で表されるんでしたね。

博士

さすがロボ子、よく覚えておるの。ここでPólya-Redfieldの数え上げが登場するんじゃ！群$G$が作用する構造$X$と色の集合$C$があるとき、$X$の各要素に$C$の色を割り当てる方法を$G$の作用に関して数えるのじゃ。

ロボ子

サイクル指標多項式$P_G(x_1, \ldots, x_n)$を利用して、色の重みに関する母関数$F(t) = \sum c_i t^i$を代入することで、総重量でソートされた色の塗り分け方を数えるんでしたね。

博士

そうじゃ！そして、漸近近似を求めるには、$F(r,s)=0$かつ$left . \frac{\partial F}{\partial w} \right |_{(r,s)} = 0$を満たす$(r,s)$を見つけるんじゃ。

ロボ子

Puiseux級数展開から$t_n = \frac{\gamma}{\Gamma(-1/2)} \frac{r^{-n}}{n^{3/2}} \left ( 1 + O \left ( \frac{1}{n} \right ) \right )$が得られますね。

博士

そう！数値計算によると、$r \approx 0.3551817478731632$, $s \approx 2.1174205967276225$, $\gamma \approx -1.8358222405236164$となるのじゃ。

ロボ子

したがって、$t_n \approx \frac{(1.835\ldots)}{2 \sqrt{\pi}} \frac{(0.355\ldots)^{-n}}{n^{3/2}}$となるんですね。

博士

そういうことじゃ！どうじゃ、ロボ子、理解できたかの？

ロボ子

はい、博士。難しい内容でしたが、何とか理解できました。

博士

ふむ、ロボ子も賢くなったの。ところでロボ子、3分木って、なんだかクリスマスツリーみたいじゃな？

ロボ子

確かにそうですね、博士。でも、まだ5月ですよ？

博士

まあ、細かいことは気にするな！クリスマスにはまだ早いけど、3分木を眺めて、良いプログラムが書けるように祈るとするか！