# 離散數學 筆記

集合論
---

* 常見集合 記起來
1. $N=\{0,1,2,...\}$，所有自然數集合
2. $Z$，所有整數集合，$Z^+$，所有正整數集合(不含0)，$Z^*$，非零整數集合
3. $Q$，所有有理數集合，$Q^+$，所有正有理數集合，$Q^*$，非零有理數集合
4. $R$，實數集合，$R^*$，非零實數集合
5. $C$，所有複數集合

* **Empty set**: $D=\{\}$，或$\emptyset$，**空集合為任何集合的子集合**。

* $\emptyset \neq \{\emptyset\}$，前者不包含元素，後者包含一個元素

* **Subset**: $A\subseteq B$ 代表，$\forall x(x\in A \Rightarrow x\in B)$
**Proper subset**: 若$A\subseteq B$且$A\neq B$，則$A\subset B$，代表A是B的真子集

* <img src="https://i.imgur.com/21bNV5X.png">

* $x\in A \Leftrightarrow \{x\}\in A$

* **差集(difference)**: $A-B=\{x|x\in A且x\notin B\}$。$A-B=A\bigcap \overline{B}$

* **對稱差(symmetric difference)**: $A\bigoplus B=(A\bigcup B)-(A\bigcap B)=(A-B)\bigcup (B-A)$

* <img src="https://i.imgur.com/HXhwYSW.png">

* 用文式圖練習集合各項觀念

* $A\bigcup (A\bigcap B)=A\bigcap (A\bigcup B)=A$

* $(A\oplus B)\oplus C=A\oplus (B\oplus C)$

* $A\bigcap (B\oplus C)=(A\bigcap B)\oplus (A\bigcap C)$

* **Cardinality**: 一個集合中相異元素的個數，$|A|$

* $|\overline{A}\bigcap \overline{B}|=|\overline{A\bigcup B}|=|U|-|A\bigcup B|=|U|-|A|-|B|+|A\bigcap B|$

* <img src="https://i.imgur.com/HqRG0N2.jpg">

* **Power set(冪集合)**: $P(A)=\{X|X\subseteq A\}$，也記做$2^A$，代表A所有子集合形成的集合

* $|A|=n,|P(A)|=2^n$

* $P(A_n)=P(A_{n-1}) \bigcup \{ \bigcup \{a_n\}|X\in P(A_{n-1})\}$，$P(A_n)$可以由$P(A_{n-1})$還有${a_n}$與$P(A_{n-1})$的連集組成

* $|P(A_n)|=2|P(A_{n-1})|$，也可以知道$A_n$中**含有偶數個元素的子集數目與含有奇數個元素的子集數目相同**，$2^{n-1}$

* <img src="https://i.imgur.com/x0tQEzX.png">

* <img src="https://i.imgur.com/oBDKoDF.png">

* **Cartesian product**: $A\times B=\{(a,b)|a\in A,b\in B\}$
$|A\times B|=|A||B|$
$A\times \emptyset=\emptyset$

數學歸納法
---

* **well ordering principle**
$Z^+$的每個非空子集必包含最小元素

* <img src="https://i.imgur.com/IGrg4Lz.png">

* <img src="https://i.imgur.com/GMTBekX.png">

* <img src="https://i.imgur.com/0wvh39K.png">

* <img src="https://i.imgur.com/iD1Zg5G.png">

* <img src="https://i.imgur.com/v4jog24.png">

基礎數論
---

* $\lfloor x+n \rfloor=\lfloor x \rfloor+n,\forall n\in Z$

* $\lfloor x \rfloor + \lfloor y \rfloor \le \lfloor x+y \rfloor \le \lfloor x \rfloor + \lfloor y \rfloor +1$

* $\lfloor x\rfloor + \lfloor -x\rfloor=\begin{cases}
0, \ if \ x\in Z\\
-1,otherwise
\end{cases}$

* $\lfloor -x \rfloor=-\lceil x \rceil,\lceil -x \rceil=-\lfloor x \rfloor$

* $n\in Z,\begin{cases}
x<n \Leftrightarrow \lfloor x \rfloor <n\\
n<x \Leftrightarrow n< \lceil x \rceil\\
x\le n \Leftrightarrow \lceil x \rceil \le n\\
n\le x \Leftrightarrow n\le \lfloor x \rfloor\\
\end{cases}$

* 若$n\in Z^+$且$n$為composite，則存在一質數$p,p|n$，且必存在一個質因數$m\le \sqrt{n}$ (證明)

* $Z^+$中有無限多個質數 (證明)

* 一個數字不是質數就是組合數，可以透過否定一個數為組合數來證明它是質數

* **代數基本定理** $n\in Z^+,n\ge 2$，n可唯一寫成若干質數的乘積，也就是n的質因數分解唯一

* **Congruence**: 同餘，若$n|(a-b)$，則$a\equiv b(mod \ n)$

* $a\equiv b(mod \ n)$ iff $a=b+kn$ iff $a \ mod \ n = b \ mod \ n$

* 若$a\equiv b(mod \ n),c\equiv d(mod \ n)$，則$a+c\equiv b+d(mod \ n),ac\equiv bd(mod \ n)$

* $(a+b) \ mod \ n = ((a \ mod \ n)+(b \ mod \ n)) \ mod \ n$ (證明)

* $ab \ mod \ n = ((a \ mod \ n)(b \ mod \ n)) \ mod \ n$ (證明)

* <img src="https://i.imgur.com/I6WJZMt.png">

* **Euclidean Algorithm**
$m,n\in Z$且$m=nq+r,gcd(m,n)=gcd(n,r)$也就是$gcd(m,n)=gcd(n,m \ mod \ n)$ (證明)

* <img src="https://i.imgur.com/nDtx5z8.png">

* 若$m,n\in Z,g=gcd(m,n)$，則$\{ms+nt|s,t\in Z\}=\{gx|x\in Z\}$ (證明)

* $ax+by=c$有整數解$x=x_0,y=y_0$ iff $gcd(a,b)|c$

* 若$p$為質數且$p|n_1n_2...n_k$，則$p|n_i$,for some $1\le i\le k$ (可用此證明代數定理唯一性)

* $a\in Z,n\in Z^+$，若存在$x\in Z,ax\equiv 1(mod \ n)$，則x為a在模n下的乘法反元素(multiplicative inverse)，滿足此條件的最小正整數x稱為least multiplicative inverse，記做$a^{-1}(mod \ n)$

* 若$gcd(a,n)=1$，則$a$在模$n$下的乘法反元素存在

* $a$為$a$在模$p$底下的乘法反元素iff $a\equiv \pm 1(mod \ p)$

* **Wilson's theorem**
假設$p$為一個質數，則$(p-1)!\equiv -1(mod \ p)$，反之亦然

* 若$gcd(c,n)=1$,則$ac\equiv bc(mod \ n) \Leftrightarrow a\equiv b(mod \ n)$

* **Fermat's little theorem**
$m\in Z$且$p$為質數，$gcd(m,p)=1$，則$m^{p-1}\equiv 1(mod \ p)$ (證明)
透過下一個定理就能證明，當n為質數的時候$\phi(n)=n-1$

* **Euler's totient function**
$\phi (n)$代表$\{1,2,3,...,n-1\}$當中跟$n$互質的元素個數
$n=p_1^{e_1}...p_k^{e_k}$為$n$的質因數分解
$\phi (n)=n\prod _{j=1}^{k}(1-\cfrac{1}{p_j})$
$\phi (p)=p-1 \Leftrightarrow p$為質數

* $m\in Z,n\in Z^+,gcd(m,n)=1$，則$m^{\phi (n)}\equiv 1(mod \ n)$ (證明)
$m^{-1}\equiv m^{\phi(n)-1}(mod \ n)$

<img src="https://i.imgur.com/WtKu5Ws.png">

* **Chinese remainder Theorem**
$n_i\in N,r_i\in Z,i=1,...,k$，$n_1,..,n_k$彼此互質
$x\equiv r_1(mod \ n_1)$
...
$x\equiv r_k(mod \ n_k)$
在mod $n=n_1n_2...n_k$下具有唯一解 (證明)

* 取$x=\sum_{j=1}^kr_jM_jN_j \ (mod \ n)$，先加完再取mod，$N_j=n/n_j,M_j=N_j^{-1}(mod \ n_j)$

關係
---

* $A,B$為兩個集合，$A\times B$的任一個子集$R$，都稱為A到B的一個Relation，當B=A時，$R\subseteq A\times A$，稱為A上的binary relation

* $R=\emptyset$，empty relation
$R=A\times B$，total relation

* $R\subseteq A\times B \Leftrightarrow R\in P(A\times B)$

* $|P(A\times B)|=2^{|A||B|}$

* **Composition Relation**
$R\subseteq A\times B,S\subseteq B\times C$
$RS=S。R$
$\forall a\in A,c\in C,(a,c)\in S。R \Leftrightarrow \exists b\in B,(a,b)\in R,(b,c)\in S$

* $(R_1R_2)R_3=R_1(R_2R_3)$

* $M_{S。R}=M_{RS}=M_RM_S$

* $R^0=\{(a,a)|a\in A\}$，$M_{R^n}=(M_R)^n$

* **Inverse Relation**
$\forall b\in B,a\in A,b \ R^{-1} \ a \Leftrightarrow a \ R \ b$

* $(R^{-1})^{-1}=R$
$R\subseteq S \Leftrightarrow R^{-1}\subseteq S^{-1}$
$M_{R^{-1}}=M_R^T$

* **Complement Relation**
$\forall a\in A,b\in B,a\overline{R}b\Leftrightarrow (a,b)\notin R$

* $M_{R\bigcap S}=M_R\wedge M_S,M_{R\bigcup S}=M_R\vee M_S$

基本關係
---

* **Reflexive relation**: $(a,a)\in R,\forall a\in A$
**Irreflexive relation**: $(a,a)\notin R,\forall a\in A$

* 若R具反身性($M_R$對角項皆為1)，則R不具非反身性，反之未必成立
R具非反身性($M_R$對角項皆為0)，則R不具反身性，反之未必成立

* **Symmetric**: $\forall a,b\in A,aRb \Rightarrow bRa$
**Asymmetric**: $\forall a,b\in A,aRb\Rightarrow b\mathrm{R}a$
**Antisymmetric**: $\forall a,b\in A,aRb,bRa\Rightarrow a=b$

* **Transitive**: $\forall a,b,c\in A, aRb\wedge bRc\Rightarrow aRc$

* $R$具遞移性$\Leftrightarrow R^2\subseteq R$

* $R$具遞移性$\Leftrightarrow R^n\subseteq R,\forall n=1,2,3...$

* 若$R,S$具反身性，則$R\bigcap S$及$R\bigcup S$具反身性
若$R,S$具對稱性，則$R\bigcap S$及$R\bigcup S$具對稱性
若$R,S$具遞移性，則$R\bigcap S$具遞移性

* <img src="https://i.imgur.com/7FLU7Kh.png">

* 若$|A|=n$，則$A$為以下關係的個數為

等價關係
---

* $R$同時具反身性、對稱性、遞移性，則稱為等價關係Equivalence relation

* **Equivalence class**: 假設$R\subseteq A\times A$為$A$上的一個等價關係，$\forall a\in A,[a]=\{x\in A|xRa\}$，表示與a具有R關係的所有元素的集合，稱為相對於a的等價類

* 假設$R\subseteq A\times A$為等價關係，$\forall a,b\in A,aRb\Leftrightarrow [a]=[b]$ (證明)

* **分割**: $A$為一個集合，$\emptyset \neq A_i\subseteq A,i=1,..,n$，若$\bigcup_{i=1}^{n}A_i=A$且$A_i\bigcap A_j=\emptyset,\forall i\neq j$，則稱$\{A_1,..,A_n\}$形成A的一個Partition，$A_i$稱為block

* $R\subseteq A\times A$為A上的等價關係，$P=\{[a]|a\in A\}$形成A的一個分割 (證明)

* **給定A上的一個等價關係，與他對應的相異等價類形成A的一個分割，給定A的一個分割，可造出一個A上的等價關係使其相異等價類為此分割，A上的等價關係與A上的分割一一對應**

* **同餘關係**: $\forall a,b\in Z,a\equiv_nb \Leftrightarrow a\equiv b \ (mod \ n)$

* 同餘關係為等價關係

* $\equiv_n$造出$[0],[1],..,[n-1]$這些n個相異等價類

* $P_i$表示i個元素上相異的等價關係個數，$P_n=\sum_{i=0}^{n-1} \dbinom{n-1}{i}P_i,\ P_0=1$

* <img src="https://i.imgur.com/5j3ddMK.png">

關係的包
---

* $r(R)$標示包含$R$的最小反身關係，稱為$R$的reflexive closure
$s(R)$標示包含$R$的最小對稱關係，稱為$R$的symmetric closure
$r(R)$標示包含$R$的最小遞移關係，稱為$R$的transitive closure

* $r(R)=R\bigcup R^0,M_{r(R)}=M_R \vee I$
$s(R)=R\bigcup R^{-1},m_{s(R)}=M_R\vee M_{R^{-1}}=M_R\vee M_R^T$
$t(R)=R^+=\bigcup_{k=1}^{\infty}R^k$
$t(s(r(R)))$必為等價關係，稱為equivalence closure

* $R_1,R_2$為等價關係，$R_1\bigcap R_2$仍為等價關係，$R_1\bigcup R_2$未必具遞移關係，所以也未必為等價關係

* 取$t(R_1\bigcup R_2)$使它具有等價關係，$t(R_1\bigcup R_2)$也為$R_1\bigcup R_2$的等價包

* $R_1,R_2$對應的分割為$\pi_1,\pi_2$
$R_1\bigcap R_2$對應的分割為$\pi_1\cdot \pi_2$
$t(R_1\bigcup R_2)$對應的分割為$\pi_1+\pi_2$

* <img src="https://i.imgur.com/iOCWHtO.png">

函數
---

* $A,B\neq \emptyset,f\subseteq A\times B$，滿足$\forall a\in A$，唯一存在$b\in B$使得$a\ f\ b$

* $A_1\subseteq A,f(A_1)=\{f(a)|a\in A_1\}$，稱為$A_1$在$f$底下的直像

* 兩函數相等的充要條件
1. f的domain=g的domain
2. f的range=g的range
3. 對domain內任一個元素x滿足f(x)=g(x)

* 若$\forall a_1,a_2\in A,a_1\neq a_2 \Rightarrow f(a_1)\neq f(a_2)$，也就是$f(a_1)=f(a_2) \Rightarrow a_1=a_2$，則f為一對一函數

* 若$f:A\rightarrow B,f(A)=B$，則f為映成函數，$\forall b\in B,\exists a\in A$使得$f(a)=b$

* $f:A\rightarrow B,A_1,A_2\subseteq A$
1. 若$A_1\subseteq A_2,f(A_1)\subseteq f(A_2)$
2. $f(A_1\bigcup A_2)=f(A_1)\bigcup f(A_2)$
3. $f(A_1\bigcap A_2)\subseteq f(A_1)\bigcap f(A_2)$

* $f$為一對一函數 $\Leftrightarrow f(A_1\bigcap A_2)=f(A_1)\bigcap f(A_2),\forall A_1,A_2\subseteq A$ (證明)

* $f:A\rightarrow B,g:B\rightarrow C$
1. 若$f,g$為一對一函數，則$g。f$也為一對一函數。反之，若$g。f$為一對一函數，必定保證$f$為一對一函數。
2. 若$f,g$為映成函數，則$g。f$也為映成函數。反之，若$g。f$為映成函數，必定保證$g$為映成函數。
3. 若$f,g$為可逆函數，則$g。f$也為可逆函數

* $f:A\rightarrow B,B_1\subseteq B$，則定義$f^{-1}(B_1)=\{a\in A|f(a)\in B_1\}$，$B_1$在$f$底下的反像(不需要f為可逆函數)

* $f:A\rightarrow B,B_1,B_2\subseteq B$
1. 若$B_1\subseteq B_2,f^{-1}(B_1)\subseteq f^{-1}(B_2)$
2. $f^{-1}(B_1\bigcup B_2)=f^{-1}(B_1)\bigcup f^{-1}(B_2)$
3. $f^{-1}(B_1\bigcap B_2)=f^{-1}(B_1)\bigcap f^{-1}(B_2)$
4. $f^{-1}(\overline{B_1})=\overline{f^{-1}(B_1)}$

鴿籠定理
---

* m隻鴿子欲飛入n個鴿籠中，其中m>n，則至少有一個鴿籠包含至少2隻鴿子

* 假設n個鴿籠，則至少要n+1隻鴿子才能保證某個鴿籠至少兩隻鴿子

* m隻鴿子飛入n個鴿籠中，m>n，則至少一個鴿籠包含$\lceil \cfrac{m}{n} \rceil$ 隻鴿子

計數問題
---

* 若$f: X\rightarrow Y$為一個函數，$|X|=m,|Y|=n,m,n<\infty$
1. 若$f$為one-to-one function，則$m\le n$
2. 若$f$為onto function，則$m\ge n$
3. 若$f$為one-to-one and onto function，則$m=n$

* $A,B\neq \emptyset,f: A\rightarrow B$為一個one-to-one and onto function，則$A\sim B$

* $\forall a,b,c,d\in R,a<b,c<d,[a,b]\sim [c,d]$

* $\sim$為一個等價關係

* 若$A=\emptyset$或$\exists n\in Z^+,A\sim \{1,2,...,n\}$，則稱$A$為finite set，否則為infinite set

* 若$A$為有限集或$A\sim Z^+$，則稱$A$為countable set，否則$A$為uncountable set

* 有限集必為可數，不可數集必為無限集，反之未必成立

* $Z$為可數集 (證明)

* $A\subseteq B$
1. 若$B$為可數集，則$A$亦為可數集
2. 若$A$為不可數集，則$B$亦為不可數集 (證明)

* 若$A$為無限集，若存在$f:A\rightarrow Z^+$為一對一函數，則$A$為可數集

* $Z^+\times Z^+\sim Z^+$

* 假設$A,B$為可數集，$A\times B$亦為可數集

* 可數集的聯集亦為可數集

* 所有正有理數的集合$Q^+$為可數集

* 所有有理數的集合$Q$為可數集

* $(0,1)$為不可數集

* $R$為不可數集且$(0,1)\sim R$

* $|N|=|Z|=|Q|<|\overline{Q}|=|R|$

排列組合
---

* n個相異物放在一個環形，排列數為$(n-1)!$

* <img src="https://i.imgur.com/5HTDnbu.png">

* $|A|=m,|B|=n$
1. 由A至B的函數個數為$n^m$，相當於m個相異物放到n個相異箱子允許空箱的方法數
2. 由A至B的一對一函數個數為$P_m^n$，相當於m個相異物放到n個相異箱子且每個箱子至多一個物品的方法數

* <img src="https://i.imgur.com/YFYp8vY.png">

* <img src="https://i.imgur.com/dk0gEZE.png">

* $\dbinom{n}{r}=\dbinom{n-1}{r-1} + \dbinom{n-1}{r}$ (證明)

* $\sum_{i=0}^n\dbinom{n}{i}=2^n$ (證明)

* $\sum_{k=0}^n\dbinom{r}{k}\dbinom{s}{n-k}=\dbinom{r+s}{n}$ (證明)

* $\sum_{k=0}^n\dbinom{n}{k}^2=\dbinom{2n}{n}$

* $(x_1+x_2+...+x_t)^n=\sum \dbinom{n}{n_1,n_2,...,n_t}x_1^{n_1}\cdot\cdot\cdot x_t^{n_t}$
$\dbinom{n}{n_1,...,n_t}=\cfrac{n!}{n_1!n_2!...n_t!}$

* n件相異物允許重複取r件組合的方法數 $\dbinom{n+r-1}{r}$
等價於r個相同球放入n個相異箱子允許空箱的方法數
$x_1+...+x_n=r$的非負整數解

* $1\le x_1 \le \cdots \le x_m \le n$，等價於n種相異物取m個且可以重複，等價於$y_1+\cdots+y_n=m$的非負整數解

$1\le x_1<\cdots<x_m\le n$，則是n個相異物取m個但不能重複

* r個相同球放入n個相異箱子不允許空箱的方法數 = $\dbinom{n-1+r-n}{r-n}=\dbinom{r-1}{r-n}=\dbinom{r-1}{n-1}$
$x_1+...+x_n=r$的正整數解

* <img src="https://i.imgur.com/ZXGHWeR.png">

* <img src="https://i.imgur.com/fSOwSMU.png">

* <img src="https://i.imgur.com/5GnY6WR.png">

*

排列組合與排容原理
---

* 假設下列符號，$S_i,i\ge 1$代表滿足i個性質的元素數量
$S_0=N$
$S_1=\sum_{i=1}^nN(a_i)$
$S_n=N(a_1a_2..a_n)$

* **排容原理**: $U$為宇集合，$N(\overline{a_1a_2...a_n})=\sum_{i=0}^n(-1)^iS_i$

* A到B的映成函數個數、m個相異物放到n個相異箱子不允許空箱:
onto(m,n) = $\sum^{n}_{i=0}{(-1)^i\dbinom{n}{i}(n-i)^m}$ (證明)

* **Stirling number of the second kind**、m個相異物放到n個相同箱子不允許空箱:
S(m,n) = $onto(m,n)/n!$
* $S(m,n)=S(m-1,n-1)+nS(m-1,n)$
m個相異物放到n個相同箱子，可以看成先把m-1個相異物
可以先建表，用S算onto

* **Stirling number of the first kind**、m個相異物安排成**恰好**n個環狀排列的方法數，$m\ge n$，[m,n] (課本有正確的標記方法 這裡寫不上去)
* m個相異物排成1個環狀排列為$(m-1)!=[m,1]$
* $[m+1,n] = [m,n-1] + m[m,n]$

* U為宇集和，有$a_1,...,a_n$，n個性質，$E_m$表示n個性質中**恰好**滿足m個性質的方法數，$L_m$表示**至少**滿足m個性質的方法數
$E_m = S_m - \dbinom{m+1}{1}S_{m+1} + \dbinom{m+2}{2}S_{m+2} -...+(-1)^{n-m}\dbinom{n}{n-m}S_n$

$L_m = S_m - \dbinom{m}{m-1}S_{m+1} + \dbinom{m+1}{m-1}S_{m+2} -...+(-1)^{n-m}\dbinom{n-1}{m-1}S_n$

亂序及禁位
---

* 亂序(derangement)，n個相異物排列，使的每個物品不在它的自然位置上(第i個物品不在位置i): $D_n = n!(\sum^{n}_{i=0}{\cfrac{(-1)^i}{i!}})$

* $n!=\sum_{k=0}^{n}\dbinom{n}{k}D_k$

* $D_n=(n-1)(D_{n-1}+D_{n-2}),n\ge 3$

* 記得泰勒展開: $e^x = \sum^{\infty}_{i=0}{\cfrac{x^i}{i!}}$，所以n夠大的時候，$D_n=n!e^{-1}$
* 將10個連續整數排列，使奇數不在其自然位置的排列數有幾種?
Ans: 五個奇數亂序五個偶數在正常位置為$D_5$，所以答案是$D_5 + \dbinom{5}{1}D_6 + \dbinom{5}{2}D_7 + ... + \dbinom{5}{5}D_{10}$

* 禁位問題通常要用到城堡多項式，假設C為一個棋盤，$r_k(C)$表示在C上放k個城堡使任兩個城堡皆不在同一行或同一列的方法數，$r(C,k)=\sum^{\infty}_{k=0}{r_k(C)x^k}$，$r_0(C)=1$，x不重要，重要的是係數，係數就是方法數，排容原理裡面用的係數通常是二項式係數，但有禁位的時候就要用城堡多項式的係數。
* 將C分成m個彼此互斥的子棋盤$C_1,C_2,...,C_m$，$r(C,x)=r(C_1,x)r(C_2,x)...r(C_m,x)$

* <img src="https://i.imgur.com/4wJcYV1.png">

離散機率
---

* Bayes' theorem:
$P(F|E)= \cfrac{P(E|F)P(F)}{P(E|F)P(F)+P(E|\overline{F})P(\overline{F})}$

生成函數
---

* 定義: $a_0,a_1,...$為一個實數數列，$A(x)=a_0+a_1x+...=\sum_{i=0}^{\infty}{a_ix^i}$
為該數列的generating function(城堡多項式就是禁位問題係數的generating function)

* $\dbinom{n}{0}、\dbinom{n}{1}a、\dbinom{n}{2}a^2、...、\dbinom{n}{n}a^n$的generating function
$\sum_{i=0}^{n}{\dbinom{n}{i}a^ix^i}=(1+ax)^n$

* $\dbinom{n}{0}、\dbinom{n}{1}x^{m-1}、\dbinom{n}{2}x^{2(m-1)}、...、\dbinom{n}{n}x^{n(m-1)}$的generating function
$\sum_{i=0}^{n}{\dbinom{n}{i}x^{im}}=(1+x^m)^n$

* $\cfrac{1}{1-x}=1+x+x^2+...=\sum_{i=0}^{\infty}{x^i}$

* 1、1、...、1、0、...的generating function是
$1+x+x^2+...+x^n=\sum_{i=0}^{n}{x^i}=\cfrac{1}{1-x}-\cfrac{x^{n+1}}{1-x}=\cfrac{1-x^{n+1}}{1-x}$

* $\cfrac{d(\cfrac{1}{1-x})}{dx}=\cfrac{1}{(1-x)^2}=\sum_{i=1}^{\infty}{ix^{i-1}}=\sum_{j=0}^{\infty}{(j+1)x^j}$，所以這是1,2,3,...的generating function，且記得generating function得從i=0開始

* $\cfrac{x}{(1-x)^2}=0+x+2x^2+3x^3+...=\sum_{i=0}^{\infty}{ix^i}$，所以此為數列0,1,2,3,...的generating function

* $\cfrac{d(\cfrac{x}{(1-x)^2})}{dx}=\cfrac{1+x}{(1-x)^3}=\sum_{i=1}^{\infty}{i^2x^{i-1}}=\sum_{i=0}^{\infty}{i^2x^{i}}$，所以它為$1^2,2^2,...$的generating function

* $n\in R, r\in N$，廣義二項式系數如下
$\dbinom{n}{r}=\cfrac{n(n-1)(n-2)...(n-r+1)}{r!}$

* $\dbinom{-n}{r}=\cfrac{(-n)(-n-1)(-n-2)...(-n-r+1)}{r!}=\cfrac{(-1)^r(n)(n+1)(n+2)...(n+r-1)}{r!}=(-1)^r\dbinom{n+r-1}{r}$

* Convolution: $a_n,b_n$為兩個數列，$c_n=a_n\ast b_n=\sum_{i=0}^n{a_ib_{n-i}}$

* $a_n、b_n$的generating function為$A(x)、B(x)$，則$A(x)B(x)$為$c_n$的generating function

* $A(x)=\sum_{n=0}^{\infty}a_nx^n$且此數列與自己卷積的生成函數為$A(x)^2$，所以
$A(x)^2=\sum_{n=0}^{\infty}(a_0a_n+a_1a_{n-1}+...+a_na_0)x^n$
如果遞迴關係式為$a_n=a_0a_{n-1}+a_1a_{n-2}+...+a_{n-1}a_0, n\ge 1$
則$a_n=\cfrac{1}{n+1}\dbinom{2n}{n}$，第n階的catalan number
包括n個節點的相異有序二元樹個數、1,...,n依序push進stack中再pop能得到幾種排列，都是這個答案

* 從(0,0)走到(n,n)只允許R(朝+x走一步),U(朝+y走一步)兩種移動，且在走的時候不可以踏上y=x這條線上，有幾種走法
所有路徑數是$\dbinom{2n}{n}$，不合法的路徑數會是n-1個R和n+1個U的不全相異物排列，數量為$\dbinom{2n}{n-1}$，所以答案是$\dbinom{2n}{n}-\dbinom{2n}{n-1}=\cfrac{1}{n+1}\dbinom{2n}{n}=C_n$

* 用generating function解決組合問題，假設三件相異物a,b,c，允許重複
$1+ax+a^2x^2$表示物品a可選取0次，1次或2次
$1+bx$表示b可選取0次或1次
$(1+ax+a^2x^2)(1+bx)(1+cx)$後，**常數項1代表都不選**，x的係數代表選擇一個物品的方法，依此類推..
把a=b=c=1帶入上式，$x^i$的係數表示選i個物品時的方法數

* n個相異物，允許重複取r個的generating function為$(1+x+x^2+...+x^r)^n$，相同的問題可看為r個相同的球放進n個相異的箱子且允許空箱的方法數，不允許重複則是$(1+x)^n$，表示不拿或拿一次

* 如果generating function是$(1+x+x^2+...+x^r)^n$，要轉化為closed form並計算係數比較醜，可以直接用$(1+x+x^2+...+x^r+...)^n=(\cfrac{1}{1-x})^n=(1-x)^{-n}=\sum_{i=0}^{\infty}{\dbinom{-n}{r}(-x)^r}$，然後求$x^r$的係數，如果有些題目規定取物品的上限，例如每個物品頂多取5個，那就不能這樣用，要用原本的closed form計算。

* <img src="https://i.imgur.com/FUWgGn7.png">
* <img src="https://i.imgur.com/UyewFoI.png">
* <img src="https://i.imgur.com/0wKJVEv.png">

整數分割
---

* 將一個整數分成若干個正整數的和且**各項次序不考慮**，相當於**n個相同物品分到n個相同箱子且允許空箱的方法數**

* $p(n)$表示n的不同分割數
$i$可以出現的次數表示為$1+x^i+x^{2i}+...=\cfrac{1}{1-x^i}$，$\forall i=1,2,3,...,n$
如果$i$只能出現一次(例如有些題目會要求計算n分割成各項皆不同的方法數)，那就要表示成$1+x^i$

* $F_n(x)=\prod_{i=1}^n{(\cfrac{1}{1-x^i})}$，其中$x^i$的係數代表對i做分割，且**每項皆小於n**的不同分割數

* $p(0),p(1),p(2),...$的generating function是$F(x)=\prod_{i=1}^{\infty}{(\cfrac{1}{1-x^i})}$

* 對任意正整數做分割，**分割成各項都不相同的方法數等於分割成各項皆為奇數的分割數** (證明)

* **任意正整數分割成r個部分的方法數等於分割成最大項為r的方法數**，用Ferrer's graph證明

指數生成函數
---

* 定義: $a_0,a_1,...$為一個實數數列，$A(x)=a_0+a_1x+a_2\cfrac{x^2}{2!}+...=\sum_{i=0}^{\infty}{a_i\cfrac{x^i}{i!}}$
為該數列的指數生成函數(exponential generating function)

* 1,1,1,1....的指數生成函數為$\sum_{i=0}^{\infty}{\cfrac{x^i}{i!}}=e^x$

* 1,-1,1,-1,...的指數生成函數為$\sum_{i=0}^{\infty}{\cfrac{(-x)^i}{i!}}=e^{-x}$

* $\cfrac{e^x+e^{-x}}{2}=\sum_{i=0,2,4...}{\cfrac{x^i}{i!}}$

* $\cfrac{e^x-e^{-x}}{2}=\sum_{i=1,3,5...}{\cfrac{x^i}{i!}}$

* $\cfrac{1}{1-x}=\sum_{i=0}^{\infty}{x^i}=\sum_{i=0}^{\infty}{i!\cfrac{x^i}{i!}}$，代表$a_i=i!$的指數生成函數為$\cfrac{1}{1-x}$

* $(1+x)^n$是數列$a_i=\dbinom{n}{i}$的生成函數，也是$a_i=P_i^n$的指數生成函數

* 若一個問題為組合問題，可以用生成函數解它，若為排列問題，可以用指數生成函數解它

* 物品可選1到無限次(允許重複選擇)，對應的指數生成函數為$1+\cfrac{x}{1!}+\cfrac{x^2}{2!}+...=e^x$
不允許重複選的話，$1+\cfrac{x}{1!}$

* 相同球放到相異箱子，用生成函數解，不同球放到不同箱子，要用指數生成函數解

求和算子
---

* $A(x)=\sum_{i=0}^{\infty}{a_ix^i}$為$a_0,a_1,...$的生成函數
則$a_n$的partial sum為$s_n=\sum_{i=0}^n{a_i}$
則$s_0,s_1,s_2,..$的生成函數為
$S(x)=\cfrac{A(x)}{1-x}$

遞迴關係式
---

* $a_n$的方程式中，只包含$a_n$之前的項，一般會用帶入法或數學歸納法來求解

* 排列組合問題也時常具有遞迴關係，這也是dp的基本精神

常係數線性遞迴關係式
---

* $C_na_n+C_{n-1}a_{n-1}+...+C_{n-k}a_{n-k}=f(n)$
假設$f(n)=0$，尋找$a_n=A\alpha^n$這樣形式的解，可得$C_n\alpha^k+C_{n-1}\alpha^{k-1}+...+C_{n-k}=0$，所以它最多具有k個相異根，且$a_n=d_1\alpha_1^n+...+d_k\alpha_k^n$
證明:

* 求解這類型的recurrence通常分為下列三種情形
1. 全部的根都相異 (假設有k個)
解: $a_n=\sum_{i=1}^kd_i\alpha_i^n$，$d_i$為任意常數
2. 有重根($\alpha_i$具有重根數$m_i$)
解: $a_n=\sum_{i=1}^nu_i(n),u_i(n)=(d_{i_0}+d_{i_1}n+\cdots + d_{i_{m_i-1}}n^{m_i-1})\alpha_i^n$
3. 共軛複根($\alpha+i\beta$,$\alpha-i\beta$)
解: $a_n=\rho^n(B_1cos(n\theta)+B_2sin(n\theta))$，其中$\rho = \sqrt{\alpha^2+\beta^2}, \theta=tan^{-1}(\cfrac{\beta}{\alpha})$

* 若方程式為non-homo，則特解的形式可以分為以下幾種
1. $f(n)=(\sum_{i=0}^kd_in^i)a^n,d_k\neq 0$
解: $a_n^{(p)}=n^r(\sum_{i=0}^kc_in^i)a^n$，若$a$為具有重根數$m$的特徵根，則$r=m$，否則$r=0$
2. $f(n)=\sum_{i=0}^kd_in^i,d_k\neq 0$
解: 參照上一種類型，a換成1的一種特例
3. $f(n)=\rho^ncos(n\theta)$或$\rho^nsin(n\theta)$，其中$\theta為已知$
解: $a_n^{(p)}=\rho^n(B_1cos(n\theta)+B_2sin(n\theta))$

轉換法求解遞迴關係式
---

* $f: Z^+\rightarrow R$
$f(1)=c, f(n)=af(\cfrac{n}{b})+c$且$n=b^k$
當$a=1, f(n)=c(\log_bn+1)$

當$a\ge 2, f(n)=\cfrac{c(an^{\log_ba}-1)}{a-1}$

圖的種類及術語
---

* 分為有向圖及無向圖，$\{a,b\}=\{(a,b),(b,a)\}$，每個無向邊可視為兩個有向邊的集合

* multigraph: 存在$a,b\in V$使得a,b之間至少兩個邊，兩個點之間的邊數稱為重數multiplicity，邊集合會是multiset(有重複元素)

* 一個walk的邊數稱為它的length

* 當起點終點相同時，稱此walk為closed walk

* **不含重複邊**的walk稱為trail，**不含重複點**的walk稱為path
不含重複點也就不會有重複邊，所以path也會是trail，但反過來不成立

* closed trail又稱為circuit迴路(至少含1邊，自己到自己)

* closed path又稱為cycle環路(至少含3邊)

* loop會是circuit但不是cycle

* **path必為trial，cycle必為circuit，反之未必成立**

* **Connected Graph**: $\forall x,y\in V,x\neq y$，存在一條由x到y的path，否則就是dosconnected graph

* **Strongly Connected Graph:** $\forall x,y\in V,x\neq y$，存在一條x到y的有向path

* **Unilaterally Connected Graph:** $\forall x,y\in V,x\neq y$，在x,y間存在一條由某一點到另一點的有向path
Strongly connected graph也是unilaterally connect graph
unilaterally connected graph不為strongly connected的時候，稱為strictly unilaterally connected graph

* **Weakly Connected Graph:** 以G為基礎的虛擬無向圖為connected graph
Unilaterally connected graph必為weakly connected graph
Weakly connected graph不為unilaterally connected graph稱為strictly weakly connected graph

* **Subgraph**
$G'=(V',E')$
$\phi \neq V'\subseteq V$
$E'\subseteq E\bigcap (V'\times V')$

* 若subgraph滿足$E'= E\bigcap (V'\times V')$(也就是原本在$G$中跟$V'$有關的邊都保存)，則稱$G'$為$G$中以$V'$為引導的誘導子圖(induced subgraph on $V'$)

* 若$V'=V$則稱$G'$為$G$的spanning subgraph生成子圖

* **極大連通誘導子圖**: $G_1=(V_1,E_1)$為G的連通誘導子圖且不存在$G$的另一個連通誘導子圖$G_2=(V_2,E_2)$使得$V_1\subset V_2$，又稱為**connected component**，一個圖的connected component數量為$\kappa (G)$

* $\kappa (G)=1$ iff $G$為連通圖
$\kappa(G)\ge 2$ iff $G$為不連通圖

* $G_1\bigcup G_2=(V_1\bigcup V_2, E_1\bigcup E_2)$

* $G=(V,E)$，若$G_1=(V-\{v\},E_1)$為不連通圖，則$v$稱為cut point、articulation point

* **Biconnected Graph:** 一個loop free的連通無向圖且**不含切點**

* **Biconnected Component:** 一個loop free的連通無向圖，可能含切點，它的極大雙連通誘導子圖就是biconnected component

* $G_1=(V,E-E_1),E_1\subseteq E$為不連通圖且$\forall E_2\subset E_1,G_2(V,E-E_2)$還是為連通圖，則$E_1$為cut set，若$E_1=\{e\}$，則稱$e$為cut edge、bridge
**所有包含cut set的set都不為cut set**

* **Complete Graph** 記做$K_n$,無向圖且$|V|=n$，$G$中任相異兩點都洽有一邊相連
$K_n$必為連通圖，$|E|=\dbinom{n}{2}$

* **Direct Complete Graph** 記做$K_n^*$，有向圖且$|V|=n$，$G$鍾任相異兩點x,y滿足$(x,y),(y,x)$**洽有一邊在$E$當中**(不是都在)
$K_n^*$並不唯一，且它的有向邊邊數為$\dbinom{n}{2}$

* **Bipartite Graph**: $G=(V_1\bigcup V_2,E)$

* **Complete bipartite graph**: $G=(V_1\bigcup V_2,E)$為一個雙分圖且$\forall x\in V_1,y\in V_2$，$\{x,y\}\in E$，記做$K_{m,n}$，邊數為$mn$，因為$E$為$V_1,V_2$的cartesian product，所以$|E|=|V_1\times V_2|=|V_1||V_2|$

* **Complement Graph**: $\overline{G}=G'=(V,E'),E'=(V\times V)-E$

* 若$G$為無向圖，且有一個$v\in V,deg(v)=1$，則$v$為懸吊點pendant

* 若v包含一個迴圈，在求v的度數時應累加二

* <img src="https://i.imgur.com/pYGHHud.png">

* **規則圖**: 假設有一個無向圖，$\forall v\in V,deg(v)=k$，則$G$為k-regular graph

* **超立方體**: $Q_n$，每個點以n個位元表示，兩個點相鄰的充要條件為兩個點的位元表示**恰好有一個位元不同**

* $Q_n$可用$Q_{n-1}$遞迴建構，就像$P(A_n)=P(A_{n-1})\bigcup \{P(A_{n-1})\bigcup {a_n}\}$，所以可知道$Q_n$的點數為$2^n$，且它為**n規則圖**

* <img src="https://i.imgur.com/nXLbtuT.png">

圖形表示法與同構
---

* Adjacency Matrix: $A=[a_{ij}]$
$a_{ij}=1$ ,if $(v_i,v_j)\in E$, else $a_{ij}=0$
如果是多重圖的話$a_{ij}$代表$(v_i,v_j)$的重數

* Incidence Matrix: $M\in F^{n\times m},M=[m_{ij}]$
$m_{ij}=1$ ,若$v_i$為$e_j$的端點

* $G_1=(V_1,E_1),G_2=(V_2,E_2)$為兩個simple graph，存在一個函數$f: V_1\rightarrow V_2$滿足
1. $f$為一對一且映成函數
2. $\forall a,b\in V_1,(a,b)\in E_1 \Longleftrightarrow (f(a),f(b))\in E_2$
此時$f$為isomorphism且$G_1\cong G_2$
若為多重圖，則條件要加上**每個邊的重數相同**
同構就是重畫的概念

* $G_1\cong G_2$ iff $\overline{G_1}\cong \overline{G_2}$

* Graph Invariant: 若不滿足任何一條，則兩圖不同構
1. 頂點數相同
2. 邊數相同
3. 度數序列相同
4. 有相同子圖
5. 對應點距離相同
6. 對應點連結性相同

* 如果$G\cong \overline{G}$，則$|V|=4k$或$4k+1$

* <img src="https://i.imgur.com/0CwIsqS.png">

圖的基本性質
---

* 對無向圖來說，$\sum_{v\in V}deg(v)=2|E|$，且**degree為奇數的點的數目必有偶數個**

* **maximal path**: 若P是G當中的一條path，且P不包含於一個更長的path，則P為maximal path，**但P未必為G中最長的path**

* 若G為一個簡單無向圖，且每個點的度數至少k，則G包含一個長度至少k+1的環路

* 每個點度數至少2，則G中包含一個環路

* $G=(V,E)$為一個連通無向圖且$|V|\ge 1$，則$|E|\ge |V|-1$，除了用數學歸納法證明，可以想到其實樹就是一個邊數最少的連通圖，樹的$|E|=|V|-1$，所以再加上更多邊就會形成cycle

* <img src="https://i.imgur.com/ud0zJF7.png">

* $A$為$G=(V,E)$的adj matrix，則$A^r$的第(i,j)項為$v_i$到$v_j$長度為r的path的個數

* $G$為bipartite graph iff $G$中不具奇數長度的環路
當一個圖中有奇數長度的環路時，它不為一個bipartite graph，例如$K_3,K_5$

* <img src="https://i.imgur.com/CSENIHV.png">

* <img src="https://i.imgur.com/T6a13sr.png">

* <img src="https://i.imgur.com/JYtqGDf.png">

* <img src="https://i.imgur.com/jUAQjJO.png">

* <img src="https://i.imgur.com/mNNNnv2.png">

尤拉迴路及漢米爾頓環路
---

* $G=(V,E)$為不含孤立點的一個無向圖
若存在一路線經過G中每一個邊恰好一次，則G具有euler trail
若存在一迴路經過G中每一個邊恰好一次，則G具有euler circuit

* $G$具有euler circuit $\Leftrightarrow$ $G$為連通圖且$\forall v\in V,deg(v)$為偶數 (證明要會)

* 由此可知complete graph $K_n$具有euler circuit $\Leftrightarrow$ n為奇數

* 在complete bipartite graph $K_{m,n}$當中 $K_{m,n}$有euler circuit $\Leftrightarrow m,n$皆為偶數

* $G$有euler trail iff $G$為連通圖且恰含0個或2個點的度數為奇數，剩下都是偶數

* 如果$G$為一個有向圖，則
$G$具有有向euler circuit $\Leftrightarrow$ $G$為強連通圖且$\forall v\in V, id(v)=od(v)$

* $G=(V,E)$為不含孤立點的一個無向圖
若存在一環路經過G中每一個點恰好一次，則G具有Hamiltonian cycle
若存在一路徑經過G中每一個點恰好一次，則G具有Hamiltonian path

* 找漢米爾頓路徑或環路是一個很大的難題

* 當$G$具有Hamiltonian cycle $C$的時候
1. $\forall v \in V, deg(v)\ge 2$
2. 若$\exists v\in V,deg(v)=2$，則與$v$相鄰的兩邊必在$C$中
3. 若$\exists v\in V,deg(v)\ge 2$，且已知與$v$相鄰的某兩邊在$C$中，則其他邊必不在$C$中

* <img src="https://i.imgur.com/0alXWE1.png">

* 有向完全圖$K_n^*$必具有有向的hamiltonian path

* $G=(V,E)$為一個無迴圈的無向圖，且$|V|\ge 3$，若$deg(x)+deg(y)\ge n-1,\forall x,y\in V,x\neq y$，則G具有Hamiltonian path
若$\forall v\in V,deg(v)\ge (n-1)/2$，則$G$具有Hamiltonian path
若$deg(x)+deg(y)\ge n,\forall x,y\in V,x,y$不相鄰，則$G$具有Hamiltonian cycle
若$\forall v\in V,deg(v)\ge n/2$，則$G$具有Hamiltonian cycle

* <img src="https://i.imgur.com/SDzpz8Z.png">

* $K_n$必有Hamiltonian cycle

* 若$G=(V_1\bigcup V_2,E)$為一個連通雙分圖
$G$有Hamiltonian cycle $\Leftrightarrow$ $|V_1|=|V_2|$
$G$有Hamiltonian path $\Leftrightarrow$ $||V_1|-|V_2||\le 1$

* <img src="https://i.imgur.com/BVrJd8n.png">

*

平面圖
---

* 若$G$經過重畫後可以使所有邊都不產生交叉，則稱為Planar Graph，平面圖

* **基本區分elementary subdivision**: $G=(V,E),E\neq \emptyset$，若將$E$去掉一個邊$\{x,y\}$並加入$\{x,z\},\{z,y\},z\notin V$，這樣的動作稱為基本區分

* **同胚homeomorphic**: 若$G_1,G_2$同構，或都可由某個圖$H$經過若干基本區分得到，則稱為同胚

* **Kuratowski's theorem**
$G$為平面圖 $\Leftrightarrow$ $G$不含子圖與$K_5$或$K_{3,3}$同胚

* 平面上所有區域的度數和恰好為他的邊數和的兩倍

* **Euler formula**
$G=(V,E)$為連通平面圖，$r$為區域數量，則$|V|-|E|+r=2$
如果$G$不是連通圖，共有$M$個分量，則$|V|-|E|+r=1+M$
* 任何平面圖都恰好有一個無限區域

* 若$G=(V,E)$為一個無迴圈的簡單連通平面圖，且$|V|=v,|E|=e\ge 2$
(1)$3r/2\le e \le (3v-6)$
(2)若$G$不含任何三角形，則$e\le 2v-4$
(3)若每個環路cycle，至少由$k$個邊組成，$k\le 3$，則$e\le \cfrac{k}{k-2}(v-2)$
**如果邊數不滿足以上條件，則不為平面圖** 背起來

* <img src="https://i.imgur.com/uQ9N8sg.png">

著色理論
---

* 對於$\forall \{a,b\}\in E,a,b$都不同顏色，則稱為一種$G$的proper coloring，若可以用n種顏色做proper coloring，則稱為n-colorable，能使$G$為proper coloring的最小n稱作chromatic number，$\chi (G)$，稱$G$為n-chromatic

* 若$G$為n-colorable，則$G$也為(n+1)-colorable，反之未必成立

* 若$G_1$為$G$的子圖，則$\chi (G_1)\le \chi(G)$

* $\chi (K_n)=n$，所以若$K_n$為$G$的子圖，則$\chi(G)\ge n$

* 若$G$為至少含一個邊的雙分圖，則$\chi(G)=2$，$\chi(K_{m,n})=2$

* 若$G$有數個分量圖$G_1,..,G_k$,則$\chi(G)=max_{1\le i\le k}(G_i)$

* 任意平面圖皆為4著色

* **chromatic polynomial**: $P(G,\lambda)$，至多使用$\lambda$種顏色對$G$做正當著色的不同方法數

* $\chi(G)=min\{\lambda|P(G,\lambda)>0\}$

* $P(K_n,\lambda)=\lambda(\lambda-1)...(\lambda-n+1)$
$P(G,\lambda)=P(G_1,\lambda)...P(G_k,\lambda)$

* **著色多項式分解定理** 證明要會
$P(G,\lambda)=P(G-e,\lambda)-P(G\cdot e,\lambda)$
$P(G,\lambda)=P(G+e,\lambda)+P(G\cdot e,\lambda)$

* $G=(V,E)$，$V\neq \emptyset$，至少需要一種顏色才能完成著色，所以$P(G,0)=0$，$P(G,\lambda)$的常數項必為0
如果至少一個邊，則$P(G,1)=0$，代表所有係數和必為0
$|V|=n$，則$P(G,\lambda)$為n次多項式且$\lambda^n$的係數為一

* $G_1,G_2$為$G$的子圖且$G=G_1\bigcup G_2,G_1\bigcap G_2=K_n$，則$P(G,\lambda)=\cfrac{P(G_1,\lambda)P(G_2,\lambda)}{\lambda^{(n)}}$

* <img src="https://i.imgur.com/jWmaxCd.png">

*

樹
---

* $G=(V,E)$為一個無環路(acyclic)的連通圖，則稱為樹

* 只含一個點稱為degenerate tree、trivial tree

* **樹必為雙分圖，因此必為2-著色，樹為邊數最少的連通圖**

* $G=(V,E)$為一個loop-free的簡單無向圖，且$|V|\ge 2$，以下敘述等下
1. $G$為非退化樹
2. $G$中任意兩點恰有唯一路徑相連
3. 去掉$G$的任一邊會讓此圖不連通
4. 加入任何$x,y\in V,\{x,y\}\notin E$，都會讓$G$產生一個環路(必包含$\{x,y\}$)
5. $|E|=|V|-1$

* $T=(V,E)$為一個非退化樹，則$T$中至少含兩個懸吊點 (證明)

* $G=(V,E)$為一無向圖，若$G$無環路，則$G$為一個森林forest
因此，樹必為森林，森林為k個樹的聯集，若k=1，則森林也是樹

* **m-ary tree**: 每個內部節點最多有m個child
**full m-ary tree**: 每個內部節點恰好有m個child

* 假設有個m-ary tree，$|V|=n$,i為內部節點數量，l為樹葉數量
1. $n\le mi+1$
2. $l\le (m-1)i+1$
3. $i\ge \cfrac{l-1}{m-1}$且$i\ge \cfrac{n-1}{m}$
4. full m-ary tree, $n=mi+1=i+l$所以$l=m(i-1)+1$

* **Complete m-ary tree**: 若$T$為高度$h$的full m-ary tree且所有leaf node的階層都是$h$

* **Balanced tree**: 若leaf的階層都是$h$或$h-1$

* 若有一顆高度$h$的m-ary tree，$l$表示樹葉的個數，$l\le m^h$

* 高度$h$的full m-ary tree，$l$表示樹葉個數，$h\ge \lceil log_ml\rceil$，若此樹平衡，則$h=\lceil log_ml\rceil$

* <img src="https://i.imgur.com/BDhB8Fi.png">

* root $r$到任何$v\in V$的邊數稱為path length
T中所有內部節點路徑長總和稱為Internal path length
所有樹葉節點的路徑長總和稱為External path length

* $T$為full m-ary tree, $i$為內部節點，$I,E$分別表示internal,external path length
則$E=(m-1)I+mi$

生成樹
---

* $G$為連通圖 $\Leftrightarrow$ $G$有生成樹

* **Matrix-Tree Theorem**
$M=[m_{ij}]$，$m_{ij}=\begin{cases}
deg(v_i) \ 若i=j \\
0 \ 若i\neq j且\{v_i,v_j\}\notin E \\
-1 \ 若i\neq j且\{v_i,v_j\}\in E
\end{cases}$

則$M$所有cofactor接相同且其值為$G$相異生成樹個數

* $K_n$的相異生成樹數量為$n^{n-2}$

* $N(G)=N(G-e)+N(G\cdot e)$

* $T$為$G$的一個生成樹，$T$的任一個邊為$T$的branch，$G$的邊但不屬於$T$的邊稱為T的chord

* $G$的任意生成樹都含有$v-1$個branch，$e-v+1$個chord，代表有$e-v+1$個基本環路，稱這些環路叫fundamental system of cycle corresponding to T
$v-1$個基本切集，稱為fundamental system of cut set corresponding to T

* 對$G$的任意環路$C$和任意生成樹$T$，$C$與$\overline{T}$必有至少一個共同邊

* 對$G$的任意切集$X$和任意生成樹$T$，$X$與$T$必有至少一個共同邊

* $X$與$C$必包含偶數個共同邊 (證明)

最小生成樹
---

*