• 欢迎光临~

组合数学习笔记

开发技术 开发技术 2022-07-21 次浏览

组合数

定义

普通定义

[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) 是等价的(ab 不同时成立等同于两者之一不成立),这就是上面第二个式子的一种情况,第一个式子同理。

基本公式的变形

根据德摩根定律变形:

[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 ]

程序员灯塔
转载请注明原文链接:组合数学习笔记
喜欢 (0)