组合数学提纲
第一章
排列
\[ P(n,r)=P_{n}^{r}=\frac{n!}{(n-r)!} \]
组合
\[ \binom{n}{r} =C_n^r=C(n,r)=\frac{n!}{r!(n-r)!} \]
可重排列
\(n\) 种不同元素取 \(r\) 个可重元素排列
\[ \overline{P}(n,r) = n^r \]
多重排列
每种元素 \(x_i\) 选择 \(r_i\) 个按次序排列，\(n=\sum_i r_i\) \[ P(n;r_1,\cdots,r_k)=\binom{n}{r_1,r_2,\cdots,r_k}=\frac{n!}{r_1!r_2!\cdots r_k!} \]
多项式幂次展开系数
有多项式 \[ (x_1+x_2+x_3+\cdots+x_m)^n \] 其项 \(x_1^{n_1}x_2^{n_2}x_3^{n_3}\cdots x_m^{n_m}\) 的系数为
\[ \binom{n}{n_1,n_2,\cdots,n_m}=\frac{n!}{n_1!n_2!\cdots n_m!} \] 项数 \(C(n+m-1,n)\)，系数和 \(m^n\)
圆周排列
经旋转重复认为是相同的排列 \[ Q(n,r)=P(n,r)/r \] 项链排列：经旋转对称重复认为是相同的排列，排列数 \(Q(n,r)/2\)
可重组合
\(n\) 种不同元素取 \(r\) 个可重元素组合
\[ \overline{C}(n,r)=C(n+r-1,r) \]
线性方程 \(x_1+x_2+\cdots+x_n=b\) 的自然数解个数 \(C(n+b-1,b)\)
不相邻组合
\(n\) 个不同元素 \(x_1,x_2,\cdots,x_n\) 取 \(r\) 个不相邻元素组合（即不存在 \(x_j,x_{j+1}\) 同时选取） \[ C(n-r+1,r) \]
格路定理
设 \(c>a\)，\(d>b\)，则由 \((a,b)\) 到 \((c,d)\) 的简单格路数 \[ |(a,b)-(c,d)|=\binom{(c-a)+(d-b)}{c-a} \] 从 \((0,1)\) 至 \((m,n)\) 不接触对角线 \(y=x\) 格路：采用一一对应原理
\[ \binom{m+n-1}{m}-\binom{m+n-1}{m-1} = \left(1-\frac{m}{n}\right)\binom{m+n-1}{m} \]
无根标号树与序列一一对应
树到序列：逐个摘去编号最小的叶子，该叶子相邻节点形成的序列（长度 \(n-2\)）
序列到树：序列一 \(b_1,b_2,\cdots,b_{n-2}\)，对应序列二 \(1,2,\cdots,n\)，从序列二中找到第一个不出现在序列一中的数 \(a_1\)，生成边 \((a_1,b_1)\)。分别从序列一和序列二中去掉 \(a_1\) 和 \(b_1\)；在余下的序列中重复上述操作，直到序列一为空，序列 2 余下两点建边
凯利定理：\(n\) 个有标号的顶点的树的数目是 \(n^{n-2}\)
排列的生成算法
序数法
排列的序数 \(m\)：排列在枚举过程的出现排名 \[ m=a_n(n-1)!+a_{n-1}(n-2)!+\cdots+a_3\cdot 2!+a_2\cdot 1! \] 序列 \((a_na_{n-1}\cdots a_2)\uparrow\) 为序数 \(m\) 对应的（递增进制）中介数，注意没有第一位
序数求中介数：使用短除法
递增进位制法
递增进位数：\(0\le a_k < k\)，表示第 \(k\) 位为 \(k\) 进制
全排列的中介数：\(a_k\) 表示数字 \(k\) 的右边比 \(k\) 小的数字个数
中介数的全排列：填空法；由大到小从中介数意义确定右侧空格个数
由排列求下一个排列：检查 \(k\) 从 \(1\sim n\) 使其最大，若排列中存在子序列 \(k,k-1,k-2,\cdots,2,1\)，则将 \(k+1\) 置于 \(k\) 位置，并在剩下的 \(k\) 个空中，依次从左至右填入 \(1,2,\cdots,k\)。若 \(k=n\)，无下一个排列
递减进位制法
中介数各位是递增进位制轴对称 \((a_2a_3\cdots a_n)\downarrow \iff (a_na_{n-1}\cdots a_2)\uparrow\)，意义由下标决定，权 \(m=\sum\limits_{k=2}^na_k\dfrac{n!}{k!}\)
递减进位数：\(0\le a_k < k\)
全排列的中介数：\(a_k\) 表示数字 \(k\) 的右边比 \(k\) 小的数字个数
中介数的全排列：由大到小从中介数意义确定右侧空格个数
由排列求下一个排列：若 \(n\) 不在最左侧则显然，否则将最长的下降序列 \(n,n-1,n-2,\cdots,i\) 删去，并将它们由小到大排在右端，将 \(i-1\) 与 \(i-2\) 对换，此时的排列就是下一个排列。若 \(i<3\) 则无下一个序列
字典序法
下一个排列：
- 串 \(P\) 从右到左找出比右边数字小的第一个数 \(P_t\)（最后一个上升位），以及该位以后的后缀 \(s_{t+1}\)
- \(s_{t+1}\) 中找出比 \(P_t\) 大的最后的数 \(P_p\)
- 将 \(P_t\)，\(P_p\) 对换后反转后缀
中介数：\((k_1k_2\cdots k_{n-1})\)，\(k_i\) 表示数字 \(P_i\) 的右边比 \(P_i\) 小的数字个数
序数：\(m=k_1\cdot (n-1)!+k_2\cdot (n-2)!+\cdots+k_{n-1}\cdot1!\)
换位法
排列 \(P=P_1P_2\cdots P_n\) 中数 \(k\) 上的箭头方向（移动方向），由排列 \(P\) 中 \(1\sim k-1\) 所构成的子序列的奇偶性决定，当为偶时，箭头向左；当为奇时，箭头向右。数 \(1,2\)上的箭头规定向左。如 \(\overset\leftarrow8\vec3\vec9\vec6\vec4\vec7\vec5\overset\leftarrow2\overset\leftarrow1\)
加点法判断箭头方向：是否加点取决于该数右侧比它小的数数量是否为奇数，子序列 \(1\sim k-1\) 点数为偶时箭头向左，否则向右
中介数：\((b_2b_3\cdots b_n)\downarrow\)，\(b_i\) 表示 \(i\) 箭尾方向上比 \(i\) 小的数的个数
中介数到序数：\(m=\sum\limits_{k=2}^na_k\dfrac{n!}{k!}\)
中介数到排列：仅需要确定 \(P_k\) 箭头方向，设排列 \(P\) 中 \(1\sim k-1\) 所构成的子排列序数为 \(a_{k-1}(P)\)（与逆序数同奇偶性），短除时判断即可
下一个排列：设 \(P_j=n\)，当 \(P_j\) 不在顶时 \(P_j\) 与箭头方向元素交换，否则对长度 \(n-1\) 的子排列使用上述做法，下一个排列中所有比 \(P_j\) 大的数改变箭头方向
组合的生成算法
给组合元素排序并以字典序生成
序号：按字典序思想
第二章
Maclaurin 公式
\[ \frac{1}{1-x}=1+x+x^2+x^3+\cdots+x^n+\cdots \]
\[ \mathrm e^{x}=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots+\frac{x^n}{n!}+\cdots \]
\[ \sin x=x-\frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}+\cdots \]
\[ \cos x=x-\frac{x^2}{2!}+\frac{x^4}{4!}-\frac{x^6}{6!}+\cdots \]
\[ \ln (1+x)=x-\frac{x^2}{2}+\frac{x^3}{3}-\frac{x^4}{4}+\cdots \]
行列式按行展开
\[ D=\sum a_{ij}(-1)^{i+j}M_{ij} \]
线性常系数齐次递推关系
\(k\) 阶线性常系数齐次递推关系 \[ a_n+C_1a_{n-1}+C_2a_{n-2}+\cdots+C_ka_{n-k}=0 \] 特征多项式 \[ C(x)=x^k+C_1x^{k-1}+\cdots+C_{k-1}x+C_k \] 有 \[ \begin{align} x^kC\left(\frac{1}{x}\right)G(x)=P(x)=\sum_{j=0}^{k-1}C_jx^j\sum_{i=0}^{k-1-j}a_ix^i \nonumber\\ \Rightarrow G(x)=\frac{P(x)}{1+C_1x+\cdots+C_{k-1}x^{k-1}+C_kx^k}\nonumber \end{align} \] 由于 \(P(x)\) 次数低于 \(k\)，则 \(G(x)\) 有分子为常数、分母为特征根表达式的分项表示
设特征多项式有 \(k\) 个根 \(q_1,q_2,\cdots,q_k\)，则通解中有 \(k\) 个分项（\(A_i\) 为待定系数）：
- 若 \(q_i\) 为单根，则项 \(A_iq_i^n\) 在通解中
- 若 \(q_i\) 为 \(m\) 重根，则项 \(\left(A_{i0}+A_{i1}n+A_{i2}n^2+\cdots+A_{i(m-1)}n^m\right)q^n\) 在通解中
- 若 \(q_{i1},q_{i2}\) 是一对共轭复根 \(\rho \mathrm e^{\pm \theta\mathrm i}\)，则项 \(A_{i1}\rho^n\cos(n\theta)+A_{i2}\rho^n\sin(n\theta)\) 在通解中
线性常系数非齐次递推关系
\(k\) 阶线性常系数非齐次递推关系 \[ a_n+C_1a_{n-1}+C_2a_{n-2}+\cdots+C_ka_{n-k}=f(n) \] 先求齐次通解，非齐次特解求解如下：
当 \(f(n)=r^ng(n)\)，其中 \(g(n)\) 是 \(n\) 的 \(p\) 次多项式，\(r\) 是 \(C(x)=0\) 的 \(m\ge 0\) 重根，特解形式 \(r^n\left(k_0n^m+k_1n^{m+1}+\cdots+k_pn^{m+p}\right)\)
Ferrers 图像
自上而下的 \(n\) 层格子，第 \(i\) 层格子数为 \(m_i\)，则 \(m_i\ge m_{i+1}\) 的图像称为 Ferrers 图像
等价于一个拆分成 \(n\) 个整数的整数拆分
结论：
- 整数 \(n\) 拆分成 \(k\) 个数的和的拆分数，和数 \(n\) 拆分成最大数为 \(k\) 的数的和的拆分数相等
- 整数 \(n\) 拆分成最多不超过 \(m\) 个数的和的拆分数，和 \(n\) 拆分成最大不超过 \(m\) 的拆分数相等
- 整数 \(n\) 拆分成互不相同的若干奇数的和的的拆分数，和 \(n\) 拆分成自共轭的 Ferrers 图像的拆分数相等
指数型母函数
\[ G_e(x)=a_0+\frac{a_1}{1!}x+\frac{a_2}{2!}x^2+\frac{a_3}{3!}x^3+\cdots+\frac{a_n}{n!}x^n+\cdots \]
若元素 \(x_1\)有 \(n_1\) 个，元素 \(x_2\) 有 \(n_2\) 个，元素 \(x_k\) 有 \(n_k\) 个；组成的 \(n=\sum n_k\) 个元素中取 \(r\) 个排列，设其不同的排列数为 \(p_r\)。则序列 \(p_0,p_1,p_2,\cdots,p_n\) 的指数型母函数为 \[ G_e(x)= (1+\frac{x}{1!}+\frac{x^2}{2!}+\cdots+\frac{x^n_1}{n_1!}) (1+\frac{x}{1!}+\frac{x^2}{2!}+\cdots+\frac{x^n_2}{n_2!}) \cdots (1+\frac{x}{1!}+\frac{x^2}{2!}+\cdots+\frac{x^n_k}{n_k!}) \]
错排
递推关系 \(D_n=(n-1)(D_{n-1}+D_{n-2})\)，\(D_1=0\)，\(D_2=1\)
通项 \(D_n=\left[1-1+\frac{1}{2!}-\frac{1}{3!}+\cdots+(-1)^n\frac{1}{n!}\right]n!\)
Stirling 数
第一类 \[ x(x-1)(x-2)\cdots(x-n+1)=s(n,0)+s(n,1)x+s(n,2)x^2+\cdots+s(n,n)x^n \] 递推 \(s(n+1,k)=s(n,k-1)-ns(n,k)\)
第二类 \[ S(n,m)=mS(n-1,m)+S(n-1,m-1) \]
球与盒子
| 球有无区别 | 盒有无区别 | 允许空盒 | 不允许空盒 |
|---|---|---|---|
| 有 | 有 | \(m^n\) | \(m!S(n,m)\) |
| 有 | 无 | \(\sum_{i=1}^{\min(n,m)} S(n,i)\) | \(S(n,m)\) |
| 无 | 有 | \(C(n+m-1,n)\) | \(C(n-1,m-1)\) |
| 无 | 无 | \(G(x)=\frac{1}{(1-x)(1-x^2)\cdots(1-x^m)}\) | \(G(x)=\frac{x^m}{(1-x)(1-x^2)\cdots(1-x^m)}\) |
Catalan 数
凸 \(n\) 边形由不相交对角线拆分三角形的方案数
\(n\) 个元素确定进栈序列的出栈序列方案数
\(n\) 个矩阵连乘的结合方案数 \[ h_{n+1}=h_2h_n+h_3h_{n-1}+\cdots+h_nh_2 = \frac{1}{n}\binom{2n-2}{n-1} \]
第三章
容斥原理
\[ \left|\bigcup_{A\in C}A\right| =\sum_{s=1}^n (-1)^{s-1}\sum_{|S|=s\wedge S\subset C}\left|\bigcap_{A\in S} A\right| \]
棋盘多项式
\(r_k(C)\) 表示 \(k\) 个棋子布置到棋盘 \(C\) 上的方案数，棋盘 \(C\) 由形状表示，\(r_0(C)=1\)，\(r_0(\emptyset)=1\)；讨论一个格子有无放子，则 \(r_k(C)=r_{k-1}(C_i)+r_k(C_e)\)，其中 \(C_i\) 表示去掉该行该列，\(C_e\) 表示去掉该格；不冲突的部分乘法原则
棋盘多项式 \[ R(C)=\sum_k r_k(C)x^k \] 有禁区的排列数 \[ r_0n!-r_1(n-1)!+r_2(n-2)!-\cdots+(-1)^nr_n \] 其中 \(r_k\) 表示 \(k\) 个棋子布置在禁区的方案数
广义容斥原理
\[ \beta(m)=\sum_{k=m}^n(-1)^{k-m}\binom{k}{m}\alpha(k) \]
\(A_i\) 为有第 \(i\) 种性质的元素集合；\(\alpha(m)=\sum_{|S|=m}\left|\bigcap_{A\in S} A\right|\) 为至少有 \(m\) 种性质的元素集合；\(\beta(m)\) 为恰有 \(m\) 种性质的元素的集合
欧拉函数
\(\varphi(n)\) 小于 \(n\) 且与 \(n\) 互素的数的个数，设 \(n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\)
\[ \varphi(n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_k}\right) \]
莫比乌斯反演
莫比乌斯函数
\[ \mu(d)=\begin{cases} 1 &,\ d=1;\\ (-1)^k &,\ d=\prod_{i=1}^k p_i\\ 0 &,\ \exists p^2 | d \end{cases} \] 莫比乌斯反演定理：\(F(n)\) 和 \(f(n)\) 是定义在非负整数集合上的两个函数，并且满足 \[ F(n)=\sum_{d|n}f(d) \] 那么存在一个结论 \[ f(n)=\sum_{d|n}\mu(d)F\left(\frac{n}{d}\right) \] 性质
\[ \varphi(n)=\sum_{d|n}\mu(d)\frac{n}{d} \] 应用于圆排列问题，设集合 \(|A|=m\) 中取 \(d\) 个元素，作周期是 \(d\) 的圆排列个数为 \(M(d)\)，则为线排列计数
\[ \sum_{d|n}dM(d)=m^n \] 得 \[ nM(n)=\sum_{d|n}\mu(d)m^{\frac{n}{d}} \] 则长度为 \(n\) 的圆排列个数 \[ T(n)=\sum_{d|n}M(d)=\sum_{d|n}\frac{1}{d}\sum_{d_1|d}\mu(d)m^\frac{d}{d_1} \]
鸽巢原理
应用：\(m,n\) 是正整数，则长度为 \(mn+1\) 的无重序列 \(S\) 有一长度为 \(m+1\) 的严格增子序列或长度为 \(n+1\) 的严格减子序列
推广鸽巢原理
\(m_1,m_2,\cdots,m_n\) 都是正整数，并有 \(m_1 + m_2 +\cdots +m_n-n + 1\) 个鸽子住进 \(n\) 个鸽巢，则至少对某个 \(i\) 有第 \(i\) 个巢中至少有 \(m_i\) 个鸽子，\(i = 1 , 2 ,\cdots, n\)
推论：若 \(\overline m\ge r\)，则至少一个 \(\ge r\)
Ramsey 问题
给定一对正整数 \(a,b\)，存在一个最小的正整数 \(r\)，对 \(r\) 个顶点的完全图的边任意红、蓝２着色，存在 \(a\) 个顶点的红边完全图或 \(b\) 个顶点的蓝边完全图，记为 r ( a , b )
判定树
第四章
群
定义：满足封闭性、结合律、有幺元、有逆元
性质：设 \(a\in G\)，则存在最小乘数 \(r(a)\)，使 \(a^{r(a)}=e\)，且 \(a^{-1}=a^{r(a)-1}\)（可得费马小定理），\(r(a)\) 称为元素 \(a\) 的阶
置换
\[ P=\begin{pmatrix} 1 & 2 & \cdots & n\\ a_1 & a_2 &\cdots & a_n \end{pmatrix} \]
任何一个 \(n\) 阶有限群都同构一个 \(n\) 个文字的置换群 \(S_n\)
循环表示
\[ \begin{pmatrix} a_1 & a_2 &\cdots & a_n \end{pmatrix} = \begin{pmatrix} a_1 & a_2 &\cdots & a_n\\ a_2 & a_3 &\cdots & a_1 \end{pmatrix} \] 对换：二阶循环
奇置换，偶置换：逆序数、对换个数
偶置换构成 \(\frac{n!}{2}\) 的子群（交代群）
共轭类：循环分解中同阶循环的数量一致的置换
共轭类 \((1)^{n_1}(2)^{n_2}\cdots(m)^{n_m}\) 的元的个数
\[ \frac{n!}{\left(\prod n_i!\right)\left(\prod i^{n_i}\right)} \] \(k\) 不动置换类 \(Z_k\)，其为一个子群
等价类：元素的等价关系指 \(G\) 中存在置换能使两元素互换；含 \(k\) 的等价类称为 含 \(k\) 的轨道 \(E_k\)
Lagrange 定理：\(|E_k||Z_k|=G\)
Burnside 引理
置换群 \(G\) 将 \([1,n]\) 划分为不同等价类的个数为
\[ \frac{1}{|G|}[c_1(P_1)+c_2(P_2)+\cdots+c_1(P_g)] \] 其中 \(c_1(P_i)\) 为 \(P_i\) 作用下，不动点（长度为 1 的循环）的个数
Polya 定理
将置换群 \(\overline G\) 下的 \([1,n]\) 用 \(m\) 种颜色涂色，方案数为
\[ \frac{1}{\left|\overline G\right|}\left[m^{c(\overline P_1)}+m^{c(\overline P_2)}+\cdots+m^{c(\overline P_\overline g)}\right] \] 其中 \(c\left(\overline P_i\right)\) 是置换的循环节数
母函数形式的 Polya 定理
设同一种颜色使用 \(k\) 次，有 \[ P(G)=\frac{1}{|G|}\sum_{i=1}^g\prod_{k=1}^n\left( x_1^k+x_2^k+\cdots+x_m^k \right)^{c_k(\overline P_i)} \]
第五章
拉丁方
\(1\sim n\) 构成的 \(n\) 阶方阵中，每行（每列）中 \(n\) 个元素都只能出现一次
正交拉丁方：设 \(A_{n\times n}\)，\(B_{n\times n}\)，是两个 \(n\) 阶拉丁方，\(C_{ij}=(A_{ij}, B_{ij})\) 若 \(C\) 中的所有数偶互不相同，则 \(A\) 与 \(B\) 正交
若存在 \(r\) 个 \(n\) 阶正交拉丁方，则 \(r< n\)
Galois 域
域：加法交换群，除去加法幺元成乘法交换群，有分配律
若 \(p\) 是素数，\(\{0,1,2,\cdots,p-1\}\) 在 \(\mod p\) 意义下 \(+\)，\(\times\) 成伽罗瓦域 \(GF(p)\)
\(GF(p)\) 上的多项式 \(GF[p,x]\)
若 \(p(x)\in GF[p,x]\) 不可表示为两个多项式的积，则称其不可化约
设 \(m(x)\) 是 \(GF[p,x]\) 上不可约 \(n\) 次多项式，则可将 \(GF[p,x]\) 划分为模 \(m(x)\) 同余类 \(GF[p,m(x)]\)，其元素构成域 \(GF(p^n)\)
正交拉丁方构造
若 \(n=p^m\)，则存在 \(n-1\) 个正交拉丁方：
设 \(\alpha_1,\alpha_2,\cdots,\alpha_n\) 是 \(GF(p^m)\) 的 \(n\) 个不同元素，其中 \(\alpha_n=0\)
构造方阵序列 \(A_{n\times n}^{(k)}\)，其中 \(a_{ij}^{(k)}=\alpha_k\cdot \alpha_i+\alpha_j\)
若 \(n=p_1^{m_1}p_2^{m_2}\cdots p_k^{m_k}\)，则存在 \(\min\{p_1^{m_1},p_2^{m_2},\cdots ,p_k^{m_k}\}-1\) 个正交拉丁方
均衡不完全区组设计
\(BIBD(b,v,r,k,\lambda)\)
\(X=\{x_1,x_2,\cdots,x_v\}\)，\(B=\{B_1,B_2,\cdots,B_b\}\)，\(B_i\subset X\)，\(|B_i|=k\)
\(X\) 的任一元素正好在 \(r\) 个子集中出现
\(X\) 的任意一对元素正好在 \(\lambda\) 个子集出现
与某元同组的总元次 \(r(k-1)=\lambda(v-1)\)
所有元素总元次 \(vr=bk\)
有 \(b\ge v\)
区组矩阵： \[ a_{ij}=\begin{cases} 1 &,\ x_i\in B_j\\ 0 &,\ x_i \notin B_j \end{cases} \] 对于 BIBD 设计，\(AA^{\mathrm T}=(r-\lambda)I+\lambda J\)，其中 \(J\) 是全 1 矩阵
对称均衡不完全区组设计
\(b=v\)
\(k=r\)
任意两组均有 \(\lambda\) 个共同元素
三连系
\(k=3\) 的 BIBD 称为三连系
\(\lambda = 1\) 的三连系称为 Steiner 三连系，存在的充要条件 \(v\equiv 1\mod 6 \vee v\equiv 3\mod 6\)