ケイリーの公式
ケイリーの公式(ケイリーのこうしき、英: Cayley's formula)は、グラフ理論における公式のひとつ。正整数 n に対し、n 個のラベル付き頂点を持つ木の個数は n であるというもの。ケイリーは19世紀のイギリスの数学者。
n個のラベル付き頂点を持つ木の個数をTnとおく。ラベルが付いた頂点とラベルが付いた辺を持つ根付き木の個数Unを2通りの方法で数える(double countingを参照)。なお根付き木の各辺は、根から遠ざかる方向に向き付けるものとする。
各ラベル付き頂点を持つ木に対して、根の選び方はn通り、辺へのラベルの付け方は(n-1)!通りなので、
U n = T n n ( n − 1 ) ! = T n n ! . {\displaystyle U_{n}=T_{n}n(n-1)!=T_{n}n!.}
次に、別の方法でUnを求める。ラベルが付いたn頂点からなる空グラフに順次向きを持った辺を付け加えることにより根付き木を構成する。k番目に付け加えられる辺のラベルはkとする。 空グラフにn-k本の辺が付け加えられてk本の根付き木(孤立点も根付き木と見なす)からなる森が出来たとする。この森にn-k+1番目の有向辺を付け加える方法は何通りか考える。付け加える有向辺の始点の選び方はn通りあり、終点は、先ほど選んだ始点が属さないk-1個の木の根のなかから選べるので、終点の選び方はk-1通りある。ゆえに辺の付け加え方はn(k-1)通りである。したがって、
U n = ∏ k = 2 n n ( k − 1 ) = n n − 1 ( n − 1 ) ! = n n − 2 n ! . {\displaystyle U_{n}=\prod _{k=2}^{n}n(k-1)=n^{n-1}(n-1)!=n^{n-2}n!.}
Tn n! = n n!から、Tn = nを得る。