ケイリーの公式のソースを表示

[[File:Cayley's formula 2-4.svg|thumb|2個、3個、4個のラベル付き頂点を持つ木の一覧。2個のラベル付き頂点を持つ木は 2<sup>2-2</sup> = 1 個、3個のラベル付き頂点を持つ木は 3<sup>3-2</sup> = 3 個、4個のラベル付き頂点を持つ木は 4<sup>4-2</sup> = 16 個ある。]]
'''ケイリーの公式'''（ケイリーのこうしき、{{lang-en-short|Cayley's formula}}）は、[[グラフ理論]]における公式のひとつ。正整数 ''n'' に対し、''n'' 個のラベル付き頂点を持つ[[木 (数学)|木]]の個数は ''n''<sup>''n''-2</sup> であるというもの。[[アーサー・ケイリー|ケイリー]]は19世紀のイギリスの数学者。

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

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

==証明==
=== プリューファーコードを用いた証明 ===
[[File:Tree graph.svg|right|frame|n=6の時の、n個の点で構成される木の例。この木のプリューファーコードは {4,4,4,5}である]]
n個の点で構成されるラベル付きの木の集合と、記号列「{a<sub>1</sub>,a<sub>2</sub>, ..., a<sub>n-2</sub>}」の集合を、1対1で対応させる（[[全単射]]）ことを考える。ただし、「a<sub>i</sub>」は整数であり、「1≦a<sub>i</sub>≦n」とする。

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

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

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

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

=== double counting法を用いた証明 ===
[[File:Graph.tree. Cayley's formula.png|thumb|有向辺を付け加える。]]
n個のラベル付き頂点を持つ木の個数を''T<sub>n</sub>''とおく。ラベルが付いた頂点とラベルが付いた辺を持つ根付き木の個数''U<sub>n</sub>''を2通りの方法で数える（[[:en:double counting (proof technique)|double counting]]を参照）。なお根付き木の各辺は、根から遠ざかる方向に向き付けるものとする。

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

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

:<math>U_n=\prod_{k=2}^{n} n(k-1) = n^{n-1} (n-1)! = n^{n-2} n!.</math>

{{nowrap|''T<sub>n</sub> n!'' {{=}} ''n''<sup>''n'' &minus; 2</sup> n!}}から、{{nowrap|''T<sub>n</sub>'' {{=}} ''n''<sup>''n'' &minus; 2</sup>}}を得る。

== 参考文献 ==
* M. Aigner and G. M. Ziegler, "Proofs from the Book", 3rd edition, Springer, 2003. ISBN 3540404600（日本語訳、蟹江幸博『天書の証明』[[シュプリンガー・ジャパン|シュプリンガー・フェアラーク東京]]、2002年 ISBN 443170986X）-- 組合せ論のひとつの章がケイリーの公式に当てられている。
* {{citation
    |last1              = Cayley
    |first1             = A.
    |authorlink1        = アーサー・ケイリー
    |contribution       = A theorem on trees
    |contribution-url   = https://archive.org/details/collmathpapers13caylrich/page/n45
    |origyear           = 1889
    |journal            = Quart. J. Pure Appl. Math.
    |volume             = 23
    |pages              = 376–378
    |editor-last        = Forsyth
    |editor-first       = A. R.
    |title              = The Collected Mathematical Papers of Arthur Cayley. Vol. 13
    |year               = 1897
    |publisher          = University Press
    |location           = Cambridge
    |doi                = 10.1017/CBO9780511703799.010
    |ref                = {{sfnref|Cayley|1889}}
}}

{{デフォルトソート:けいりいのこうしき}}
[[Category:グラフ理論]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]