# Cayley's Formula 與 Prüfer Code
這篇要來聊聊生成樹，在競程最常看到的生成樹題目，除了最小生成樹相關的之外，應該就是計數了。最小生成樹在[這一篇](https://hackmd.io/@ShanC/minimum-spanning-tree)聊過，這裡主要就是談談計數。計數就是計算某種東西的數量，本質上就是要能夠和 $\mathbb{N}$ 一一對應 (或 bijection) 而已。國高中的計數就只是算算排列組合數、要分成幾堆之類而已

然而，在樹的計數，因為樹本身的結構很特殊，計數並不是一件簡單的事情。這類關於樹的競程題非常少見，但是每次見到鐵定是難題，尤其那些會跟 Combinatorics 一起出現的怪東西們，更是令人頭痛

這篇筆記會以生成樹作為切入點，來聊聊 Cayley's Formula、Prüfer Code 與克希荷夫的矩陣樹定理，並提供三種證明 Cayley's Formula 的方法

由於有些東西真的太難了，可能不會講要怎麼證明 ||反正競程能用就好||

## 生成樹
通常我們會討論生成樹，都是在一張一般的圖上討論。如果是樹的話，討論其生成樹沒什麼意義，因為樹的生成樹就是自己

### 定義
若一棵樹 $T$ 是一張連通圖 $G$ 的子圖，且 $V(T) = V(G)$ (即 $T$ 擁有所有 $G$ 的節點)，則稱 $T$ 為一棵生成樹

<center class = "half">
<img src="https://hackmd.io/_uploads/B1NKHX98kl.png" style="width: 340px">
<img src="https://hackmd.io/_uploads/Hy6qrXcLJg.png" style="width: 350px">
</center>
<p class="text-center">
下圖就是上圖的生成樹
</p>

### 常見的生成樹例子
#### 深度優先搜尋樹 DFS Tree
[深度優先搜尋 (DFS)](https://hackmd.io/@ShanC/bfs_dfs) 會訪問圖上的所有節點。事實上將走訪路徑保留後，可以連接所有節點形成一顆生成樹

#### 廣度優先搜尋樹 BFS Tree
相同地，BFS 也後產生一顆生成樹。此生成樹會有一個性質 : 根節點所有其他點的距離為最短

#### 最短路徑樹
對於一張帶權圖，若利用 Dijkstra's algorithm，由於一定會遍歷整張圖的所有節點，因此肯定會形成一棵生成樹。而如果將出發點 $s$ 視為根，那麼 $s$ 到所有點的路徑邊權總和最小 (俗稱路徑最短)

## Prüfer Code
上面介紹完生成樹，可以得知一張圖的生成樹可以有很多種，但是具體來說有幾種呢? 既然圖是一種有限結構，那生成樹的數量也應該是有限的吧! 那具體來說是幾種呢?

直接算真的非常困難，所以我們可以先把所有的樹都編成一組 Prüfer Code，說明 Prüfer Code 與生成樹是 bijection。如此一來，算 Prüfer Code 的數量就等於數生成樹的數量。這樣就可以導出一個公式 (Cayley's Formula) 來解決這個問題

備註 : 這裡我們討論的節點都有**數字標籤**

### 演算法
#### 輸入
一棵樹 $T$。其中，節點集合 $S=[n]=\{1, ..., n\}\subseteq \mathbb{N}$

#### 輸出
一個由節點標籤組成的序列 $f(T)=(a_1, a_2, ..., a_{n-2})$。其中，序列長度為 $n - 2$

#### 過程
1. 給一個圖 $T$、維護序列 $f(T)$
2. 總共迭代 $n-2$ 次
3. 在第 $i$ 次迭代時，把葉子中編號最小節點的鄰居當作 $a_i$，並刪掉葉子中編號最小節點

### 舉例說明

給一張 $7$ 個節點的樹、$f(T)=()$:

<center>
<img src="https://hackmd.io/_uploads/BkOv_IW4xg.png" style="margin: 0 auto; display: block; width: 400px">
</center>

$~$
刪除 $2$、$f(T)=(7)$:

<center>
<img src="https://hackmd.io/_uploads/SylZFLbVxx.png" style="margin: 0 auto; display: block; width: 400px">
</center>

$~$
刪除 $3$、$f(T)=(7, 4)$:

<center>
<img src="https://hackmd.io/_uploads/rJsHKLbEgl.png" style="margin: 0 auto; display: block; width: 400px">
</center>

$~$
刪除 $5$、$f(T)=(7, 4, 4)$:

<center>
<img src="https://hackmd.io/_uploads/rJq5YUZVxg.png" style="margin: 0 auto; display: block; width: 400px">
</center>

$~$
刪除 $4$、$f(T)=(7, 4, 4, 1)$:

<center>
<img src="https://hackmd.io/_uploads/BkgfqL-4eg.png" style="margin: 0 auto; display: block; width: 300px">
</center>

$~$
刪除 $6$、$f(T)=(7, 4, 4, 1, 7)$:

<center>
<img src="https://hackmd.io/_uploads/By6KcLbNlg.png" style="margin: 0 auto; display: block; width: 250px">
</center>

$~$
刪除 $7$、$f(T)=(7, 4, 4, 1, 7, 1)$:

<center>
<img src="https://hackmd.io/_uploads/HJ7es8bEge.png" style="margin: 0 auto; display: block; width: 125px">
</center>

刪到只剩 $2$ 個節點就可以停了
輸出 : 序列 $(7, 4, 4, 1, 7, 1)$

藉由這個演算法，可以知道每棵生成樹都會對應一個序列，接下來你可能會好奇這個序列是否代表唯一的生成樹，事實上答案是肯定的。下一段 Cayley's Formula 的證明中，會證明這件事

## Cayley's Formula

### 公式
對於具有標籤 $[n]=\{1,...,n\}$ 的節點集合，總共有 $n^{n-2}$ 棵樹 ($n\geq 2$)

### 舉個例子
當 $n=3$ 時，樹的數量為 $3^{3-2}=3$

<center>
<img src="https://hackmd.io/_uploads/BkZ368-Ngx.png" style="margin: 0 auto; display: block; width: 500px">
</center>

注意 : 雖然三棵樹是同構 (isomorphism)，但因為編號不同，所以要視為三種不同生成樹

### 證明
首先推一下 Prüfer Code 總共有多少種可能 :

已知 Prüfer Code 長度為 $n - 2$，序列每個位置可以填入 $n$ 種數字標籤，因此共有 $n^{n-2}$ 種可能

<center>
<img src="https://hackmd.io/_uploads/HyCnjacExe.png" style="margin: 0 auto; display: block; width: 500px">
</center>

$~$

接下來使用歸納法證明 Prüfer Code 與生成樹是 bijection :

令 $S^{n-2}$ 為序列的集合，$S\subseteq \mathbb{N}$ 是大小為 $n$ 的節點集合

Basis step : 當 $n=2$
存在一個 $2$ 節點的樹，其序列長度為 $0$，是唯一的空序列

Induction step : 當 $n\gt 2$
假設給定一個節點集合 $S$ 與序列 $a$，存在一個唯一的 $T$ 使得 $f(T)=a$
令第一個被刪除的葉節點叫 $x$。根據演算法，我們會紀錄 $a_1$ 在序列中，也就是 $x$ 的唯一鄰居，因此 $T$ 存在一條邊 $xa_1$。在刪除 $x$ 後，樹的節點集合變成 $S'=S-\{x\}$，然後序列 $a'=(a_2, ..., a_n)$
根據歸納假設，僅存在一棵節點集合為 $S'$ 樹 $T'$ 使得 $f(T')=a'$
因為每棵序列為 $a$ 的樹都有加上 $xa_1$，所以僅存在最多一個可能使 $f(T)=a$。再者，將 $T'$ 加上 $xa_1$ 會形成節點集合 $S$ 與序列 $a$，所以這就是那唯一的可能

由於樹和 Prüfer Code 是 bijection。Prüfer Code 的數量是 $n^{n-2}$，那麼樹的數量也是 $n^{n-2}$

## 一些拓展
### 公式 : 固定 degree 的情況下求有幾棵樹
給定一些整數 $d_1, d_2, ..., d_n$，加起來為 $2n-2$
總共有 $\cfrac{(n-2)!}{\Pi (d_i-1)!}$ 棵節點集合為 $[n]$ 的樹使每個節點 $i$ 都有度數為 $d_i$

### 推導

在序列中，每個元素 $x$ 都會出現 $d_x-1$ 次，因為在演算法中我們會把與其相連的葉節點都刪掉，直到 $x$ 成為葉節點或是成為最後兩個的其中一個節點。因此，在長度為 $n-2$ 的序列中，每個元素 $i$ 都出現了 $d_i-1$ 次。當我們隨便亂生一個串，總共會有 $(n-2)!$ 個序列，但其中有重複的，所以要除掉 $\Pi (d_i-1)!$ 次

其實也可以寫成 multinomial coefficient 的形式

$$
\cfrac{(n-2)!}{(d_1-1)!(d_2-1)!... (d_n-1)!}=\dbinom{n-2}{d_1-1, d_2-1, ..., d_n-1}
$$

### 公式 : 求讓圖連通的方法數

給定 $k$ 個連通塊的大小 $s_1, s_2, ..., s_k$，總節點數為 $\sum ^{k}_{i=1}s_i=n$
讓圖連通的方法數 : $n^{k-2}~\Pi^k_{i=1} s_i$

### 推導
我不會，但[這篇](https://cp-algorithms.com/graph/pruefer_code.html)有寫 (因為他重複使用變數，而且步驟有點跳，所以我看不懂)

## 另一種推導 Cayley's Formula 的方法
因為最近學了生成函數 (generating function)，所以給出用生成函數推導的方法

### 推導
計算 $n$ 個點上有根樹的數量叫 $t(n)$，若移除了根並觀察子樹，會得到一個遞迴式
||天啊這要怎麼觀察||

$$
t(n+1)=(n+1)\sum_{k\geq 0}\sum_{i_1+i_2+...+i_k=n, i_j\geq1}\frac{n!}{i_1!i_2!...i_k!} t(i_1)t(i_2)...t(i_k) \frac{1}{k!}
$$

乘上 $x^{n+1}$ (因為我們要搞生成函數)，然後整理一下
$$
\frac{t(n+1)}{(n+1)!}x^{n+1}=\sum_{k\geq 0}\frac{1}{k!}\sum_{i_1+i_2+...+i_k=n, i_j\geq1}\frac{t(i_1)x^{i_1}}{i_1!}\frac{t(i_2)x^{i_2}}{i_2!}...\frac{t(i_k)x^{i_k}}{i_k!}
$$

這就會是我們的生成函數 $T(x)$ 囉!! (最下面的等式是用泰勒展開搞回去)
$$\begin{split}
T(x)&=\sum_{n\geq 0}\frac{t(n+1)}{(n+1)!}x^{n+1}=\sum_{k\geq 0}\frac{1}{k!}\sum_{n\geq 0}\sum_{i_1+i_2+...+i_k=n, i_j\geq1}\frac{t(i_1)x^{i_1}}{i_1!}\frac{t(i_2)x^{i_2}}{i_2!}...\frac{t(i_k)x^{i_k}}{i_k!}
\\&=x\sum_{k\geq 0} \frac{T(x)^k}{k!}
\\&=xe^{T(x)}
\end{split}
$$

接下來把有 $T(x)$ 的都放到左邊
$$
T(x)e^{-T(x)}=x
$$

因為它長的很像拉格朗日反演的樣子，所以我們弄弄看拉格朗日反演公式
然後再平移一下多項式
$$\begin{split}
[x^n]T(x)&=\cfrac{1}{n}[x^{-1}]\cfrac{1}{(xe^{-x})^n}
\\&=\cfrac{1}{n}[x^{-1}]x^{-n}e^{nx}
\\&=\cfrac{1}{n}[x^{n-1}]e^{nx}
\\&=\cfrac{1}{n}\cfrac{n^{n-1}}{(n-1)!}
\\&=\cfrac{n^{n-1}}{n!}
\end{split}
$$

因此，$$t(n)=n^{n-1}$$
最後，因為我們算的是有根的樹，但答案應該要是沒有根的樹，因此要除掉一個 $n$
得到 $n^{n-2}$ 為有標籤的節點所能形成的樹的數量

## 克希荷夫矩陣樹定理 Kirchhoff's Matrix Tree Theorem
克希荷夫的矩陣樹定理可以求出給定一張圖 $G$ 的生成樹數量。若要理解其方法，需要先知道要怎麼用矩陣玩圖論。這種用線性代數玩圖論的領域叫做 Spectual Graph Theory

首先，這裡的圖都假設連通，否則沒辦法討論其生成樹

### 鄰接矩陣 Adjancency Matrix
這應該資料結構就學過了，放在數學裡也是一樣

鄰接矩陣 $A\in \mathbb{R}^{N\times N}$ 是一個方陣。對於每個 $A_{i, j}$ 代表點對 $(i, j)$ 之間的邊數，其中有幾種性質
- 允許自環，每個自環會在對角線上的元素貢獻 $2$
- 鄰接矩陣在無向圖是對稱的矩陣

### 度數矩陣 Degree Matrix
度數矩陣 $D\in\mathbb{R}^{N\times N}$ 是一個對角矩陣。對於每個節點 $i$，$D_{i, i}$ 代表其度數，除了對角以外的部分皆為 $0$。其中，自環對度數貢獻為 $2$

### 拉普拉斯矩陣 Laplacian Matrix
拉普拉斯矩陣 $$L=D-A$$

有學過向量微積分的話應該很熟悉拉普拉斯運算子，就是梯度的散度那個，它本質上就是相鄰減自身，通通加總，並除掉一個分母。拉普拉斯矩陣也有相似的概念，只是不知道為什麼反過來了

### 餘因式 Minor
令 $B$ 為一個方陣，$B$ 的 minor $M_{i, j}$ 是一個消除第 $i$ 列第 $j$ 行後的矩陣的行列式

### 餘因子 Cofactor
在上一個定義中，$B$ 的 cofactor 為 $$C_{i, j}=(-1)^{i+j}M_{i, j}$$

### 引理 1
令 $L$ 為某張無向圖的拉普拉斯矩陣，則所有 $L$ 的 minor 套上絕對值後都相同

### 引理 2
令 $L$ 為某張無向圖的拉普拉斯矩陣，則所有 $L$ 的 cofactor 都相同

### 邊收縮 Contraction
如下圖，收縮後的圖 $G.e$

<center>
<img src="https://hackmd.io/_uploads/SyF5TFoExx.png" style="margin: 0 auto; display: block; width: 300px">
</center>

### 矩陣樹定理 Matrix Tree Theorem
給定一張無向圖 $G=(V, E)$，對於任何節點 $i, j\in\{1, 2, ..., |V|\}$，$G$ 的生成樹數量為 $\tau(G)=C_{i, j}$

### 證明概述
證明有很多版本，這裡採用我比較看得懂的版本，因為太複雜所以大概說一下就好
||可能有點不太嚴謹||

因為圖都是連通的，考慮一條邊 $e$，當我們在找生成樹的時候，$e$ 要嘛在樹上要嘛不在 (廢話)。若 $e$ 在樹上，則我們不用考慮他，可以使用邊收縮並找出 $G.e$ 的生成樹數量。若 $e$ 不在樹上，相當於我們忽略它，因此就是要找 $G-e$ 的生成樹數量。因此，可以得到 $\tau(G)=\tau(G-e)+\tau(G.e)$ ||有點像是對圖做遞迴的感覺||

<center>
<img src="https://hackmd.io/_uploads/BJEgQcoVxx.png" style="margin: 0 auto; display: block; width: 300px">
</center>

$~$
我們可以對邊做歸納法

Basis case : 整張圖只有兩點與他們之間的 $d$ 條邊

$L=\left(
\begin{array}{cc}
d & -d \\
-d & d \\
\end{array}
\right)$，所以 $\tau(G)=C_{1, 1}=L_{1, 1} = d$

歸納假設 : 假設對 $G-e$ 與 $G.e$，定理都為真
Inductive step : 我們希望證明定理在 $\tau(G)$ 時為真
將兩節點 $i, j$ 特別挑出來，令 $d_i, d_j$ 為度數，$d$ 為 $i, j$ 之間的邊數，則我們可以整理出以下行列式。其中，$r_i$ 與 $r_j$ 是紀錄 $i, j$ 的相關訊息，$L'$ 是拉普拉斯矩陣中沒動到的其他部分

$$
det(L^G)=\left|
\begin{array}{ccc}
d_i & -d & r_i^T \\
-d & d_j & r_j^T\\
r_i & r_j & L' \\
\end{array}
\right|
$$

當然我們也可以整理出 $G-e$ 的行列式

$$
det(L^{G-e})=\left|
\begin{array}{ccc}
d_i - 1 & -d + 1 & r_i^T \\
-d + 1 & d_j - 1 & r_j^T\\
r_i & r_j & L' \\
\end{array}
\right|
$$

還有 $G.e$ 的行列式

$$
det(L^{G.e})=\left|
\begin{array}{cc}
d_i+d_j-2 & r_i^T+r_j^T \\
r_i+r_j & L' \\
\end{array}
\right|
$$

根據引理 1, 2，取 $i, i$ 也會是答案。為了結束歸納法，我們說明
$$
det(L^G_{i, i})=det(L_{i, i}^{G-e})+det(L^{G.e}_{i, i})
$$

也就是
$$
\left|
\begin{array}{cc}
d_j & r_j^T\\
r_j & L' \\
\end{array}
\right|=\left|
\begin{array}{cc}
d_j - 1 & r_j^T\\
r_j & L' \\
\end{array}
\right|+\left|\begin{array}{cc}
L'
\end{array}
\right|
$$

這可以用 Laplace expansion 展開來證

最後，根據歸納假設，因為定理在 $G-e$ 與 $G.e$ 為真，因此在 $G$ 也為真
所以 $$C^G_{i, i}=C^{G-e}_{i, i}+C^{G.e}_{i, i}=\tau(G-e)+\tau(G.e)=\tau(G)$$

### 舉例說明

下圖總共有八種生成樹

<center>
<img src="https://hackmd.io/_uploads/r1ytg6jEex.png" style="margin: 0 auto; display: block; width: 200px">
</center>

$~$
當然我們也可以用矩陣樹定理算出來

$$
A=\left(
\begin{array}{cccc}
0 & 1 & 1 & 0\\
1 & 0 & 1 & 1\\
1 & 1 & 0 & 1\\
0 & 1 & 1 & 0\\
\end{array}
\right),~
D=\left(
\begin{array}{cccc}
2 & 0 & 0 & 0\\
0 & 3 & 0 & 0\\
0 & 0 & 3 & 0\\
0 & 0 & 0 & 2\\
\end{array}
\right),
~L=\left(
\begin{array}{cccc}
2 & -1 & -1 & 0\\
-1 & 3 & -1 & -1\\
-1 & -1 & 3 & -1\\
0 & -1 & -1 & 2\\
\end{array}
\right)
$$

將第 $2$ 行第 $2$ 列刪掉得到 $L_{2, 2}=\left(
\begin{array}{ccc}
2 & -1 & 0\\
-1 & 3 & -1\\
0 & -1 & 2\\
\end{array}
\right)$

$$
\begin{split}
det(L')&=\left|
\begin{array}{ccc}
2 & -1 & 0\\
-1 & 3 & -1\\
0 & -1 & 2\\
\end{array}
\right|
=2\left|
\begin{array}{ccc}
3 & -1\\
-1 & 2\\
\end{array}
\right|+\left|
\begin{array}{ccc}
-1 & -1\\
0 & 2\\
\end{array}
\right|
=2\times 5 - 2
=8
\end{split}
$$

### 導出 Cayley's Formula
Cayley's Formula 的條件與矩陣樹定理的條件有點不同
- Cayley's Formula : 有標籤的節點集合
- 矩陣樹定理 : 一張圖 $G$

若把矩陣樹定理給的 $G$ 換成完全圖 $K_n$，那就相當於變成 Cayley's Formula 的條件，所以就可以計算拉普拉斯矩陣

$$
D^{K_n}=\left(
\begin{array}{cc}
n & n & \dots & n\\
n & n & \dots & n\\
\vdots & \vdots & \ddots & \vdots\\
n & n & \dots & n
\end{array}
\right)
,~A^{K_n}=\left(
\begin{array}{cc}
1 & 1 & \dots & 1\\
1 & 1 & \dots & 1\\
\vdots & \vdots & \ddots & \vdots\\
1 & 1 & \dots & 1
\end{array}
\right)
$$

$$
L^{K_n}=D^{K_n}-A^{K_n}=\left(
\begin{array}{cc}
n-1 & -1 & \dots & -1\\
n & n-1 & \dots & -1\\
\vdots & \vdots & \ddots & \vdots\\
-1 & -1 & \dots & n-1
\end{array}
\right)
$$

然後再找出 cofactor $C_{i, j}$ (刪哪行哪列都一樣)，其中 cofactor 的大小只有 $(n-1)\times(n-1)$

$$
C^{K_n}_{i, j}=\left|
\begin{array}{cc}
n-1 & -1 & \dots & -1\\
-1 & n-1 & \dots & -1\\
\vdots & \vdots & \ddots & \vdots\\
-1 & -1 & \dots & n-1
\end{array}
\right|
$$

這個鬼東西並不好求，所以可以考慮找 eigenvalue。其中，我們需要用到以下性質 :
- 矩陣行列式就是所有 eigenvalue 相乘
- 矩陣的 trace 是其 eigenvalue 之和
- 若 $\lambda$ 是矩陣 $A$ 的 eigenvalue，則 $\lambda + c$ 是 $A + cI$ 的 eigenvalue

令 $L^i$ 是這個 $(n-1)\times (n-1)$ 矩陣，考慮 $L^{i}-nI$ 是一個所有元素都是 $-1$ 的矩陣
- 觀察 trace 會等於 $(-1)\times (n-1)=1-n$ 又等於所有 eigenvalue 之合
- 所以可以得到 $L^{i}-nI$ 的所有 eigenvalue 中只有一個是 $1-n$，其他都是 $0$
- 因此所有的 eigenvalue 就是剛才的結果加 $n$，也就是 $1, n, ..., n$，共 $n-2$ 個 $n$ 與 $1$ 個 $1$
- 將它們所有 eigenvalue 乘起來就會是行列式的答案，也就是 $n^{n-2}$

答案就這樣莫名其妙地算出來了

## 備註
這些東西一出現就肯定是難題，通常跟什麼 generating function、stirling numbers 等等噁心的東西一起出現，所以建議去學 Combinatorics 或是讀 Generatingfunctionology (一本書)

## 題目練習

[Zerojudge g088. 生成樹數量](https://zerojudge.tw/ShowProblem?problemid=g088) (奇怪的東西)
[OnlineJudge 10843 - Anne's game](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=20&page=show_problem&problem=1784) (Cayley's formula 裸題)
[Codeforces 156 D. Clues](http://codeforces.com/contest/156/problem/D) (拓展 Cayley's formula)
[CSES Prüfer Code](https://cses.fi/problemset/task/1134/) (Prüfer Code 裸題)
[Codeforces 917 D. Stranger Trees](https://codeforces.com/problemset/problem/917/D?locale=en) (做法很多，要想一下)
[Codeforces 1762 E. Tree Sum](https://codeforces.com/problemset/problem/1762/E) (動動腦)
[CSES Functional Graph Distribution](https://cses.fi/problemset/task/2415) (Cayley's formula，好像也要用 Stirling number，神奇的數學題)
[ABC 253 Ex - We Love Forest](https://atcoder.jp/contests/abc253/tasks/abc253_h) (矩陣樹定理 + 位元 DP)
[ABC 323 G - Inversion of Tree](https://atcoder.jp/contests/abc323/tasks/abc323_g) (矩陣樹)
[Atcoder jsc2021 G - Spanning Tree](https://atcoder.jp/contests/jsc2021/tasks/jsc2021_g) (矩陣樹)

----

## 參考資料
- D.B.West - Introduction to Graph Theory 2/e
- [CP-algorithms - Prüfer code](https://cp-algorithms.com/graph/pruefer_code.html)
- [Geeksforgeeks - Cayley's Formula](https://www.geeksforgeeks.org/cayleys-formula/)
- [[Tutorial] Generating Functions in Competitive Programming (Part 2)](https://codeforces.com/blog/entry/77551)
- [師大演算法筆記 - graph spectrum](https://web.ntnu.edu.tw/~algo/GraphSpectrum.html)

----

> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2025/6/25