形式的冪級数、ケイリーの公式、Prüfer コード

難しかったけど解説ACしたら何かわかったような気がしたのでメモ。

解法の考え方

N頂点ラベル付き木は、各要素が1~Nで長さN-2の配列に１対１対応させることができる。（Prüfer コード。これを使うと、N頂点ラベル付き木の個数が $N^{N-2}$ 個であることがわかる（ケイリーの公式）。）
上記方法で対応させた配列における、各数字の登場回数（の集合）が、元の木の次数-1（の集合）と対応する
逆に木の次数の集合${d_i}$を固定したとき、それに対応する木の種類数が、$\frac{(N-2)!}{\prod_{i} (d_i-1)!}$となる
次数の集合は、グラフが木であることから、総和が$2N-2$となる必要がある
次数の和の部分を仮の変数xに対する指数として考える。$\frac{x^{d_i}}{(d_i-1)!}$という項を掛け合わせると、係数（に定数$(N-2)!$をかけたりしたもの）が種類数、xの指数が次数の和、に対応する。
この掛け算の結果において、xの指数が2N-2になっていれば木の条件を満たす。
そこで、各s_iに対応する項を持つ関数 $f= \sum_{s\in S} \frac{x^{s}}{(s-1)!} $（母関数）を考えて、これを十分な数かけ合わせたのち、$x^{2N-2}$の係数を見てやることで答えがわかる。
元の式にある(N-2)!を忘れずに。

マークダウンの数式の書き方忘れたので後で書く

（追記）調べたら出たけど思ったより面倒だった。