ケイリーの公式

2個、3個、4個のラベル付き頂点を持つ木の一覧。2個のラベル付き頂点を持つ木は 2^2-2 = 1 個、3個のラベル付き頂点を持つ木は 3^3-2 = 3 個、4個のラベル付き頂点を持つ木は 4^4-2 = 16 個ある。

ケイリーの公式（ケイリーのこうしき、英: Cayley's formula）は、グラフ理論における公式のひとつ。正整数 n に対し、n 個のラベル付き頂点を持つ木の個数は n^n-2 であるというもの。ケイリーは19世紀のイギリスの数学者。

歴史

この公式にアーサー・ケイリーの名が冠されているのは、1889年の論文 (Cayley 1889) に由来する。ただし、この論文が引用しているカール・ヴィルヘルム・ボルチャルトの論文（1860年）において、すでに証明が与えられている。また、ジェームス・ジョセフ・シルベスターも1857年に同値な命題を与えている。

1918年にハインツ・プリューファーが行った証明が有名で、この過程でプリューファーコードの概念が生み出された。

証明

プリューファーコードを用いた証明

n=6の時の、n個の点で構成される木の例。この木のプリューファーコードは {4,4,4,5}である

n個の点で構成されるラベル付きの木の集合と、記号列「{a₁,a₂, ..., a_n-2}」の集合を、1対1で対応させる（全単射）ことを考える。ただし、「a_i」は整数であり、「1≦a_i≦n」とする。

「1≦a_i≦n」（つまり、記号「a_i」は1からnまでの値を取りうる）であるから、記号列「{a₁, a₂, ..., a_n-2}」の個数は、全部で「n^n-2」個あると言える。なので、もしn個の点で構成される木の集合と、記号列「{a₁,a₂, ..., a_n-2}」の集合を、1対1で対応させることができたなら、n 個のラベル付き頂点を持つ木の個数が「n^n-2」個であるということが直ちに言える。「n=1」または「n=2」の時は自明であるので、「n≧3」の時について考えよう。

端点のラベルで最小のものをb₁とし、b₁に隣接している点のラベルをa₁とする。この時、点b₁とその接続辺を除去すると、「n-1」個の点で構成されるラベル付きの木が得られる。次に、この新しい木の端点で最小のラベルをb₂とし、点b₂に隣接している点のラベルをa₂とし、点b₂とその接続辺を除去する。このように、端点と隣接辺のセットを次々に除去していき、2つの点になるまで続けていく。この結果、記号列{a₁,a₂, ..., a_n-2}が得られる。この記号列を「プリューファーコード」と呼ぶ。例えば上図のようなラベル付きの木の場合、「n=6」であり、プリューファーコードは 「{4,4,4,5}」である。

逆も見ていこう。まず、辺のないn個の点だけで構成されるグラフを考えよう。このグラフの中で、記号列「{a₁,a₂, ..., a_n-2}」の中にはない、最小の点のラベルをb₁として、点b₁と点a₁を辺で結ぶ。次に、記号列からa₁を除去し、点b₁に×印を付けよう。次に、記号列「{a₂, ..., a_n-2}」の中にはなく、×印もついていない最小の点のラベルをb₂として、点b₂と点a₂を辺で結ぶ。このように、次々と線を結んでいき、点a_n-2と点b_n-2まで結び、最後に×印の付いていない（点b₁からb_n-2までに含まれなかった）2点を線で結ぶ。こうしてできたグラフを見ると、最初の木と同じものである。

このように見ていくと、任意に設定したプリューファーコードから、必ず最初に出発した木に戻ることができることが分かる。つまり、記号列「{a₁,a₂, ..., a_n-2}」の集合と、n個の点で構成されるラベル付きの木の集合が、1対1で対応していることが言える。証明終。

double counting法を用いた証明

有向辺を付け加える。

n個のラベル付き頂点を持つ木の個数をT_nとおく。ラベルが付いた頂点とラベルが付いた辺を持つ根付き木の個数U_nを2通りの方法で数える（double countingを参照）。なお根付き木の各辺は、根から遠ざかる方向に向き付けるものとする。

各ラベル付き頂点を持つ木に対して、根の選び方はn通り、辺へのラベルの付け方は(n-1)!通りなので、

$U_{n}=T_{n}n(n-1)!=T_{n}n!.$

次に、別の方法でU_nを求める。ラベルが付いたn頂点からなる空グラフに順次向きを持った辺を付け加えることにより根付き木を構成する。k番目に付け加えられる辺のラベルはkとする。 空グラフにn-k本の辺が付け加えられてk本の根付き木（孤立点も根付き木と見なす）からなる森が出来たとする。この森にn-k+1番目の有向辺を付け加える方法は何通りか考える。付け加える有向辺の始点の選び方はn通りあり、終点は、先ほど選んだ始点が属さないk-1個の木の根のなかから選べるので、終点の選び方はk-1通りある。ゆえに辺の付け加え方はn(k-1)通りである。したがって、

$U_{n}=\prod _{k=2}^{n}n(k-1)=n^{n-1}(n-1)!=n^{n-2}n!.$

T_n n! = n^{n − 2} n!から、T_n = n^{n − 2}を得る。

参考文献

• M. Aigner and G. M. Ziegler, "Proofs from the Book", 3rd edition, Springer, 2003. ISBN 3540404600（日本語訳、蟹江幸博『天書の証明』シュプリンガー・フェアラーク東京、2002年 ISBN 443170986X）-- 組合せ論のひとつの章がケイリーの公式に当てられている。
• Cayley, A. (1897) [1889], A theorem on trees, in Forsyth, A. R., “The Collected Mathematical Papers of Arthur Cayley. Vol. 13”, Quart. J. Pure Appl. Math. (Cambridge: University Press) 23: 376–378, doi:10.1017/CBO9780511703799.010, https://archive.org/details/collmathpapers13caylrich/page/n45