根付き木で考える.

ある根ではない頂点 \(u\) とその子孫からなる部分木において, \(u\) の色を固定したときのその部分木の色分けの組み合わせ数 \(C(u)\) を考える.

これは \(u\) の子を \(v_i\) とすると, その子の色分けの組み合わせの数は, \(u\) とその親の色が使えないことと, 子たちの色は別々にしなければいけないことから, \({}_{K-2}P_{r}\) (\(r\) は \(u\) の子の数) となる. 当然ながら, \(r < K-2\) の場合は組み合わせの数は \(0\) である.

そして, \(v_i\) の色分けの組み合わせの数も考えると,

\[C(u) = {}_{K-2}P_r \prod_i C(v_i)\]

となる. これを再帰で計算する.

最後に全体の色分けの組み合わせの数は, 根の子を \(v_i\) とすると, 根の子は根の色が使えないだけなので,

\[K {}_{K-1}P_r \prod_i C(v_i)\]

となる.