Martian148's blog Martian148's blog
首页
  • ICPC 算法笔记
  • ICPC 算法题解
  • 体系结构
  • 高等数学
  • 线性代数
  • 概率论与数理统计
  • 具体数学
  • Martian148的奇思妙想
  • 游记
  • 通识课笔记
关于
  • useful 网站
  • 友情链接
  • 分类
  • 归档

Martian148

一只热爱文科的理科生
首页
  • ICPC 算法笔记
  • ICPC 算法题解
  • 体系结构
  • 高等数学
  • 线性代数
  • 概率论与数理统计
  • 具体数学
  • Martian148的奇思妙想
  • 游记
  • 通识课笔记
关于
  • useful 网站
  • 友情链接
  • 分类
  • 归档
  • 线上赛板子(实时更新)
  • 数据结构

  • 数学

    • 数论
    • 多项式与生成函数
    • 线性代数
    • 组合数学
      • 容斥原理
      • 特殊的数
        • Catalan 数
        • 斯特林数
        • 第二类斯特林数
        • 分拆数
    • 博弈论
  • 计算几何

  • 动态规划

  • 图论

  • 字符串

  • 杂项

  • 算法笔记
  • 数学
martian148
2024-08-31
目录

组合数学

# 组合数学

# 容斥原理

容斥原理的简单形式,设 AAA 和 BBB 是分别具有性质 P1P_1P1​ 和 P2P_2P2​ 的有限集,有

A∪B=∣A∣+∣B∣−∣A∩B∣ A\cup B =|A|+|B|-|A\cap B| A∪B=∣A∣+∣B∣−∣A∩B∣

e.g. 求正整数 111 到 nnn 中,既不是 222 的倍数也不是 333 的倍数的数的个数

设 S={1,2,⋯,n}S=\{1,2,\cdots ,n\}S={1,2,⋯,n},AAA 是 222 的倍数,BBB 是 333 的倍数,那么答案就是 ∣S∣−∣A∪B∣|S|-|A\cup B|∣S∣−∣A∪B∣

由于 ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A\cup B|=|A|+|B|-|A\cap B|∣A∪B∣=∣A∣+∣B∣−∣A∩B∣, 所以答案就是 n−⌊n2⌋−⌊n3⌋+⌊n6⌋n-\lfloor \frac{n}{2}\rfloor -\lfloor \frac{n}{3}\rfloor +\lfloor \frac{n}{6}\rfloorn−⌊2n​⌋−⌊3n​⌋+⌊6n​⌋

e.g. 求由 nnn 个元素 1,2,⋯,n1,2,\cdots,n1,2,⋯,n 全排列中,满足 111 和 222 不相邻,333 和 444 不相邻的排列数

设 AAA 是 111 和 222 相邻,BBB 是 333 和 444 相邻,那么答案就是 n!−∣A∪B∣n!-|A\cup B|n!−∣A∪B∣

所以答案就是 n!−2(n−1)!−2(n−1)!+4(n−2)!n!-2(n-1)!-2(n-1)!+4(n-2)!n!−2(n−1)!−2(n−1)!+4(n−2)!

考虑三个子集的容斥原理

∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣ |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C| ∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣

推广到 nnn 个集合

设 SSS 是一个有限集,A1,A2,⋯,AnA_1,A_2,\cdots ,A_nA1​,A2​,⋯,An​ 是 SSS 的 nnn 个子集,那么

∣A1∪A2∪⋯∪An∣=∑i=1n(−1)i−1∑1≤j1<j2<⋯<ji≤n∣Aj1∩Aj2∩⋯∩Aji∣ |A_1\cup A_2\cup \cdots \cup A_n|=\sum_{i=1}^n(-1)^{i-1}\sum_{1\leq j_1<j_2<\cdots <j_i\leq n}|A_{j_1}\cap A_{j_2}\cap \cdots \cap A_{j_i}| ∣A1​∪A2​∪⋯∪An​∣=i=1∑n​(−1)i−11≤j1​<j2​<⋯<ji​≤n∑​∣Aj1​​∩Aj2​​∩⋯∩Aji​​∣

我们对答案取补集的形式也很常见:

S−∣A1∪A2∪⋯∪An∣=∑i=0n(−1)i∑1≤j1<j2<⋯<ji≤n∣Aj1∩Aj2∩⋯∩Aji∣ S-|A_1\cup A_2\cup \cdots \cup A_n|=\sum_{i=0}^n(-1)^{i}\sum_{1\leq j_1<j_2<\cdots <j_i\leq n}|A_{j_1}\cap A_{j_2}\cap \cdots \cap A_{j_i}| S−∣A1​∪A2​∪⋯∪An​∣=i=0∑n​(−1)i1≤j1​<j2​<⋯<ji​≤n∑​∣Aj1​​∩Aj2​​∩⋯∩Aji​​∣

这里需要定义 ∣∩∅∣=S|\cap \varnothing|=S∣∩∅∣=S

e.g. mmm 件不同的物品,分配给 nnn 个人,要求每个人至少要分得一件物品,求不同的分配方案数

设 S=S=S= 总方案数,Ai=A_i=Ai​= 第 iii 个人没有分到物品的方案数

答案就是

S−∣A1∪A2∪⋯∪An∣=∑i=0n(−1)i∑1≤j1<j2<⋯<ji≤n∣Aj1∩Aj2∩⋯∩Aji∣ S-|A_1\cup A_2\cup \cdots \cup A_n|=\sum_{i=0}^n(-1)^{i}\sum_{1\leq j_1<j_2<\cdots <j_i\leq n}|A_{j_1}\cap A_{j_2}\cap \cdots \cap A_{j_i}| S−∣A1​∪A2​∪⋯∪An​∣=i=0∑n​(−1)i1≤j1​<j2​<⋯<ji​≤n∑​∣Aj1​​∩Aj2​​∩⋯∩Aji​​∣

∣Aj1∩Aj2∩⋯∩Aji∣|A_{j_1}\cap A_{j_2}\cap \cdots \cap A_{j_i}|∣Aj1​​∩Aj2​​∩⋯∩Aji​​∣ 就是 n−in-in−i 个人分配 mmm 件物品的方案数,即 C(n,n−i)×(n−i)m=C(n,i)×(n−i)mC(n,n-i)\times (n-i)^{m}=C(n,i)\times (n-i)^{m}C(n,n−i)×(n−i)m=C(n,i)×(n−i)m

得到了答案的递推式:

∑i=0n(−1)iC(n,i)×(n−i)m \sum_{i=0}^n(-1)^{i}C(n,i)\times (n-i)^{m} i=0∑n​(−1)iC(n,i)×(n−i)m

e.g. 错排问题:ppp 是一个排列,满足 pi≠ip_i\neq ipi​​=i 的数的个数称为错排数,求错排数

设 SSS 是所有排列数,AiA_iAi​ 是 iii 不在 pip_ipi​ 的位置的排列数

∣S−∪i=1nAi∣=∑i=0nCni(n−i)! |S-\cup^{n}_{i=1} A_i|=\sum_{i=0}^{n}C_{n}^i(n-i)! ∣S−∪i=1n​Ai​∣=i=0∑n​Cni​(n−i)!

容斥原理的符号形式

设 SSS 是一个有限集,a1,a2,⋯,ana_1,a_2,\cdots, a_na1​,a2​,⋯,an​ 是 nnn 种性质

  • 记 N(ai)N(a_i)N(ai​) 为 SSS 中有 aia_iai​ 性质的元素的数量。特殊的,记 N(1)=∣S∣N(1)=|S|N(1)=∣S∣
  • 记 N(1−ai)N(1-a_i)N(1−ai​) 为 SSS 中没有 aia_iai​ 性质的元素的数量
  • N(ai1,ai2,⋯,aik)N(a_{i_1},a_{i_2},\cdots,a_{i_k})N(ai1​​,ai2​​,⋯,aik​​) 为 SSS 中同时有 ai1,ai2,⋯,aika_{i_1}, a_{i_2},\cdots,a_{i_k}ai1​​,ai2​​,⋯,aik​​,性质的元素的数量
  • 记 N(a+b)=N(a)+N(b)N(a+b)=N(a)+N(b)N(a+b)=N(a)+N(b)

通过符号形式,我们可以把容斥原理改成多项式来处理

则,容斥原理可以写成:

N((1−a1)(1−a2)⋯(1−an))=∑i=0n(−1)i∑1≤j1<j2<⋯<ji≤nN(aj1,aj2,⋯,aji) N((1-a_1)(1-a_2)\cdots(1-a_n))=\sum\limits_{i=0}^n(-1)^i \ \sum\limits_{1\le j_1<j_2<\cdots<j_i\le n} N(a_{j_1},a_{j_2},\cdots,a_{j_i}) N((1−a1​)(1−a2​)⋯(1−an​))=i=0∑n​(−1)i 1≤j1​<j2​<⋯<ji​≤n∑​N(aj1​​,aj2​​,⋯,aji​​)

e.g. 求正整数 111 到 nnn 中,既不是 222 的倍数,也不是 333 的倍数,但是 555 的倍数的数的数量

设 a1a_1a1​ 设 222 的倍数,a2a_2a2​ 是 333 的倍数, a3a_3a3​ 是 555 的倍数

答案就是 N((1−a1)(1−a2)a3)=N(a3−a1a3−a2a3+a1a2a3)N((1-a_1)(1-a_2)a_3)=N(a_3-a_1a_3-a_2a_3+a_1a_2a_3)N((1−a1​)(1−a2​)a3​)=N(a3​−a1​a3​−a2​a3​+a1​a2​a3​)

# 特殊的数

# Catalan 数

Catalan 数有三种计算公式

公式 111:

Cn=1n+1(2nn)=(2nn)−(2nn+1)=(2nn)−(2nn−1) C_n = \frac{1}{n + 1}\tbinom{2n}{n}=\tbinom{2n}{n}-\tbinom{2n}{n+1}=\tbinom{2n}{n}-\tbinom{2n}{n-1} Cn​=n+11​(n2n​)=(n2n​)−(n+12n​)=(n2n​)−(n−12n​)

公式 111 可以从一个基本模型推导出来:把 nnn 个 111 和 nnn 个 000 排成一行,使这一行的任意 kkk 个数中 111 的数量总是大于或等于 000 的数量,这样的排列一共有 CnC_nCn​ 个

公式 222:

Cn=∑k=0nCkCn−1−k,C0=1 C_n=\sum\limits_{k=0}^nC_kC_{n-1-k},\ C_0 = 1 Cn​=k=0∑n​Ck​Cn−1−k​, C0​=1

公式 333:

Cn=4n−2n+1Cn−1 C_n=\frac{4n-2}{n+1}C_{n-1} Cn​=n+14n−2​Cn−1​

模型 1:棋盘问题

一个 nnn 行 nnn 列的棋盘,从左上角走到右上角,一直在对角线右下方走,不穿过主对角线,走法有多少种?

对方向编号,向上为 000,向右为 111,那么从左下角到右上角一定会经过 nnn 个 111 和 nnn 个 000,如果第 kkk 步之前 000 的个数超过 111 的个数了,就说明一定超过对角线了

从左下角到右上角的路线方案总共有 333 种:

  • A :在对角线下方的方案数
  • B :在对角线上方的方案数
  • C :穿过对角线的方案数

显然, (2nn)=A+B+C\tbinom{2n}{n}=A+B+C(n2n​)=A+B+C,现在的问题转化成如何求 B+CB+CB+C

我们需要找一条穿过对角线或者完全在对角线上方的路线,然后按照一条虚线映射

image.png

我们发现,一条穿过对角线的路线和新路线是一一对应的,而新路线的方案数是 (2nn+1)=(2nn−1)\tbinom{2n}{n+1}=\tbinom{2n}{n-1}(n+12n​)=(n−12n​),从 2n2n2n 个里面选 n+1n+1n+1 个 000,选 n−1n-1n−1 个 111

所以 Cn=(2nn)−(2nn−1)C_n = \tbinom{2n}{n}-\tbinom{2n}{n-1}Cn​=(n2n​)−(n−12n​)

使用生成函数推导

根据递推公式:

Cn=∑k=0nCkCn−1−k C_n=\sum\limits_{k=0}^nC_kC_{n-1-k} Cn​=k=0∑n​Ck​Cn−1−k​

定义生成函数 f(x)=∑n=0∞Cnxnf(x)=\sum\limits_{n=0}^{\infty}C_nx^nf(x)=n=0∑∞​Cn​xn,那么:

C(x)=∑n≥0Cnxn=1+x+x∑n≥1∑i=0nCiCn−1xn=1+x+x(C(x)2−1)=1+xC2(x) \begin{aligned} C(x)&=\sum\limits_{n\ge 0} C_nx^n\\ &=1+x+x\sum\limits_{n\ge 1} \sum\limits_{i=0}^nC_iC_{n-1}x^n\\ &=1+x+x(C(x)^2-1)\\ &=1+xC^2(x) \end{aligned} C(x)​=n≥0∑​Cn​xn=1+x+xn≥1∑​i=0∑n​Ci​Cn−1​xn=1+x+x(C(x)2−1)=1+xC2(x)​

考虑类似于实数的二次方程,解得:

C(x)=−1+1−4x2x C(x)=\frac{-1+\sqrt{1-4x}}{2x} C(x)=2x−1+1−4x​​

其中:

(1−4x)12=∑n=0∞(12n)(−4)nxn=∑n≥012(12−1)(12−2)⋯(12−n+1)n!(−4)nxn \begin{aligned} (1-4x)^{\frac{1}{2}}&=\sum_{n=0}^{\infty} \binom{\frac{1}{2}}{n}(-4)^nx^n\\ &=\sum\limits_{n\ge 0}\frac{\frac{1}{2}(\frac{1}{2}-1)(\frac{1}{2}-2)\cdots(\frac{1}{2}-n+1)}{n!}(-4)^nx^n \end{aligned} (1−4x)21​​=n=0∑∞​(n21​​)(−4)nxn=n≥0∑​n!21​(21​−1)(21​−2)⋯(21​−n+1)​(−4)nxn​

所以:

C(x)=−∑n≥012(12−1)(12−2)⋯(12−n)(n+1)!(−4)nxn C(x)=-\sum\limits_{n\ge 0}\frac{\frac{1}{2}(\frac{1}{2}-1)(\frac{1}{2}-2)\cdots(\frac{1}{2}-n)}{(n+1)!}(-4)^nx^n C(x)=−n≥0∑​(n+1)!21​(21​−1)(21​−2)⋯(21​−n)​(−4)nxn
[xn]C(x)=12(12−1)(12−2)⋯(12−n)(n+1)!(−4)n=−12(−12)(−32)⋯(−2n−12)⋅1⋅2⋯n(n+1)!(n)!(−4)n=1⋅3⋅5⋯2n−1⋅2⋅4⋯2n(n+1)!n!=(2n)!(n+1)!n!=1n+1(2nn) \begin{aligned} [x^n]C(x)&=\frac{\frac{1}{2}(\frac{1}{2}-1)(\frac{1}{2}-2)\cdots(\frac{1}{2}-n)}{(n+1)!}(-4)^n\\ &=-\frac{\frac{1}{2}(-\frac{1}{2})(-\frac{3}{2})\cdots(-\frac{2n-1}{2})\cdot1\cdot2\cdots n}{(n+1)!(n)!}(-4)^n\\ &=\frac{1\cdot3\cdot5\cdots2n-1\cdot2\cdot4\cdots2n}{(n+1)!n!}\\ &=\frac{(2n)!}{(n+1)!n!}=\frac{1}{n+1}\binom{2n}{n} \end{aligned} [xn]C(x)​=(n+1)!21​(21​−1)(21​−2)⋯(21​−n)​(−4)n=−(n+1)!(n)!21​(−21​)(−23​)⋯(−22n−1​)⋅1⋅2⋯n​(−4)n=(n+1)!n!1⋅3⋅5⋯2n−1⋅2⋅4⋯2n​=(n+1)!n!(2n)!​=n+11​(n2n​)​

# 斯特林数

# 第二类斯特林数

考虑一个问题:

有 nnn 个互不相同的求球,放到 kkk 个互不区分的盒子里,每个盒子里至少要有一个球,球方案数

用动态规划来解决这个问题

f(n,k)=kf(n−1,k)+f(n−1,k−1) f(n,k)=kf(n-1,k)+f(n-1,k-1) f(n,k)=kf(n−1,k)+f(n−1,k−1)

我们定义 f(n,k)f(n,k)f(n,k) 为第二类斯特林数,记作 S2(n,k)S_2(n,k)S2​(n,k),这种方法的时间复杂度为 O(nk)O(nk)O(nk)

考虑用容斥原理求出 O(klog⁡n)O(k\log n)O(klogn) 的递推式

先把盒子按照 1∼k1\sim k1∼k 编号,设 aia_iai​ 表示第 iii 个盒子没有球,答案就是

N((1−a1)⋯(1−ak))=∑i=0k(−1)i(ki)(k−i)n=S2(n,k)×k! N((1-a_1)\cdots(1-a_k))=\sum\limits_{i=0}^k(-1)^i\binom{k}{i}(k-i)^n=S_2(n,k)\times k! N((1−a1​)⋯(1−ak​))=i=0∑k​(−1)i(ik​)(k−i)n=S2​(n,k)×k!

则我们能得到第二类斯特林数的通项公式

{nk}=1k!∑i=0k(−1)i(ki)(k−i)n {n\brace k}=\frac{1}{k!}\sum\limits_{i=0}^k(-1)^i\binom{k}{i}(k-i)^n {kn​}=k!1​i=0∑k​(−1)i(ik​)(k−i)n

第二类斯特林数还有一个重要的公式

nm=∑k=0m{mk}nk‾ n^m=\sum\limits_{k=0}^m {m\brace k} n^{\underline{k}} nm=k=0∑m​{km​}nk​

可以思考组合意义来理解,把 mmm 个相互区分的球放到 nnn 个相互区分盒子里面,朴素的方法就是 nmn^mnm

我们可以先去 kkk 个盒子放球,要求每个盒子中至少有一个球,这个的方案数就是 CnkS2(m,k)k!=S2(m,k)nk‾C_n^kS_2(m,k)k!=S_2(m,k)n^{\underline{k}}Cnk​S2​(m,k)k!=S2​(m,k)nk​

第二类斯特林数有关于 nnn 的指数生成函数

∑n≥0S2(n,k)xnn!=1k!(exp⁡(x)−1)k \sum_{n\ge 0} S_2(n,k)\frac{x^n}{n!}=\frac{1}{k!}(\exp(x)-1)^k n≥0∑​S2​(n,k)n!xn​=k!1​(exp(x)−1)k

这样就可以求一行的斯特林数,就是 nnn 固定

我们有

{nk}=1k!∑i=0k(−1)i(ki)(k−i)n=∑i=0k(−1)i1i!×1(k−i)!(k−1)n {n\brace k}=\frac{1}{k!}\sum_{i=0}^k(-1)^i\binom{k}{i}(k-i)^n=\sum_{i=0}^k(-1)^i\frac{1}{i!}\times \frac{1}{(k-i)!}(k-1)^n {kn​}=k!1​i=0∑k​(−1)i(ik​)(k−i)n=i=0∑k​(−1)ii!1​×(k−i)!1​(k−1)n

设 f(x)=∑i=0n(−1)i1i!xi,g(x)=∑j=0n1j!jnf(x)=\sum_{i=0}^n(-1)^i\frac{1}{i!}x^i,g(x)=\sum_{j=0}^n\frac{1}{j!} j^nf(x)=∑i=0n​(−1)ii!1​xi,g(x)=∑j=0n​j!1​jn

所以

{nk}=[xk]f(x)⋅g(x) {n\brace k}=[x^k]f(x)\cdot g(x) {kn​}=[xk]f(x)⋅g(x)

总时间复杂度为 O(nlog⁡n)O(n\log n)O(nlogn)

# 分拆数

nnn 个无标号的球分配到 kkk 和无标号的盒子的方案数,每个盒子不为空,记为 p(n,k)p(n,k)p(n,k)

有递推关系

p(n,k)=p(n−1,k−1)+p(n−k,k) p(n,k)=p(n-1,k-1)+p(n-k,k) p(n,k)=p(n−1,k−1)+p(n−k,k)

image-20241101001500147

构造一种排列方式,一共有 kkk 行,每一行的球的数量都比上一行少,每一列考虑:

  • 如果最后一行只有一个球 p(n−1,k−1)p(n-1,k-1)p(n−1,k−1)
  • 如果最后一行不止一个球 p(n−k,k)p(n-k,k)p(n−k,k)

关于 nnn 的常生成函数:∑n≥0p(n,k)xn=xk∏i=1k11−xi\sum_{n\ge 0}p(n,k)x^n=x^k\prod_{i=1}^k \frac{1}{1-x^i}∑n≥0​p(n,k)xn=xk∏i=1k​1−xi1​

如何快速求 p(n,k)p(n,k)p(n,k):先取 ln 再 exp

nnn 个无标号的球分配到一些无编号盒子,每个盒子不为空的方案数,记为 p(n)p(n)p(n)

有 p(n)=∑k=1np(n,k)p(n)=\sum_{k=1}^n p(n,k)p(n)=∑k=1n​p(n,k)

递推关系

p(n)=∑k≥1(−1)k−1(p(n−3k2−k2)+p(n−3k2+k2)) p(n)=\sum_{k\ge 1}(-1)^{k-1}(p(n-\frac{3k^2-k}{2})+p(n-\frac{3k^2+k}{2})) p(n)=k≥1∑​(−1)k−1(p(n−23k2−k​)+p(n−23k2+k​))

常生成函数

∑n≥0p(n)xn=∏i≥111−xi \sum_{n\ge 0} p(n) x^n=\prod_{i\ge 1}\frac{1}{1-x^i} n≥0∑​p(n)xn=i≥1∏​1−xi1​

这个表展示了一些经典的分配问题

image-20241101003947933

上次更新: 2025/04/08, 18:03:31
线性代数
博弈论

← 线性代数 博弈论→

最近更新
01
在 ACM 集训队年会上的讲话
07-01
02
计算机网络笔记
06-13
03
LLM101 NLP学习笔记
06-02
更多文章>
Theme by Vdoing | Copyright © 2024-2025 Martian148 | MIT License
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式