Cayley’s Formula

「頂点の数がn個あるラベル付き木の種類は、n^n-2個」らしい。

この公式は、Cayley’s Formulaと呼ばれている。

証明は、木の集合Tとprufer sequenceの集合の間にbijectiveな関数が存在することを使って、prufer sequenceの要素数を数えればいい。

ここに分かりやすい証明がある。

自分で証明したときは、関数fがbijectiveであることを示すために、fがinjectiveであることとsurjectiveであることを示したけど、上のpdfにあるように、ある関数fとfの逆関数が存在するって示せば十分なのか。逆関数があるってことはfはinjectiveじゃないといけないし、f: x -> yとして任意のy'に対してx' = f^-1(y')がf(x') = y'を満たすからfはsurjective。

最後に（というかこれがこの公式を知るきっかけとなったのですが）、Cayley’s Formulaを使うとエレガントに解ける問題を紹介します。

Codeforces #177 Polo the Penguin and Houses