凱萊公式

凱萊公式是以數學家亞瑟 凱萊（Arthur Cayley）的名字命名的一個公式，解決了給定n個不同點的情況下，不同構的樹的計數問題。

基本介紹

• 中文名：凱萊公式
• 外文名：Cayley’s formula
• 表達式：k=n^(n-2)
• 提出者：Arthur Cayley
• 提出時間：1860年
• 適用領域：數學

定義

給定n個不同的點，組成的無根樹的個數有n的n-2次方。又被稱為樹多項式。

發展歷史

該式最初在1860年由Carl Wilhelm Borchardt發現並證明。1889年Cayley從多方面拓展了這一公式，從頂點的度入手得到了更多的結論。因此儘管Cayley借鑑了Borchardt的文章，這個公式的標準名稱依然被定為“Cayley's formula”（凱萊公式）。

推導過程

凱萊公式的證明方法包括基爾霍夫矩陣樹定理（又稱為矩陣-樹定理）、Prüfer 編碼、算兩次等方法。

使用矩陣-樹定理可以較快地得到結果。求n個不同的點可組成的不同構的樹的個數，等同於求一個n階完全圖下，不同的生成樹的個數。這實際上就是矩陣-樹定理的特殊情況（如右圖所示），即要求一個對角線上的值為n-1、其餘位置均為-1的矩陣的值。可以直接通過線性代數方法計算，或者可以通過數學歸納法，得出該矩陣的值為n^(n-2)，即為結果。

矩陣-樹定理視角下的凱萊定理形式

推廣

凱萊公式的推廣即為矩陣-樹定理。