「頂点の数がn個あるラベル付き木の種類は、nn-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
0 件のコメント:
コメントを投稿