组合数学
春日野悠
·
·
个人记录
第一类斯特林数
符号：\begin{bmatrix}n\\m\end{bmatrix}
组合意义：n个数分成m个圆排列的方案数
递推公式：\begin{bmatrix}n\\m\end{bmatrix}=\begin{bmatrix}n-1\\m-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\m\end{bmatrix}
第二类斯特林数
符号：\begin{Bmatrix}n\\m\end{Bmatrix}
组合意义：n个数划分成m个集合的方案数
递推公式：\begin{Bmatrix}n\\m\end{Bmatrix}=\begin{Bmatrix}n-1\\m-1\end{Bmatrix}+m\begin{Bmatrix}n-1\\m\end{Bmatrix}
下降幂
n^{\frac{m}{}}=n(n-1)(n-2)\cdots(n-m+1)
n^{\frac{m}{}}=\dbinom{n}{m}m!
上升幂
n^{\frac{}{m}}=n(n+1)(n+2)\cdots(n+m-1)
定理
\begin{Bmatrix}n\\m\end{Bmatrix}=\dfrac{1}{m!}\sum\limits_{k=0}^m(-1)^k\dbinom{m}{k}(m-k)^n (1)
n^{\frac{k}{}}=\sum\limits_{i=0}^k(-1)^{k-i}\begin{bmatrix}k\\i\end{bmatrix}n^i (2)
\max(S)=\sum\limits_{T \subseteq S}(-1)^{|T|-1}\min(T) (3)
n^m=\sum\limits_{i=0}^{m}\begin{Bmatrix}m\\i\end{Bmatrix}n^{\frac{i}{}} (4)
n^{\frac{}{m}}=\sum\limits_{k=0}^m\begin{bmatrix}m\\k\end{bmatrix}n^k (5)
\dbinom{n}{k}k^{\frac{m}{}}=\dbinom{n-m}{k-m}n^{\frac{m}{}} (6)
斯特林反演
f(n)=\sum\limits_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix}g(k)\Longleftrightarrow g(n)=\sum\limits_{k=0}^n(-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix}f(k)
引理(1)：x^{\frac{n}{}}=(-1)^n(-x)^{\frac{}{n}} x^{\frac{}{n}}=(-1)^n(-x)^{\frac{n}{}}
证明引理(1)：
对第一个式子：
右边=(-1)^n(-x)(-x+1)(-x+2)\cdots(-x+n-1)
=x(x-1)(x-2)\cdots(x-n+1)
=x^{\frac{n}{}}
对第二个式子：
右边=(-1)^n(-x)(-x-1)(-x-2)\cdots(-x-n+1)
=x(x+1)(x+2)\cdots(x+n-1)
=x^{\frac{}{n}}
引理(2)：\sum\limits_{k=m}^n(-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix}\begin{Bmatrix}k\\m\end{Bmatrix}=[m=n]
\sum\limits_{k=m}^n(-1)^{n-k}\begin{Bmatrix}n\\k\end{Bmatrix}\begin{bmatrix}k\\m\end{bmatrix}=[m=n]
证明引理(2)：
根据定理(4)：n^m=\sum\limits_{k=0}^m\begin{Bmatrix}m\\k\end{Bmatrix}n^{\frac{k}{}}
根据引理(1)变形上式：n^m=\sum\limits_{k=0}^m\begin{Bmatrix}m\\k\end{Bmatrix}(-1)^k(-n)^{\frac{}{k}}
又由定理(5)：n^m=\sum\limits_{k=0}^m\begin{Bmatrix}m\\k\end{Bmatrix}(-1)^k\sum\limits_{j=0}^k\begin{bmatrix}k\\j\end{bmatrix}(-n)^j
交换求和符号得：n^m=\sum\limits_{j=0}^mn^j\sum\limits_{k=j}^m(-1)^{k-j}\begin{Bmatrix}m\\k\end{Bmatrix}\begin{bmatrix}k\\j\end{bmatrix}
设a_j=\sum\limits_{k=j}^m(-1)^{k-j}\begin{Bmatrix}m\\k\end{Bmatrix}\begin{bmatrix}k\\j\end{bmatrix}
上式相等当且仅当a_0=a_1=\dots=a_{m-1}=0，a_m=1
注意此处仅j=m处正负号有影响，所以可写成如下形式，
故\sum\limits_{k=j}^m(-1)^{k-m}\begin{Bmatrix}m\\k\end{Bmatrix}\begin{bmatrix}k\\j\end{bmatrix}=[j=m]，另一个同理可得
若有f(n)=\sum\limits_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix}g(k)
对g(n)=\sum\limits_{j=0}^n[j=n]g(j)用引理(2)可得:
g(n)=\sum\limits_{j=0}^n\sum\limits_{k=j}^n(-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix}\begin{Bmatrix}k\\j\end{Bmatrix}g(j)
交换求和符号：
g(n)=\sum\limits_{k=0}^n(-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix}\sum\limits_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}g(j)
又因为有:f(k)=\sum\limits_{j=0}^{k}\begin{Bmatrix}k\\j\end{Bmatrix}g(j)
所以g(n)=\sum\limits_{k=0}^n(-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix}f(k)，得证，另一个同理
二项式反演
形式：
（0）f(n)=\sum\limits_{i=0}^n (-1)^i \dbinom{n}{i} g(i) \iff g(n)=\sum\limits_{i=0}^n (-1)^i \dbinom{n}{i} f(i)
（1）f(n)=\sum\limits_{i=0}^n g(i) \iff g(n)=\sum\limits_{i=0}^n (-1)^{n-i} \dbinom{n}{i} f(i)
（2）f(k)=\sum\limits_{i=k}^n (-1)^{i-k} \dbinom{i}{k} g(i) \iff g(k)=\sum\limits_{i=k}^n \dbinom{i}{k} f(i)
证明：
试举形式2一例，把右侧代入左侧，有
\begin{align} f(k) &=\sum\limits_{i=k}^n (-1)^{i-k} \dbinom{i}{k} \sum\limits_{j=i}^n \dbinom{j}{i} f(j)\\&= \sum\limits_{i=k}^n \sum\limits_{j=i}^n (-1)^{i-k} \dbinom{i}{k} \dbinom{j}{i} f(j) \\&= \sum\limits_{j=k}^n f(j)\sum\limits_{i=k}^j (-1)^{i-k} \dbinom{i}{k} \dbinom{j}{i} \\&= \sum\limits_{j=k}^n \dbinom{j}{k} f(j) \sum\limits_{i=k}^j \dbinom{j-k}{j-i} (-1)^{j-i} (-1)^{k-j} \\&= \sum\limits_{j=k}^n (-1)^{j-k} \dbinom{j}{k}f(j)\sum\limits_{t=0}^{j-k} \dbinom{j-k}{t} (-1)^t (+1)^{j-k-t} \end{align}
又因为二项式定理，(-1+1)^{j-k}=\sum\limits_{t=0}^{j-k} \dbinom{j-k}{t} (-1)^t (+1)^{j-k-t}，则
\begin{align} f(k) &= \sum\limits_{j=k}^n (-1)^{j-k} \dbinom{j}{k} f(j) [j=k] \\&= f(k) \end{align}
证毕，Q.E.D
形式0可以用容斥原理证明，形式1就是形式0的代换
min-max 容斥
形式：\max(S)=\sum\limits_{T \subseteq S} (-1)^{|T|-1} \min(T)（\max，\min对调仍然成立）
证明：
构造一个容斥系数函数f(x)，使得 \max(S)=\sum\limits_{T \subseteq S} f(|T|) \min(T)
考虑第x+1大的元素的贡献，则贡献为[x=0]=\sum\limits_{i=0}^x \dbinom{x}{i}f(i+1)，右边就是枚举哪些集合的最小值会成为第x+1大
设g(k)=[k=0]，则g(k)=\sum\limits_{i=0}^k \dbinom{k}{i} f(i+1)
根据二项式反演，得：
\begin{align} f(k+1) &=\sum\limits_{i=0}^k (-1)^{k-i} \dbinom{k}{i} g(i) \\&= \sum\limits_{i=0}^k (-1)^{k-i} \dbinom{k}{i} [i==0] \\&= (-1)^k \end{align}
故f(k)=(-1)^{k-1}，\max(S)=\sum\limits_{T \subseteq S} (-1)^{|T|-1} \min(T)
证毕，Q.E.D