Search on the blog

2013年4月29日月曜日

Cayley’s Formula

「頂点の数が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 件のコメント:

コメントを投稿