Skip to content

组合数学

参考资料

  • 离散数学及其应用 - 翻译版, 包括 "离散数学" 和组合数学 / 初等数论 /... - 4

基础计数原理

基本法则

  • 加法原理: 若 A∩B=∅A \cap B = \emptyset, 则 ∣A∪B∣=∣A∣+∣B∣|A \cup B| = |A| + |B|
  • 乘法原理: ∣A×B∣=∣A∣⋅∣B∣|A \times B| = |A| \cdot |B|
  • 容斥原理: ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A \cup B| = |A| + |B| - |A \cap B|
  • 除法法则 类似计数时重复计算, 最终结果需要除以重复次
  • 鸽巢原理: 将 nn 个物体放入 kk 个盒子, 至少存在一个盒子包含 ⌈n/k⌉\lceil n/k \rceil 个物体

排列组合

类型 公式 示例
排列 P(n,k)=n!(n−k)!P(n,k) = \frac{n!}{(n-k)!} 5 人选 3 人排队: P(5,3)=60P (5,3)=60
组合 C(n,k)=n!k!(n−k)!C(n,k) = \frac{n!}{k!(n-k)!} 5 人选 3 人: C(5,3)=10C (5,3)=10

允许重复的排列组合

  • 排列与组合
  • 排列(有序, 可重复): nrn^r

  • 组合(无序, 可重复): (n+r−1r)\binom{n+r-1}{r}

  • 多重集排列

  • 若集合中有重复元素, 排列数为 n!∏i(ki!)\frac{n!}{\prod_{i} (k_i!)}, 其中 kik_i 为第 ii 类元素的重复次数

  • 将 nn 个相同元素分为 kk 组, 每组大小为 RiR_i, 则分组方式为 n!∏i=1k(Ri!)\frac{n!}{\prod_{i=1}^{k} (R_i!)} | 重复组合 | C(n+k−1,k)C(n+k-1,k) | 3 种水果买 5 个: C(7,5)=21C (7,5)=21 |

  • 字典序生成排列

  • 比特串生成组合

高级计数技术

递推关系

常系数齐次线性递推关系

对于递推关系: an=c1an−1+c2an−2+⋯+ckan−k a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}

  • 特征方程法
  • 特征方程为: rk−c1rk−1−c2rk−2−⋯−ck=0r^k - c_1 r^{k-1} - c_2 r^{k-2} - \cdots - c_k = 0
  • 若特征根 r1,r2,…,rkr_1, r_2, \ldots, r_k 互异, 通解为 an=A1r1n+A2r2n+⋯+Akrkn a_n = A_1 r_1^n + A_2 r_2^n + \cdots + A_k r_k^n
  • 若存在重根(如二重根 rr), 对应解为 (A+Bn)rn(A + Bn) r^n

常系数非齐次线性递推关系

an=c1an−1+⋯+ckan−k+F(n) a_n = c_1 a_{n-1} + \cdots + c_k a_{n-k} + F(n)
  • 求解步骤
  • 先求齐次方程的通解 an(h)a_n^{(h)}
  • 再找一个特解 an(p)a_n^{(p)}(形式与 F(n)F(n) 相关)
  • 通解为 an=an(h)+an(p)a_n = a_n^{(h)} + a_n^{(p)}

生成函数

  • 生成函数是以一个数列的变形作为不同幂次项的系数的多项式和式
  • 普通生成函数指数列项直接为系数 G(x)=∑k=0∞akxkG(x) = \sum_{k=0}^\infty a_kx^k
  • 它显然是数学工具

广义二项式

  • 将 C(n,k)C(n,k) 中 nn 推广为实数
  • 广义二项式定理 (1+x)n=∑k=0∞(nk)xk(∣x∣<1)(1+x)^n = \sum_{k=0}^\infty \binom{n}{k} x^k \quad (|x|<1)

斐波那契数列

  • F(n)=F(n−1)+F(n−2)F (n) = F (n-1) + F (n-2)
  • 卢卡斯数列 L(n)L(n) 是以 2,1 开始的斐波那契数列 F(n)F(n)
  • 注意到 L(n)2−5F(n)2=−4L(n)^2 - 5F(n)^2 = -4
  • 以斐波那契数列相邻两项作为输入会使欧几里德算法达到最坏复杂度
  • 2L(m+n)=5F(m)F(n)−L(m)L(n)2L(m+n) = 5F(m)F(n) - L(m)L(n)
  • 2F(m+n)=F(m)L(n)+L(m)F(n)2F(m+n) = F(m)L(n) + L(m)F(n)

特殊计数序列

卡特兰数

\(Cn=undefinedn+1C(2n,n)C_n = \frac undefined{n+1} C (2n,n)\) 应用场景:

  1. 合法括号序列数
  2. 二叉树形态数
  3. 凸多边形三角剖分数

斯特林数

类型 定义 递推关系
第一类 [nk][n \atop k]: nn 元 kk 轮换 s(n,k)=s(n−1,k−1)+(n−1)s(n−1,k)s(n,k) = s(n-1,k-1) + (n-1)s(n-1,k)
第二类 nk{n \atop k}: nn 元 kk 子集 S(n,k)=S(n−1,k−1)+kS(n−1,k)S(n,k) = S(n-1,k-1) + kS(n-1,k)
  • 第二种斯特林数 S(n,k)S(n,k) 表示将 n 个不同的元素分成 k 个非空集合的方案数
  • 第一种斯特林数 S(n,k)S(n,k) 表示将 n 个不同的元素分成 k 个非空轮换的方案数
  • 一组元素 (n 个) 的轮换是指将这组元素的排列顺序循环右移一位得到的 n 个排列

组合恒等式

  • 二项式系数求和
  • ∑r=0n(nr)=2n\sum_{r=0}^{n} \binom{n}{r} = 2^n
  • 奇数项和等于偶数项和: ∑r odd(nr)=∑r even(nr)=2n−1\sum_{r \text{ odd}} \binom{n}{r} = \sum_{r \text{ even}} \binom{n}{r} = 2^{n-1}

  • 加权求和: ∑r=0n2r(nr)=3n\sum_{r=0}^{n} 2^r \binom{n}{r} = 3^n

  • 帕斯卡恒等式

  • (n+1r)=(nr)+(nr−1)\binom{n+1}{r} = \binom{n}{r} + \binom{n}{r-1}
  • 杨辉三角性质: (n+1r+1)=∑j=rn(jr)(r≤n)\binom{n+1}{r+1} = \sum_{j=r}^{n} \binom{j}{r} \quad (r \leq n)
名称 公式
范德蒙德 ∑k=0rC(m,k)C(n,r−k)=C(m+n,r)\sum_{k=0}^r C(m,k)C(n,r-k) = C(m+n,r)
多项式定理 (∑xi)n=∑n!∏ki!∏xiki(\sum x_i)^n = \sum \frac{n!}{\prod k_i!}\prod x_i^{k_i}

经典问题

错位排列

  • Dn=(n−1)(Dn−1+Dn−2)(D1=0,D2=1)D_n = (n-1)(D_{n-1} + D_{n-2}) \quad (D_1=0, D_2=1)
  • 封闭形式: Dn=n!∑k=0n(−1)kk!D_n = n!\sum_{k=0}^n \frac {(-1)^k}{k!}

夫妻围坐

  • nn 对夫妻围坐一圈, 每对夫妻之间有一个人, 问有多少种方案:
  • (2n)!2n−∑k=1n(−1)k+1C(n,k)2k(2n−1−k)!\frac {(2n)!}{2n} - \sum_{k=1}^n (-1)^{k+1} C (n,k) 2^k (2n-1-k)!