蒟蒻的组合数学实在是太弱了，所以在初赛之前赶紧来复习一下，大部分内容由 \(OI-Wiki\) 整合而来。
普及知识点标 \(J\)，提高知识点标 \(S\)
加法原理&乘法原理（\(J\)）
加法原理
假设完成一项任务有 \(n\) 种方案，每种方案的办法数目为 \(a_i\)，则完成这项任务的总方法数为 \(a_1+a_2+\cdots+a_n\)。
乘法原理
假设完成一项任务分 \(n\) 个步骤，每种步骤又有 \(a_i\) 个办法，则完成这项任务的总方法数为 \(a_1\times a_2\times\cdots\times a_n\)。
一些排列组合的符号（\(J\)）
排列数
从 \(n\) 个元素中选择 \(m\) 个组成的排列个数（\(n,m\in\mathbb{N},m\leq n\)），用符号 \(A_n^m\) 或 \(P_n^m\) 表示，即
\[A_n^m=n(n-1)(n-2)\cdots(n-m+1)=\dfrac{n!}{(n-m)!} \]如何理解？假设有 \(n\) 个人，我们要从中选择 \(m\) 个人来排队。对于第一个位置，我们有 \(n\) 个人可以选；因为选掉了一个人，第二个位置就只剩下 \((n-1)\) 个人可以选。依次类推，第 \(m\) 个位置就有 \((n-m+1)\) 个人可以选，根据乘法原理把它们相乘起来就是了。
全排列
即 \(n\) 个元素组成的排列个数：\(A_n^n=n!\)
排列数的递推公式
\[\text{递推边界：}\forall i\in\mathbb{N},A_i^1=1 \]\[A_n^m=A_n^{m-1}\times(n-m+1) \]\[\]组合数
从 \(n\) 个元素中选择 \(m\) 个组成的组合个数（\(n,m\in\mathbb{N},m\leq n\)），用符号 \(C_n^m\) 表示，为了表达方便可以简写成 \(\dbinom{n}{m}\)，即
\[C_n^m=\dfrac{A_n^m}{m!}=\dfrac{n!}{m!(n-m)!} \]如何理解？如果我们从 \(n\) 个人中选 \(m\) 个人，如果不在乎顺序，就是 \(C_n^m\)，如果在乎顺序，则选出来的 \(m\) 个人还要再全排，得到 \(A_n^m\)。则
\[A_n^m=C_n^m\times A_m^m=C_n^m\times m! \]组合数的递推公式
\[\text{递推边界：}\forall i\in\mathbb{N},C_i^0=1 \]\[C_n^m=C_{n-1}^{m}+C_{n-1}^{m-1} \]如何理解这个递推公式？我们只需要简单的举个例子。我们可以把 \(C_n^m\)
这个方案，分成两个集合：包含 \(1\) 与不包含 \(1\)。
如果不包含 \(1\) 这个数，则我们需要在剩下的 \(2\) 到 \(n\) 这 \((n-1)\) 个数里面选择 \(m\) 个数，即 \(C_{n-1}^{m}\)。
如果包含，则我们需要在剩下的 \(2\) 到 \(n\) 这 \((n-1)\) 个数里面选择 \((m-1) 个数\)，即 \(C_{n-1}^{m-1}\)。根据加法原理把两个集合的方案相加即可。
组合数一些简单的东西
组合数的对称性（\(J\)）
\[\dbinom{n}{m}=\dbinom{n}{n-m} \]\(proof:\) 即对选出来的集合对全集取补集，数值不变。
二项式定理（\(S\)）
\[(a+b)^n=\sum_{i=0}^n\dbinom{n}{i}a^{i}b^{n-i} \]其用组合数阐明了一个展开式的系数，可以用数学归纳法证明，可是窝太菜了不会，只好给出我的非数学归纳法的证明：
首先我们可以把左边的柿子化成
\[\begin{matrix}\underbrace{(a+b)(a+b)\cdots+(a+b)}\\n\text{个}(a+b)\end{matrix} \]这个柿子展开后有 \(2^n\) 项，我们要将展开后的柿子合并同类项，最终每一项都形如 \(k\times a^ib^{n-i}\)。我们想知道的就是前面的 \(k\)，那么我们就得出一个问题，对于每一个 \(i\ (0\le i\le n)\)，有多少个 \(a^ib^{n-i}\)，即从 \(n\) 个 \(a\) 中选 \(i\) 个 \(a\) 方案个数（剩下的都是 \(b\) 所以不用管），即 \(\dbinom{n}{i}\)。所以 \(k=\dbinom{n}{i}\)，所以二项式定理成立。
杨辉三角（\(J\)）
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
这是杨辉三角的 \(0\) 至 \(10\) 行，我们会发现第 \(i\) 行第 \(j\) 个数（\(j\) 从 \(0\) 开始）对应着 \((a+b)^i\) 展开式的系数 \(\dbinom{i}{j}\)，第 \(n\) 行 \(m\) 列的数（设为 \(a_{n,m}\)）的递推式为
\[a_{n,m}=a_{n-1,m}+a_{n-1,m-1} \]由于 \(a_{n,m}=\dbinom{n}{m}\)，可以推出
\[\dbinom{n}{m}=\dbinom{n-1}{n}+\dbinom{n-1}{m-1} \]这同时也证明了组合数的递推式。
组合数的另一个递推式
\[\dbinom{n}{m}=\dfrac{n}{m}\dbinom{n-1}{m-1} \]\(proof:\)
\[\dbinom{n}{m}=\dfrac{n!}{m!(n-m)!}=\dfrac{n}{m}\times\dfrac{(n-1)!}{(m-1)!(n-1-m+1)!}=\dfrac{n}{m}\dbinom{n-1}{m-1} \]其他一些杂七杂八的东西
\[\dbinom{n}{0}+\dbinom{n}{1}+\cdots+\dbinom{n}{n}=\sum_{i=0}^n\dbinom{n}{i}=2^n\qquad\qquad(1) \]\[\dbinom{n}{0}-\dbinom{n}{1}+\dbinom{n}{2}-\cdots+(-1)^n\dbinom{n}{n}=[n=0]\qquad\quad(2) \]\[\dbinom{n}{0}+\dbinom{n}{2}+\dbinom{n}{4}+\cdots=\dbinom{n}{1}+\dbinom{n}{3}+\dbinom{n}{5}+\cdots=2^{n-1}\quad(3) \]\(proof:\) 当 \(a=b=1\) 时，代入二项式定理可以证明 \((1)\) 式；当 \(a=1,b=-1\) 时，代入二项式定理可证明 \((2)\) 式；\(\frac{(1)\text{式}+(2)\text{式}}{2}\) 可以证明 \((3)\) 式。
一些解题技巧
例题1. 六个人站一排，求
（1）甲不在排头，乙不在排尾的方案数。
（2）在上一小问的前提下，甲乙不相邻的方案数。
可以先思考一下。
解答：
（1）：对于这类题，我们可以用“正难则反”的方法。什么叫正难则反呢？就是对于从正面很难解答的题型，我们从反面来推。
如这道题，我们发现直接硬算很麻烦，我们可以换一种思路：求出六个人的全排列，再减去甲在排头的方案数和乙在排尾的方案数就行了。答案为
\[A_6^6-A_5^5-A_5^5=6!-5!-5!=480 \]如果您觉得这正确，那就大错特错了，因为甲在排头，并且乙在排尾被多减了一次！根据容斥原理，我们要把多减去的那部分再加回来，所以正确的答案应该是
\[A_6^6-A_5^5-A_5^5+A_4^4=504 \]（2）： 这里我们用分类讨论的方法，我们分四种情况讨论：
-
甲在排尾，乙在排头：显然，甲乙位置确定中间四个随便排，方案数为 \(A_4^4\)。
-
甲在排尾，乙不在排头：那么乙只有 \(3\) 种选择（不在排头，且不与甲相邻），剩下的四人随便排，方案数为 \(3\times A_4^4\)。
-
甲不在排尾，乙在排头：对称地，方案数为 \(3\times A_4^4\)。
-
甲不在排尾，乙不在排头：我们还可以再分讨：
- 甲在 \(2\) 号位：那么乙只有两种选法，方案数为 \(2\times A_4^4\)。
- 甲在 \(3\) 号位：那么乙只有一种选法，方案数为 \(A_4^4\)。
- 甲在 \(4\)、\(5\) 号位的情况分别于在 \(3\)、\(2\) 号位的情况相同。
综上，总方案数为
\[A_4^4+3\times A_4^4\times 2+2\times A_4^4\times2+A_4^4\times2=312 \]例题2. 八个人站一排，求
（1）甲乙必须相邻的排列数。
（2）甲乙必须不相邻的排列数。
解答：
（1）：对于这类题，我们可以采用捆绑法，即将甲乙看作一个人，那么就是七个人求全排列，同时甲乙之间是有序的，其内部还需要全排列，所以答案为
\[A_7^7*A_2^2=10080 \]（2）：这个就很水了，“正难则反”，用八个人的全排列减去甲乙相邻的方案数就行，答案不用我说了。
例题3.
某人射击 \(8\) 枪，命中 \(4\) 枪，恰好有 \(3\) 枪连续命中，有多少种不同情况？
解答：
这题应使用捆绑法解答，把连续的 \(3\) 枪看作一个，但注意是恰好有 \(3\) 枪连续命中，也就是说另外一枪和这三枪不能相邻，如果容斥或者分讨将会非常麻烦，有什么更简单的方法呢？
这里就要使用我们的插空法，有时也叫隔板法。
什么意思呢？我们将没命中的四枪提取出来，
_·_·_·_·_
我们发现，相邻两枪中间都有空位，总共有 \(4+1=5\) 个空位，我们只要将捆绑的 \(3\) 枪和另外一枪插入到这些空位中，不就满足它们不相邻了嘛？由于这几枪都是无序的，所以答案就是 \(C_5^2\)。
例题4.
求不定方程 \(\sum\limits_{i=1}^nx_i=m\) 的正整数解个数。
解答：
这题需要用到隔板法，我们把 \(m\) 想象成 \(m\) 个相同的小球，我们要把这些小球分成 \(n\) 份有多少个方案呢？我们可以在这些小球之间的空位中放入 \((n-1)\) 个隔板（一个空位最多只能放一个隔板），这样就能把这些小球分成 \(n\) 份了。由于两端不能放隔板，所以有 \((m-1)\) 个空位，答案为 \(C_{m-1}^{n-1}\)。
例题5.
求不定方程 \(\sum\limits_{i=1}^nx_i=m\) 的非负整数解个数。
这题看似和上一题一样，但 \(x_i\) 变成了非负整数，也就是说 \(x_i\) 可以为 \(0\)，那这样隔板可以放在一起，这怎么算呢？
令 \(y_i=x_i+1\)，则有 \(\sum\limits_{i=1}^{n}y_i=m+n\)。我们发现，这里的 \(y_i\) 都是正整数，且每一个 \(y_i\) 的解都对应一个 \(x_i\)，那么我们就很好地转化成了上题，答案即为 \(C_{m+n-1}^{n-1}\)。
组合数学进阶（\(S\)）
卡特兰数
定义 \(H_n\) 为卡特兰数的第 \(n\) 项。
亿些递推公式
递推边界： \(H_0=1.\)
\[H_n=\dfrac{\binom{2n}{n}}{n+1} \]\[H_n=\dfrac{H_{n-1}(4n-2)}{n+1}\quad\text{线性递推，超好用！！1} \]\[H_n=\dbinom{2n}{n}-\dbinom{2n}{n-1} \]\[H_n=\begin{cases}\sum_{i=1}^nH_{i-1}H_{n-i} & n\ge2 \\1 & n=1,0\end{cases} \]要用到卡特兰数的问题
-
有 \(2n\) 个人排成一行进入剧场。入场费 \(5\) 元。其中只有 \(n\) 个人有一张 \(5\) 元钞票，另外 \(n\) 人只有 \(10\) 元钞票，剧院无其它钞票，问有多少中方法使得只要有 \(10\) 元的人买票，售票处就有 \(5\) 元的钞票找零？
-
一位大城市的律师在她住所以北 \(n\) 个街区和以东 \(n\) 个街区处工作。每天她走 \(2n\) 个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
-
在圆上选择 \(2n\) 个点，将这些点成对连接起来使得所得到的 \(n\) 条线段不相交的方法数？
-
对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方法数？
-
一个栈（无穷大）的进栈序列为 \(1,2,3,\cdots,n\)，有多少个不同的出栈序列？
-
\(n\) 个结点可构造多少个不同的二叉树？
-
将 \(n\) 个 \(+1\) 和 \(n\) 个 \(-1\) 构造成 \(2n\) 项的数列 \(a_1,a_2,\cdots,a_{2n}\)，满足 \(\forall k\in[1,2n],\sum_{i=1}^k a_i \ge0\) 的方案数为？
第二类斯特林数
不说第一类是因为第一类不常见。
例题：P3904 三只小猪
定义：\(S(n,m)\) （或简写成 \(\begin{Bmatrix}n\\m\end{Bmatrix}\)）表示将 \(n\) 个两两不同的元素，划分为 \(m\) 个互不区分的非空子集的方案数。
递推公式
递推边界 \(S(n,0)=[n=0].\)
\[S(n,m)=S(n-1,m-1)+m\times S(n-1,m) \]递推式的解释可见我的题解
错排列
例题：P1595 信封问题
定义: \(f(n)\) 表示将 \(n\) 个元素错排（就是第 \(i\) 个元素不能放到第 \(i\) 个位置）的方案数。
递推公式：
递推边界：\(f(0)=0,f(1)=1.\)
\[f(n)=(n-1)(f(n-1)+f(n-2)) \]如何理解？对于第 \(n\) 个元素，它肯定不能放在第 \(n\) 个位置，只能放在前面的 \((n-1)\) 个位置上，设 \(k=1,2,\cdots,n-1\)，我们可以把第 \(n\) 个元素放在第 \(k\) 个位置上，而原来第 \(k\) 个位置上的元素有两种选择：
-
交换到第 \(n\) 个位置上，方案数就是对剩下的 \((n-2)\) 个元素错排，即 \(f(n-2)\)。
-
不到第 \(n\) 个位置上，方案数就是除去第 \(n\) 个位置外的 \((n-1)\) 个元素错排，即 \(f(n-1)\)。
对于 \(k\) 有 \((n-1)\) 种取值，总方案数即为 \(f(n)=(n-1)(f(n-1)+f(n-2))\)。
圆排列
定义：\(n\) 个人全部来围成一圈，所有的排列数记为 \(Q_n^n\)。
由于从不同的位置断开会变成不同的队列，有
\[Q_n^n\times n=A_n^n\Rightarrow Q_n^n=\dfrac{A_n^n}{n}=(n-1)! \]由此可知，从 \(n\) 个人中选 \(m\) 个人来围成一圈的排列数为
\[Q_n^m=\dfrac{A_n^m}{m}=\dfrac{n!}{m\times(n-m)!} \]容斥原理
直接看 \(oi-wiki\) 吧太多了不想写（
鸽巢原理
也叫抽屉原理，它常被用于证明存在性和求最坏情况下的解。——\(OI-Wiki\)
简单情况
将 \(n+1\) 个元素分成 \(n\) 组，那么至少一组有两个（或以上）个元素。
证明显然。
推广到一般情况
将 \(n\) 个元素分成 \(k\) 组，则至少一组有大于等于 \(\Big\lceil\dfrac{n}{k}\Big\rceil\) 个元素。
反证法证明，假设每组有小于 \(\Big\lceil\dfrac{n}{k}\Big\rceil\) 个元素，则每组最多有 \((\Big\lceil\dfrac{n}{k}\Big\rceil-1)\) 个元素。
\(\because(\Big\lceil\dfrac{n}{k}\Big\rceil-1)\times k=k\Big\lceil\dfrac{n}{k}\Big\rceil-k<k(\dfrac{n}{k}+1)-k=n\).
\(\therefore\) 矛盾.
总结，将 \(n\) 个元素划分成 \(A_1,A_2,\cdots,A_k\) ,\(k\) 个集合，则至少有一个集合 \(A_i\) 满足 \(A_i\ge\Big\lceil\dfrac{n}{k}\Big\rceil\)。