组合数
定义
普通定义
[binom nm=frac{n!}{m! (n-m)!}
]
这里，当 (n<m) 时，认为该式值为 (0)。
扩展定义
[binom nm=frac{n^{underline m}}{m!}quad(ninmathbb C,minmathbb N)
]
基本性质
对称性
[binom nm=binom n{n-m}
]
显然。
加法公式
[binom nm=binom{n-1}m+binom{n-1}{m-1}
]
证明：组合意义。
在 (n) 中选 (m) 个，可分为两种情况：
- 选第 (n) 个，则需在前 (n-1) 个中选 (m-1) 个。
- 否则需在前 (n-1) 个中选 (m) 个。
上指标求和
[sum_{i=0}^nbinom ik=binom{n+1}{k+1}
]
证明：数学归纳法。
- (n=k) 时，显然有 (binom kk=binom{k+1}{k+1})
- (n>k) 时，设结论在 (mathbb Ncap[0,n-1]) 上成立，根据加法公式，有：
[begin{aligned}
binom{n+1}{k+1}&=binom nk+binom n{k+1}\
&=binom nk+sum_{i=0}^{n-1}binom ik\
&=sum_{i=0}^nbinom ik
end{aligned}
]
因此，结论成立。
吸收恒等式
[mbinom nm=nbinom{n-1}{m-1}
]
[binom nmbinom mk=binom nkbinom{n-k}{m-k}
]
证明：第一个式子显然是第二个式子在 (k=1) 时的特殊情况，所以只需证明第二个式子。
组合意义。从 (n) 中选出 (m) 个，再从这 (m) 个中选 (k) 个，等价于先从 (n) 中选出 (k) 个，再把这 (k) 个与另外 (m-k) 个凑出 (m) 个。
范德蒙德卷积
[sum_{i+j=m}=binom kibinom{n-k}j=sum_{i=0}^mbinom kibinom{n-k}{m-i}=binom nm
]
证明：组合意义。考虑前 (k) 个选几个，把所有情况相加即可。
二项式定理
[(a+b)^n=sum_{i=0}^nbinom nia^ib^{n-i}
]
证明：考虑展开 ((a+b)^n) 后，(a^ib^{n-i}) 的系数，显然为在 (n) 个 ((a+b)) 中选 (i) 个 (a) 的情况总数。
广义二项式定理
[(x+y)^{alpha}=sum_{kge 0}binom{alpha}{k}x^ky^{alpha-k}quad(alphainmathbb R)
]
我不会证明（事实上我没学过微积分）。
练习 1
求：
[sum_{i=0}^nbinom{n-i}i
]
解：设原式为 (f(n))。
[begin{aligned}
f(n)&=sum_{i=0}^nbinom{n-i}i\
&=sum_{i=0}^nbinom{n-1-i}i+binom{n-1-i}{i-1}\
&=sum_{i=0}^{n-1}binom{n-1-i}i+sum_{i=1}^{n-1}binom{n-1-i}{i-1}\
&=sum_{i=0}^{n-1}binom{n-1-i}i+sum_{i=0}^{n-2}binom{n-2-i}i\
&=f(n-1)+f(n-2)
end{aligned}
]
又 (f(0)=1,f(1)=1)，故 (f(n)=F_{n+1})，其中 (F_i) 表示斐波那契数列的第 (i) 项。
另一种方法是利用斐波那契数列的组合意义。
求一个 (2times n) 的棋盘，使用任意多张 (1times 2) 的骨牌 完全 覆盖所有格子的方案数。设有 (f_n) 种方案。
讨论第 (n) 列是被一张竖着放的骨牌覆盖，还是被两张横着放的骨牌覆盖，即可得知 (f_n=f_{n-1}+f_{n-2})。
由于边界为 (f_0=1)，因此 (f_n=F_{n+1})。用组合数计算。若有 (2i) 张横着放置的骨牌，则一对在同一列上的骨牌会占据两列。
所以先减去 (i) 列（肯定会被占用），然后从剩下的列中选 (i) 列就是答案。所以 (f_n=sum_{i=0}^nbinom{n-i}i)。
练习 2
求：
[sum_{i=0}^nbinom{m+i-1}{i}
]
解：
[begin{aligned}
sum_{i=0}^nbinom{m+i-1}{i}
&=sum_{i=0}^nbinom{m+i-1}{m-1}\
&=sum_{i=0}^{m+n-1}binom{i}{m-1}\
&=binom{m+n}{m}
end{aligned}
]
第一步和第三步分别运用了对称性、上指标求和。
斯特林数
第二类斯特林数
定义
(begin{Bmatrix}n\mend{Bmatrix}) 表示将 (n) 个不同的元素划分为 (m) 个互不区分的非空集合的方案数。
性质
[begin{Bmatrix}n\mend{Bmatrix}=begin{Bmatrix}n-1\m-1end{Bmatrix}+mbegin{Bmatrix}n-1\mend{Bmatrix}
]
边界：(begin{Bmatrix}n\0end{Bmatrix}=[n=0])
第一类斯特林数
定义
(n) 个人坐在 (m) 张非空圆桌上的方案数记为第一类斯特林数，用 (begin{bmatrix}n\mend{bmatrix}) 表示。
性质
[begin{bmatrix}n\mend{bmatrix}=begin{bmatrix}n-1\m-1end{bmatrix}+(n-1)begin{bmatrix}n-1\mend{bmatrix}
]
边界：(begin{bmatrix}n\0end{bmatrix}=[n=0])
下降幂和上升幂
定义
[a^{underline n}=prod_{k=a-n+1}^ak
]
[a^{overline n}=prod_{k=a}^{a+n-1}k
]
斯特林数的性质
下降幂、上升幂与幂的转化
[x^{overline m}=sum_{k=0}^mbegin{bmatrix}m\kend{bmatrix}x^k\
x^{underline m}=sum_{k=0}^m(-1)^{m-k}begin{bmatrix}m\kend{bmatrix}x^k\
x^m=sum_{k=0}^mbegin{Bmatrix}m\kend{Bmatrix}x^{underline k}
]
通项公式
[begin{Bmatrix}m\kend{Bmatrix}=frac 1{k!}sum_{i=0}^k(-1)^{k-i}binom kii^m
]
容斥原理
基本公式
设 (S) 为有限集，(A_1,A_2,cdots,A_nsubseteq S)，(A={A_1,A_2,cdots,A_n}) 则有：
[|bigcup_{i=1}^{n}A_i|=sum_{k=1}^n(-1)^{k-1}sum_{1le i_1<i_2<cdots<i_kle n}|bigcap_{j=1}^kA_{i_j}|
]
证明：
设一个元素被 (A) 中的 (m) 个集合包含，则它对左侧贡献为 (1)。
它对右侧的贡献为：(sum_{i=1}^m(-1)^{i-1}binom{m}{i})（从这 (m) 个集合中任选几个集合都会包含）
(=-sum_{i=1}^m(-1)^ibinom{m}{i}=1-sum_{i=0}^m(-1)^ibinom{m}{i}=1-(1-1)^m=1)
德 · 摩根定律
[(bigcup_{i=1}^nA_i)^{complement}=bigcap_{i=1}^nA_i^{complement}qquadqquad(bigcap_{i=1}^nA_i)^{complement}=bigcup_{i=1}^nA_i^{complement}
]
感性理解：大家都知道 !(a&&b) 和 (!a)||(!b) 是等价的（a 与 b 不同时成立等同于两者之一不成立），这就是上面第二个式子的一种情况，第一个式子同理。
基本公式的变形
根据德摩根定律变形：
[begin{aligned}
|bigcap_{i=1}^nA_i^{complement}|&=|(bigcup_{i=1}^{n}A_i)^{complement}|\
&=|S|-sum_{k=1}^n(-1)^{k-1}sum_{1le i_1<i_2<cdots<i_kle n}|bigcap_{j=1}^kA_{i_j}|\
&=|S|+sum_{k=1}^n(-1)^{k}sum_{1le i_1<i_2<cdots<i_kle n}|bigcap_{j=1}^kA_{i_j}|
end{aligned}
]
[begin{aligned}
|bigcap_{i=1}^nA_i|&=|(bigcup_{i=1}^nA_i^{complement})^{complement}|\
&=|S|-sum_{k=1}^n(-1)^{k-1}sum_{1le i_1<i_2<cdots<i_kle n}|bigcap_{j=1}^kA_{i_j}^{complement}|\
&=|S|+sum_{k=1}^n(-1)^{k}sum_{1le i_1<i_2<cdots<i_kle n}|bigcap_{j=1}^kA_{i_j}^{complement}|
end{aligned}
]
子集反演
定义在两个集合上的函数 (mathbf{f,g})，若
[mathbf f(S)=sum_{Tsubseteq S}mathbf g(T)
]
则
[mathbf g(S)=sum_{Tsubseteq S}(-1)^{|S|-|T|}mathbf f(T)
]
以后有时间再证明吧。感觉和二项式反演的证明思路可能差不多。
二项式反演
这是子集反演的特殊情况：多个集合的交集大小只和集合数目有关，而与具体是哪些集合无关。
我们用 (g(i)) 表示某 (i) 个补集的交集大小（即不满足某 (i) 个条件的方案数），
(f(i)) 表示某 (i) 个原集的交集大小（即钦定 / 至少满足某 (i) 个条件的方案数）。
特别地，(f(0)=g(0)=|S|)，因为 (0) 个条件相当于任意情况。
根据上面的变形公式，我们有：
[begin{aligned}
f(n)&=|S|+sum_{k=1}^n(-1)^kbinom nkg(k)\
&=sum_{k=0}^n(-1)^kbinom nkg(k)\
g(n)&=|S|+sum_{k=1}^n(-1)^kbinom nkf(k)\
&=sum_{k=0}^n(-1)^kbinom nkf(k)
end{aligned}
]
令 (h(k)=(-1)^kg(k)) 再代进去，可以得出：
[begin{aligned}
f(n)&=sum_{k=0}^nbinom nkh(k)\
h(n)&=sum_{k=0}^n(-1)^{n+k}binom nkf(k)\
&=sum_{k=0}^n(-1)^{n-k}binom nkf(k)
end{aligned}
]
能得出二项式反演：
[f(n)=sum_{k=0}^nbinom nkh(k)\
h(n)=sum_{k=0}^n(-1)^{n-k}binom nkf(k)
]
另一种表述是，若两个序列 (f,g) 满足：
[f_n=sum_{i=0}^nbinom nig_i
]
则有：
[g_n=sum_{i=0}^n(-1)^{n-i}binom nif_i
]
这里的 (f,g) 貌似代表什么都可以。
也就是说，我们可以不关心其具体意义，只要在推出这种式子时，知道它能够与另一个式子相互转化就可以了。
也可以用代入法证明。
[begin{aligned}
f(n)&=sum_{i=0}^n(-1)^ibinom nig(i)\
&=sum_{i=0}^n(-1)^ibinom nisum_{j=0}^i(-1)^{i-j}binom ijf(j)\
&=sum_{i=0}^nsum_{j=0}^i(-1)^{i-j}binom nibinom ijf(j)\
&=sum_{j=0}^nf(j)sum_{i=j}^n(-1)^{i-j}binom nibinom ij\
&=sum_{j=0}^nbinom njf(j)sum_{i=j}^n(-1)^{i-j}binom{n-j}{i-j}\
&=sum_{j=0}^nbinom njf(j)sum_{k=0}^{n-j}(-1)^kbinom{n-j}{k}\
&=sum_{j=0}^nbinom njf(j)(1-1)^{n-j}
end{aligned}
]
这时我们不能直接把后面那项变为 (1)，需要分类讨论。
- 当 (n-jne 0) 时，((1-1)^{n-j}=0)。
- 否则，回到上式，其值为 (sum_{k=0}^0binom0k=binom00=1)。
- 综上，(sum_{j=0}^nbinom nj(1-1)^{n-j}=1)。
最终，得出了 (f(n)=f(n))，证毕。
应用
题目常让我们求：
- 至少满足一个条件（所有集合并集大小）
- 恰好满足所有条件（所有集合交集大小）
然而，我们能求的是：
- 至少满足某 (k) 个条件 （某 (k) 个集合交集大小）
我们运用上面的公式转化一下就可以了。
P6076[JSOI2015]染色问题
先考虑颜色。“每种颜色在棋盘上至少出现一次”就是“每种颜色都要出现”。
套二项式反演：
[g_A(c)=sum_{i=0}^c(-1)^{c-i}binom cif_A(i)
]
对于行，我们可以强制它满足限制。也就是在计算列的时候，把方案数减一。
考虑列。
套二项式反演：
[g_B(m)=sum_{i=0}^m(-1)^{m-i}binom mif_B(i)
]
[f_B(i)=((k+1)^i-1)^n
]
[f_A(k)=g_B(m)=sum_{i=0}^m(-1)^{m-i}binom mi((k+1)^i-1)^n
]
再代回就可以了。
推导第二类斯特林数的通项公式
复习一下，(begin{Bmatrix}m\kend{Bmatrix}) 定义是
(m) 个不同的元素划分为 (k) 个互不区分的非空集合的方案数。
设数列 (g_k) 表示将 (m) 个互不相同的元素划分为 (k) 个有区别集合的方案数，
(f_k) 表示将 (m) 个互不相同的元素划分为 (k) 个有区别非空集合的方案数。
那么显然，(g_k=k^m)。
通过枚举非空集合的个数，可以得知：
[g_k=sum_{i=0}^kbinom kif_i
]
套用二项式反演：
[f_k=sum_{i=0}^k(-1)^{k-i}binom kig_i
]
由于斯特林数中，集合互不区分，故 (begin{Bmatrix}m\kend{Bmatrix}=dfrac{f_k}{k!})
所以得出结论：
[begin{Bmatrix}m\kend{Bmatrix}=frac 1{k!}sum_{i=0}^k(-1)^{k-i}binom kii^m
]