公式解説にある prüfer code を用いた部分問題の結果の導出を記します。文字を置き換え、一般的な問題にしておきます。

\(n\) 個の連結グラフがあり、これらの頂点数は \(s_1,s_2,\dots ,s_n\) である。これらを \(n-1\) 個の橋で結んで連結にする方法を数え上げよ。

この問題の答えは \(\displaystyle \prod_{i=1}^{n}s_i \left(\sum_{i=1}^{n}s_i\right)^{n-2}\) です。以下、これの導出を行います。

各頂点の次数が指定されたときの頂点ラベル付き木の数え上げには prüfer code が有効です。 \(n\) 頂点の木で、頂点 \(i\) の次数が \(d_i\) であるような木の個数を求めましょう。木に対応する prüfer code の長さは \(n-2\) で、このうち \(i\) は \(d_i-1\) 回現れます。したがって、多項係数を用いると、答えは \(\dfrac{(n-2)!}{\prod_{i=1}^{n}(d_i-1)!}\) です。

さて、元の問題に戻りましょう。橋で \(i,j\ (i\neq j)\) 個目の連結グラフを結ぶ方法は \(s_is_j\) 通りあります。連結グラフをひとつの超頂点だと考えたときの \(n-1\) 個の橋の配置（すなわち木の形状）を決め、\(i\) 個目の連結グラフに対応する超頂点の次数を \(d_i\) とすると、 \(\displaystyle\prod_{i=1}^{n}s_i^{d_i}\) が元の問題の答えに寄与します。各超頂点の次数 \(\lbrace d_i\rbrace\) のみ指定されたときの寄与は、 \((n-2)!\displaystyle\prod_{i=1}^{n}\dfrac{s_i^{d_i}}{(d_i-1)!}\) です。

先の式は積の形で書けているので、FPS の積を考えると都合が良いです。\(i\) 番目の連結グラフの次数 \(d\) をパラメータにした FPS を \(f_i\) とし、次のように定めます。

\[f_i=\prod_{d\ge 1}\dfrac{s_i^d}{(d-1)!}x^{d-1}\]

このとき、元の問題の答えは

\[(n-2)![x^{n-2}]\prod_{i=1}^{n}f_i\]

と書くことができます。ここで、 \(f_i\) が \(\exp x\) の定義に似ていることに注目すると、 \(f_i=s_i\exp (s_ix)\) が分かります。したがって

\[\prod_{i=1}^{n}f_i=\left(\prod_{i=1}^{n}s_i\right) \exp{\left(\sum_{i=1}^{n}s_ix\right)}\]

となります。 \(\exp\) の定義に従って、この式で \([x^{n-2}]\) を取り出すと、結論を得ることができます。