ZXP 老师的组合数学. 说实话没讲多少内容，难度也比较低（内容应该就基本只有这些
- 事后：竟然考了 100，属实没想到
- 笑话一则：考后飞机说“md，有个 4 分的题搞错了”，出分后：96
- PS：听闻某优秀校友，小学名师挂了这门课（似乎是零蛋/缺考），不为嘲讽，仅作分享（
第二章 抽屉原理
吧 \(n+1\) 个物体放入 \(n\) 个抽屉, 则至少存在一个抽屉里面有至少两个物体.
第三章 排列组合
重集的排列
\(k\) 种元素, 个数无限: \(r\)-排列数为 \(k^r\). \(k\) 种元素, 第 \(i\) 种有 \(n_i\) 个: 全排列为 \(\frac{(n_1+\cdots+n_k)!}{n_1!\cdots n_k!}\).
重集的组合
\(x_1+\cdots+x_k=r\) 的非负整数解个数为 \(\binom{r+k-1}{r}\).
第四章 二项式系数
组合恒等式
- (帕斯卡公式): \(\binom{\alpha}{k}=\binom{\alpha-1}{k}+\binom{\alpha-1}{k-1}\);
- \(\binom{\alpha}{k}\binom{k}{p}=\binom{\alpha}{p}\binom{\alpha-p}{k-p}=\binom{\alpha}{k-p}\binom{\alpha+p-k}{p}\);
- \(\binom{\alpha+k}{p+k}\binom{p+k}{k}=\binom{\alpha+k}{k}\binom{\alpha}{p}\);
- \(\sum\limits_{k=0}^n\binom{n}{k}=\sum\limits_k\binom{n}{k}=2^n\);
- \(\sum\limits_{k=0}^n(-1)^k\binom{\alpha}{k}=(-1)^m\binom{\alpha-1}{m}\);
- \(\sum\limits_{k=0}^n\binom{\alpha}{k}\binom{\beta}{n-k}=\binom{\alpha+\beta}{n}\);
- \(\sum\limits_{k=0}^n\binom{\alpha+k}{k}\binom{\beta-k}{n-k}=\binom{\alpha+\beta+1}{n}\).
第五章 容斥原理
符号说明
- \(A_i\): \(S\) 中满足性质 \(P_i\) 的元素集合;
- \(N(i)\): \(S\) 中恰好具有 \(i\) 个性质的元素集合;
- \(L(i)\): \(S\) 中至少具有 \(i\) 个性质的元素集合;
- \(W(i)\): \(A_1,\cdots,A_m\) 中所有 \(i\) 个交集的元素个数之和.
容斥原理
- \(N(0)=W(0)-W(1)+W(2)-\cdots+(-1)^mW(m)\);
- \(L(1)=|S|-N(0)=W(1)-W(2)+W(3)-\cdots+(-1)^{m-1}W(m)\).
重集的组合
求方程 \(x_1+\cdots+x_n=r\) 带上下界 \((a_i\leqslant x_i\leqslant b_i)\) 的整数解个数.
解答: 先做变换 \(y_i=x_i-a_i\), 则方程变形为 \(y_1+\cdots+y_n=r-a_1-\cdots-a_n\). 记 \(y_i\leqslant b_i-a_i\) 为条件 \(P_i\), 用容斥原理即可.
错位排列与禁位排列
错位排列
- 递推: \(D_n=(n-1)(D_{n-1}+D_{n-2})\), \(D_1=0\), \(D_2=1\);
- 通项: \(D_n=n!\cdot\left(1-\frac{1}{1!}+\frac{1}{2!}-\cdots+\frac{1}{n!}\right)\).
禁位排列
- 递推: \(Q_n=(n-1)Q_{n-1}+(n-2)Q_{n-2}\);
- 组合证明: 考虑去掉 \(n\) 的情况, 若前 \(n-1\) 项本身就能构成禁位排列, 则只需要 \(n\) 不在 \(n-1\) 后即可, 方案数 \((n-1)Q_{n-1}\); 若前 \(n-1\) 项本身不能构成禁位排列, 则只能有一个 \(i\) 使得 \(a_{i+1}=a_i+1\), 则此时 \(n\) 只能放在此处, 考虑到 \(i\) 有 \(n-2\) 种选择, 并且去掉 \(i+1\) 后, 序列构成长度为 \(n-2\) 的禁位排列, 此时方案数为 \((n-2)Q_{n-2}\), 得证.
第六章 递推关系与生产函数
递推关系
线性 齐次 常系数
\(h_n-a_1h_{n-1}-\cdots-a_kh_{n-k}=0\) 的特征方程为 \(q_k-a_1q_{k-1}-\cdots-a_k=0\)
- 若特征方程有 \(k\) 个单根, 则通解为 \(h_n=C_1q_1^n+\cdots+C_kq_k^n\);
- 若 \(q_i\) 的重数为 \(s_i\), 则通解为 \(n^jq_i,~0\leqslant j\leqslant s_i,~1\leqslant i\leqslant k\) 的线性组合.
非齐次
求一个特解, 然后求齐次方程的通解. 设 \(f(n)=D_r(n)q^n\), \(D_r\) 为 \(r\) 次多项式, 则有特解 \[h(n)=n^sF_r(n)q^n\] 其中 \(F_r\) 为多项式, \(s\) 是 \(q\) 的重数.
生成函数
生成函数: \(h(x)=\sum\limits_{n=0}^\infty h_nx^n\).
若递推式为 \(h_n+a_1h_{n-1}+\cdots+a_kh_{n-k}=0\), 则其生成函数为 \[h(x)=\frac{b_0+b_1x+\cdots+b_{k-1}x^{k-1}}{1+a_1x+\cdots+a_kx^k}.\] 其中 \(b_n=\sum\limits_{i=0}^n a_ih_{n-i}\), \(a_0=1\).
第八章 二分图匹配
最大匹配
找 \(M\)-交错链, 标记算法求最大匹配.
König定理: 最大匹配 \(=\) 最小点覆盖.
\(p\)-正则: 每个点度都是 \(p\). 完美匹配: 若二分图 \(G\) 满足 \(|X|=|Y|=n\), 且一个匹配含 \(n\) 条边, 则称其为完美匹配.
定理: \(p\geqslant 1\) 的 \(p\)-正则二分图一定有完美匹配.
稳定匹配
延迟认可算法.
定理: 由延迟认可算法得到的匹配是稳定匹配.
第九章 组合设计
\(p^k\) 元域的构造
取 \(\mathbb{Z}_p\) 的 \(k\) 次不可约多项式 \(f\), 令其 \(k\) 个根为 \(a_1,\cdots,a_k\), 则 \(\mathbb{Z}_p\) 的 \(k\) 次扩张 \(\mathbb{Z}_p(a_1,\cdots,a_k)\) 即为 \(p^k\) 元域.
区组设计
BIBD 的性质
- 每一组含 \(k\) 个元素;
- 每一对都恰好出现在 \(\lambda\) 个区组中, 则为平衡区组设计(Balanced);
- \(k<v\), 不完全(Incomplete);
定理: BIBD 中, \(r(k-1)=\lambda(v-1)\).
可利用包含 \(x_i\) 的元素对的个数来组合证明.
定理: BIBD 中, \(bk=vr\).
可利用 BIBD 的关联矩阵中 \(1\) 的个数来组合证明.
定理: BIBD 中, \(b\geqslant v\).
\(b=v\) 时称为 SBIBD (symmetric).
符号说明
- \(b\): 区组的个数;
- \(v\): 集合元素总数;
- \(k\): 每个区组中的元素个数;
- \(r\): 包含任何一个特定元素的不同区组的个数;
- \(\lambda\): 包含任何一对特定元素的不同区组的个数.
SBIBD 的构造
定理: 若 \(B\) 是 \(\mathbb{Z}_v\) 的差分集, 则 \(B\) 生成的区组构成一个指标为 \(\lambda=\frac{k(k-1)}{v-1}\) 的 SBIBD.
如 \(\mathbb{Z}_7\) 中取 \(B=\{0,1,3\}\), 则 \[ \begin{align} B+0 &=\{0,1,3\}, \\ B+1 &=\{1,2,4\}, \\ B+2 &=\{2,3,5\}, \\ B+3 &=\{3,4,6\}, \\ B+4 &=\{4,5,0\}, \\ B+5 &=\{5,6,1\}, \\ B+6 &=\{6,0,2\}, \\ \end{align} \] 构成一个 \(b=v=7,~k=r=3,~\lambda=1\) SBIBD.
Steiner三元系统
定理: STS 中, \(r=\frac{\lambda(v-1)}{2},~b=\frac{\lambda v(v-1)}{6}\).
一个 \(v=9,~\lambda=1\) 的 STS: \[ \begin{align} &\{0,1,2\},\{3,4,5\},\{6,7,8\}, \\ &\{0,3,6\},\{1,4,7\},\{2,5,8\}, \\ &\{0,4,8\},\{1,5,6\},\{2,3,7\}, \\ &\{0,5,7\},\{1,3,8\},\{2,4,6\}. \\ \end{align} \]
拉丁方
\(n\) 阶拉丁方: 由 \(n\) 个元素构成的 \(n\times n\) 方阵, 每行每列都包含了所有 \(n\) 个元素.
定理: \((r,n)=1\), 则 \(a_{ij}=r\times i+j\) 构成 \(\mathbb{Z}_n\) 的拉丁方, 记作 \(\mathbf{L}_n^r\).
正交拉丁方
将两个 \(n\) 阶拉丁方对应位置的元素组成二元有序组, 可以构成一个新的 \(n\) 阶方阵. 如果该方阵中, \((0,0)\sim (n-1,n-1)\) 都恰好出现一次, 则称这两个拉丁方正交. 称两两正交的拉丁方为MOLS. 第一行为 \(0,\cdots,n-1\) 的MOLS由如下定理给出:
定理: 设 \(F\) 是一个 \(n=p^k\) 元域, 其中元素为 \(f_i\), 则 \(a_{ij}=r\times a_i+a_j\) 为拉丁方, \(\forall~r\neq 0\in F\), 记作 \(\mathbf{L}_n^r\). 当 \(r\) 取遍所有 \(F\) 中非零值时, 可以得到 \(n-1\) 个两两正交的拉丁方.