ケイリーの公式

ケイリーの公式

ケイリーの公式は、グラフ理論の分野において重要な成果を示すもので、正整数 n に対して、n 個のラベル付き頂点を持つ木の個数が n^(n-2) であると定義されています。この公式は、19世紀の数学者アーサー・ケイリーにちなんで名付けられました。

歴史的背景

ケイリーの公式は、1889年に発表された彼の論文が起源です。ただし、この公式が示されたのはケイリーだけではなく、1860年にカール・ヴィルヘルム・ボルチャルトによっても証明されています。また、1857年にはジェームス・ジョセフ・シルベスターも同様の主張をしており、公式の背景には多くの数学者の貢献が影響しています。さらに、1918年にはハインツ・プリューファーが別の証明を行い、その過程でプリューファーコードの概念を導入しました。

証明方法

ケイリーの公式の証明方法として、二つのアプローチが広く知られています。一つはプリューファーコードを用いた証明であり、もう一つはダブルカウント法を用いた証明です。

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

1. ラベル付き木の対応付け: n 個の点から成るラベル付き木と、記号列 {a1, a2, ..., an-2} を1対1で対応させることを考えます。ここで、各 ai は1から n までの整数です。
2. 全単射の確認: 各 ai は1からnの値を取るため、記号列の組み合わせは n^(n-2) 通り存在することが分かります。したがって、もし木と記号列が一対一で対応していれば、木の数は n^(n-2) であることが示されます。
3. 木の構築: 最小ラベルの点 b1 とその接続点 a1 を選び、b1 及びその辺を削除すると (n-1) 頂点の木を得ます。この操作を繰り返し、最終的に記号列 {a1, a2, ..., an-2} を生成します。このプロセスにより、必ず元の木を復元できます。

ダブルカウント法を用いた証明

1. 定理の定義: n 個のラベル付き頂点を持つ木の個数を Tn とし、根付き木の数を Un と定義します。
2. 根付き木の数え方: 根を選ぶ方法は n 通り、各辺にラベルを付ける方法は (n-1)! 通りであるため、U_n = T_n n! という関係が成り立ちます。
3. 他の方法での数え方: 空グラフに順次辺を追加する方法でも Un を計算できます。この手法からも同様に U_n = n^(n-2) n! という結果が導かれ、最終的に T_n = n^(n-2) が証明されます。

参考文献

この公式は、組合せ論を語る上で欠かせないものであり、詳細な内容は以下の文献に記されています。

• - M. Aigner and G. M. Ziegler, 'Proofs from the Book', 3rd edition, Springer, 2003.
• - Cayley, A. (1897). 'A theorem on trees' in 'The Collected Mathematical Papers of Arthur Cayley'.

ケイリーの公式は、現在も様々な数学的研究や応用に影響を与えており、グラフ理論の基礎的な理論の一部として位置づけられています。

もう一度検索