Prüfer sequence への言い換え

実を言うとこの言い換えは本質的には必要なく、次数列のままでも同じ議論ができるのですが、わかりやすさのために Prüfer sequence に言い換えてからお話させていただきます。

\(2\) つのラベル付き木の次数列が等しいことは、Prüfer sequenceにおける各頂点の登場回数が等しいことと同値です。またその直径の最大は Prüfer sequence に登場する頂点の種類数 + \(1\) に等しいです。

そこで \(\left \lbrace 1, \dots, N \right \rbrace\) のソート済み \(N - 2\) 項列 \(P _ 1, \dots, P _ { N - 2 }\) の集合を \(\mathcal P\) とおき、各 \(P \in \mathcal P\) に対してそのスコア \(f(P)\) を、\(P\) に登場する頂点の種類数 + \(1\) と定義すると、答えは

\[ \mathtt{ans} = \sum _ { P \in \mathcal P } f ( P ) = \left \lvert \mathcal P \right \rvert \cdot E \left \lbrack f \right \rbrack \]

（ただし \(E \left \lbrack f \right \rbrack\) は\(\mathcal P\) の要素数と\(P\) を \(\mathcal P\) から一様ランダムに選択したときの \(f ( P )\) の期待値）となります。

要素数 \( \left \lvert \mathcal P \right \rvert \)、期待値 \( E \left \lbrack f \right \rbrack\) の計算

\(\mathcal P\) の要素は Stars and bars (combinatorics) - Wikipedia にある方法により、\(N - 2\) 個の ★ と \(N - 1\) 個の | から成る長さ \(2 N - 3\) の文字列 \(s\) と一対一対応します。この言い換えをすると、

\[ \begin{aligned} \left \lvert \mathcal P \right \rvert &= \binom { 2 N - 3 } { N - 1 } \\ f ( P ) &= N - 1 - (s の ★★ に等しい部分文字列の個数) \end{aligned} \]

がわかります。 さらに \(s\) の長さ \(2\) の部分文字列は \(2 N - 4\) 個あり、それぞれが ★★ に等しくなる確率は

\[ \frac { N - 2 } { 2 N - 3 } \cdot \frac { N - 3 } { 2 N - 4 } \]

ですから、

\[ \begin{aligned} E \left \lbrack f \right \rbrack = N - 1 - (2 N - 4) \cdot \frac { N - 2 } { 2 N - 3 } \cdot \frac { N - 3 } { 2 N - 4 } = \frac { N ^ 2 - 3 } { 2 N - 3 } \end{aligned} \]

となり、

\[ \begin{aligned} \mathtt{ans} = \binom { 2 N - 3 } { N - 1 } \frac { N ^ 2 - 3 } { 2 N - 3 } = \binom { 2 N - 4 } { N - 2 } \frac { N ^ 2 - 3 } { N - 1 } \end{aligned} \]

と結論付けられます。