順列 \(P\) の最長増加部分列は \(G(P)\) の最大マッチングを \(m\) として \(N - m\)です。 そのため、頂点数が\(N\), 直径 \(d\), 最大マッチング \(m\) である木を生成する順列 \(P\) の個数を \(c(d, m)\)とすると

\[A_d = \sum_{m=1}^{\lfloor{N/2\rfloor}}c(d,m)(N-m)^K\]

となります。

1. \(c(d, m)\)の計算について

\(N=2\) のときは \(c(1,1)=1\)（それ以外は \(0\)）であり、\(N\ge3\) かつ \(d=2\) のときはスターグラフのみが可能で \(c(2,1)=2\)（それ以外は \(0\)）です。
以下では \(N\ge3,\ d\ge3\) を仮定します。

まず、以下の性質が成り立ちます。

性質1
木 \(T\) がある順列 \(P\) によって \(G(P)\) と表される。 \(\iff\) 木 \(T\) が Caterpillar Graph （直径上の頂点から距離 1 以内に全ての頂点が存在する木）である。

(略証)順列から生成されるグラフが木であるとき、「321-avoiding」という性質を持つことから、深い分岐を持てないことに起因します。

Caterpillarの直径パス（長さ \(d\)）上の頂点を \(v_0, v_1, \dots, v_d\) とし、\(d-1\) 個の頂点 \(v_1, \dots, v_{d-1}\)に葉を付け加えることを考えます。 ここで、 \(v_i\) に接続する葉の数を \(\ell_i\) として数列 \(L = (\ell_1, \ell_2, \dots, \ell_{d-1})\) を考えたとき、頂点数の総和から \(\displaystyle\sum_{i = 1}^{d - 1} \ell_i = N - (d - 1)\) が成り立ちます ( \(v_0, v_d\) は葉であることに注意してください）。

このとき、数列 \(L\) と 順列\(P\) の対応関係について、以下の性質が成り立ちます。

性質 2
各数列 \(L = (\ell_1, \dots, \ell_{d-1})\) に対して、それを生成する順列は構築順序を左から右に固定すると 2 通り である。

(略証) 直径パス \(v_1, v_2, \dots\) の値 \(P(v_i)\) について、木構造を保つには、推移的な辺を作らないよう大小関係を交互に反転させる必要があります 。
Type 1 : \(P(v_1) < P(v_2) > P(v_3) < P(v_4) \dots\)
Type 2 : \(P(v_1) > P(v_2) < P(v_3) > P(v_4) \dots\)
各 \(v_i\) に接続する \(\ell_i\) 個の葉は、互いに辺を持たないため順列内で 昇順 に並び、かつ \(v_i\) とのみ接続するため 、Type 1 または Type 2 を決めると葉の配置も一意に定まります 。なお、この 2 つの順列は互いに逆順列の関係にあります 。

ここで、内側の頂点 \(v_1, \dots, v_{d-1}\) を以下の 3 種類に分類して数え上げを行います。

1. \(a\)(個) : 葉を持ち、自身の葉とマッチングする頂点 (\(a \geq 2\))
   
2. \(b\)(ペア) : 葉を持たず、直径上で隣接する頂点同士でペアを作りマッチングする部分
   
3. \(c\)(個) : 葉を持たず、マッチングにも使用されない頂点
   

\(a,b,c\)は直径と最大マッチングの条件より \(a + 2b + c = d - 1\), \(a + b = m\)を満たす必要があります。

したがって、\(a\) を全探索し、 \(2\binom{a-1}{c}\binom{a+b-2}{b}\binom{N-d}{a-1}\) の総和をとることで数え上げることが可能です。（二項係数の定義域外は0とします。）

さらに、\(b=m-a,\ c=d-1-2m+a\) を用いて式変形を行うと\(c(d, m)\) は以下のように計算できます。（\(L\) 自体の左右反転（e.g., \(\{2,1\}\) と \(\{1,2\}\)）は、別の数列として区別して計算するため \(L\) の対称性を考える必要はありません。）

\[\begin{aligned} c(d, m) &= \sum_{a = 2}^{d-1} 2\binom{a-1}{c} \binom{a+b-2}{b} \binom{N-d}{a-1}\\ &= \sum_{a' =0}^{d-3} 2\binom{N-d}{2m-d} \binom{N-2m}{N-d-1-a'} \binom{m-2}{a'}\\ &=2\binom{N-d}{2m-d} \binom{N-m-2}{N-d-1} \end{aligned}\]

これは、\(d = 2\) についても正しく計算されています。

\(c(d,m)\) を愚直に和を取って \(O(N)\) で計算すると、\(A_1,\dots,A_{d-1}\) を全体で \(O(N^3 + N\log K)\) で求めることができ、部分点を得られます。

2. 高速化

以上より、\(A_d\) は以下のように式変形できます。

\[\begin{aligned} A_d &= \sum_{m=1}^{\lfloor{N/2\rfloor}}2\binom{N-d}{2m-d} \binom{N-m-2}{N-d-1}(N-m)^K \\ &= \sum_{m=1}^{\lfloor{N/2\rfloor}}2\frac{(N-d)!}{(2m-d)!(N-2m)!} \cdot \frac{(N-m-2)!}{(N-d-1)!(d - m - 1)!}(N-m)^K \\ &= (N-d)\sum_{m=1}^{\lfloor{N/2\rfloor}}\frac{2(N-m)^K(N-m-2)!}{(N-2m)!(m-1)!}\cdot\frac{(m-1)!}{(2m-d)!(d-m-1)!}\\ &= (N-d)\sum_{m=1}^{\lfloor{N/2\rfloor}}\frac{2(N-m)^K(N-m-2)!}{(N-2m)!(m-1)!}\binom{m - 1}{d - m - 1} \end{aligned}\]

ここで、\(b_m = \frac{2(N-m)^K(N-m-2)!}{(N-2m)!(m-1)!}\) を前計算すると以下が得られます。

\[\begin{aligned} A_d &= (N-d)\sum_{m=1}^{\lfloor{N/2\rfloor}} b_m [x^{d-m-1}] (1+x)^{m-1} \\ &= (N-d) [x^{d-2}]\sum_{m=1}^{\lfloor{N/2\rfloor}} b_m x^{m-1} (1+x)^{m-1} \\ &= (N-d) [x^{d-2}]\sum_{m=1}^{\lfloor{N/2\rfloor}}b_m (x + x^2)^{m-1} \end{aligned}\]

これは、 \(f(x) = \displaystyle\sum_{i=0}^{\lfloor{N/2\rfloor}-1}b_{i+1} x^i\) と定義すれば、上記の総和部分は \(\displaystyle\sum_{m=1}^{\lfloor{N/2\rfloor}}b_m (x + x^2)^{m-1} = f(x+x^2)\)となリます。ここで、\(x+x^2 = (x+1/2)^2 - 1/4\) であることから、\(f(x+x^2)\) はTaylor shiftを用いて多項式の合成を行うことにより \(b_m\) の前計算と合わせて、全体で \(O(N \log N + N\log K)\) で計算可能です。