ケイリーの公式

数学において、ケイリーの公式は、アーサー・ケイリーにちなんで名付けられたグラフ理論の結果です。これは、任意の正の整数に対して、ラベル付き頂点上の木の数はであると述べています。 ${\displaystyle n}$${\displaystyle n}$${\displaystyle n^{n-2}}$

この式は、ラベル付き頂点を持つ完全グラフの全域木の数をカウントするのと同等です( OEISのシーケンスA000272 )。

ケイリーの木公式の証明は数多く知られている。^[1] この公式の古典的な証明の 1 つは、キルヒホッフの行列木定理 を使用する。 これは、行列の行列式を含む任意のグラフにおける全域木の数の公式である。プリューファー列はケイリーの公式の全単射証明を与える。アンドレ・ジョヤルによる別の全単射証明は、2 つの区別されたノードを持つnノードの木と最大有向擬似森との間の 1 対 1 変換を見つける。ジム・ピットマンによる二重カウントによる証明は、n 頂点の空グラフに追加して根付き木を形成できる有向辺の異なる列の数を 2 つの異なる方法でカウントする。二重カウント (証明手法) § 木の数え上げ を参照。

この公式は1860年にカール・ヴィルヘルム・ボルチャートによって初めて発見され、行列式によって証明された。^[2] 1889年の短いメモで、ケイリーは頂点の次数を考慮して、この公式をいくつかの方向に拡張した。^[3] 彼はボルチャートの元の論文を参照したが、「ケイリーの公式」という名前がこの分野で標準となった。

ケイリーの公式は、 n頂点上のラベル付き根付きフォレストの数、つまり( n + 1) ^{n − 1 を即座に与えます。各ラベル付き根付きフォレストは、ラベル}n + 1の頂点を追加し、それをフォレスト内のツリーのすべてのルートに接続する ことで、頂点が 1 つ追加されたラベル付きツリーに変換できます。

根付森と駐車機能には密接な関係があり、 n台の車に対する駐車機能の数も( n +1) ^{n −1}である。根付森と駐車機能の一対一の関係は1968年にMP Schützenbergerによって示された。^[4]

以下はケイリーの公式をラベル付きフォレストに一般化したものだ: T _{n , k を}、頂点 1、2、...、k がすべて異なる接続要素に属するような、 k 個の接続要素を持つn個の頂点上のラベル付きフォレストの数とする。すると、 T _{n , k} = k n ^{n − k − 1}となる。^[5]