目录
组合数学学习笔记
设事件\(A\)有\(m\)种产生方式，事件\(B\)有\(n\)种产生方式，事件\(A\)与事件\(B\)相互独立，那么“事件\(A\)或\(B\)”共有\(m+n\)种产生方式。
加法法则注重于分类问题的解决。
设事件\(A\)有\(m\)种产生方式，事件\(B\)有\(n\)种产生方式，事件\(A\)与事件\(B\)相互独立，那么“事件\(A\)与\(B\)”共有\(m*n\)种产生方式。
乘法法则注重于分步问题的解决。
从\(n\)个不同的元素中取出\(r\)个元素，按次序排列的方案数，称作从\(n\)个中取\(r\)个的无重排列，用\(A(n,r)\)表示。
\[
A_n^r = \frac{n!}{(n-r)!}
\]
从\(n\)个元素中取\(r\)个元素，每个元素可以重复取，方案数为\(n^r\)，即每个位置有\(n\)个选择，共\(r\)个位置。
从\(n\)个元素中取出\(r\)个元素形成一个环，最终环的个数。
方案数为\(\frac{A(n,r)}{r}\)，即先考虑所有的排列情况并将其连接成环，一个环从中间断开会形成\(r\)个序列，那么所有的情况除以\(r\)则得到最终方案数。
类似于圆排列，但是项链可以翻转，所以方案数为：
\[
\frac{A(n,r)}{2r}
\]
设元素\(a_1,a_2,\cdots,a_k\)互不相同，每个元素有\(n_i\)个，那么所有元素的全排列为：
\[
\frac{n!}{n_1!n_2!\cdots n_k!}
\]
可记为\(n\choose n_1n_2\cdots n_k\)。
可以理解为：先将所有的元素打上标号，那么就全为不同的元素，此时方案数为\(n!\)，之后对于每一类元素消除其冗余度\(n_i!\)即可。
带限制的排列问题可以用指数型母函数解决。
从\(n\)个元素中取出\(r\)个元素，不考虑元素之间的顺序时，总的方案数。记为\(C(n,r)\)或者\(n\choose r\)。
有公式：
\[
C(n,r)=\frac{n!}{r!(n-r)!}
\]
从\(n\)个元素中取出\(r\)个数，每个元素可以重复取的组合方案数。
可以将问题等价于：把\(r\)个元素划分成\(n\)类，每类元素个数没有要求。
那么方案数即为：
\[
C(r+n-1,n-1)
\]
相当于求解\(x_1+x_2+\cdots+x_r=n\)的非负整数解的方案数，采用隔板法即可求解。
从\(A=\{1,2,\cdots,n\}\)中取\(r\)个不相邻的组合方案数，其组合数为
\[
C(n-r+1,r)
\]
可采用标号法来求解，假设选取任意一个解\(S=\{1,3,\cdots,n\}\)，因为是组合，我们将其按照升序排列，对应位置的下标为\(\{0,1,\cdots,r-1\}\)。我们将元素与对应下标相减（去掉限制条件），那么有\(S'=\{1,2,\cdots,n-r+1\}\)。易知问题转变成了从\(n-r+1\)个数中选取\(r\)个数的组合数。这两者的方案数是一一对应的。
相同的方法可以用来求解可重组合数，只是我们要累加元素的下标（可以去掉重复），同样可以得到上述结果。
可用普通母函数解决。
组合数为二项式定理展开式中对应项的系数：
\[
(x+y)^n=\sum_{i=0}^n C(n,i)x^iy^{n-i}
\]
相当于\((x+y)\cdot (x+y)\cdot \cdots \cdot (x+y)\)中，每一项只会选取一个，那么若\(x\)选取了\(i\)个，对应\(y\)选取了\(n-i\)个，方案数为\(C(n,i)=C(n,n-i)\)。
根据这个，令\(x=y=1\)则有：
令\(x=1,y=-1\)有：
还有些其它的式子：
考虑第\(m\)个元素选还是不选，分类过后加起来即可。
组合数还有一些其它的恒等式，就不一一列举了(懒)。
另外，二项式定理还可以扩展为多项式定理：
\[
(x_1+x_2+\cdots+x_t)^n=\sum_{n_1+\cdots+n_t=n}{n\choose n_1n_2\cdots n_t}x_1^{n_1}x_2^{n_2}\cdots x_t^{n_t}
\]
原理是
\[C(n,n_1)\cdot C(n-n_1,n_2)\cdot \cdots \cdot C(n-n_1-n_2-\cdots-n_{t-1}, n_t)={n\choose n_1n_2\cdots n_t}
\]
可见多项式的系数刚好对应多重集的排列个数。
直观点来说，母函数就是一列用来展示一串数字的挂衣架。一般母函数也被称作“生成函数”。
举个例子，序列\(\{a_n\}\)的母函数即为：
\[
G(x)=\sum_{i=0}^{\infty}a_ix^i
\]
母函数一般分为两类：普通型母函数和指数型母函数。其中，普通型母函数主要用来解决多重集的组合问题，而指数型母函数一般用来解决多重集的排列问题。同时，母函数还可以解决递归数列的通项问题。
用\(1\)~\(m\)之间的整数凑出整数\(n\)的方案数。
如果是有序拆分，相当于\(n\)个无区别小球放入\(m\)个有区别盒子，不允许空盒的方案数，答案为\(C(n-1,r-1)\)。
这里是无序拆分。
对于\(1\)~\(m\)之间的每个整数单独考虑，问题相当于将\(n\)个没有区别的小球划分入\(m\)个没有区别的盒子中且允许有空盒的存在。
每一个的生成函数序列为：
\[
G_i(x)=1+x^i+x^{2i}+\cdots
\]
对于\(i=1\)来说：\(G_1(x)\)表示\(1\)这个数取\(0,1,2\cdots\)个的方案数都为\(1\)，其余同理。
又因为\(G_i(x)=\frac{1}{1-x^i}\)，所以最终的答案为\(G(x)=\prod G_i(x)\)这个多项式中\(x_n\)前面的系数。
直接说结论吧，通过\(Ferrers\)图观察可以得到：
母函数是求解递推式中数列通项的一大利器。
比如汉诺塔问题中，递推式为：
\[
h(n)=2h(n-1)+1,h(1)=1
\]
那么我们构造出序列\(\{h_n\}\)的母函数为：
\[
G(x)=\sum_{i=1}^{\infty}h_ix^i
\]
然后我们利用递推关系来求解：
\[
\begin{aligned}
&x^2:h(2)=2h(1)+1\\
&x^3:h(3)=2h(2)+1\&\cdots
\end{aligned}
\]
对应相乘，左边就变为：
\[
G(x)-h_1x=G(x)-x
\]
右边变为：
\[
\begin{aligned}
&2xG(x)+x^2+x^3+\cdots \=&2xG(x)+x^2(1+x+x^2+\cdots)\=&2xG(x)+\frac{x^2}{1-x}
\end{aligned}
\]
然后解得：
\[
\begin{aligned}
G(x)=&\frac{x}{(1-x)\cdot (1-2x)}\=&\frac{1}{1-2x}-\frac{1}{1-x}
\end{aligned}
\]
因为\(1-x=\sum_{i=0}^{\infty}x_i\)，所以就能得到\(h(n)=2^n-1\)。
一般求解递推式的通项都是用的这种方法，后面还有更加简便的方法~
刚才的普通型母函数中，其实可以发现求解的问题一般是“组合类”的问题，只关心元素的选取而没有关心元素的顺序。
倘若在整数拆分中，选取了\(n_i\)个\(a_i\)，现在要关心顺序，那么答案即为多重集的排列数：\(n\choose n_1n_2\cdots n_t\)。
那放在母函数里面，我们可以将式子变为：
\[
G(x)=1+\frac{x}{1!}+\frac{x^2}{2!}+\cdots
\]
这样选取不同的元素以及不同的个数就自动算好了分母部分。
那么对于\(\{a_n\}\)序列，称\(G_e(x)=\sum_{n=0}^{\infty}a_n\frac{x^n}{n!}\)为\(\{a_n\}\)的指数生成函数。
用\(1,2,3,4\)构成一个五位数，要求\(1\)出现不超过\(2\)次，不能不出现；\(2\)出现不超过\(1\)次；\(4\)出现的次数为偶数。
易知这是一个排列的问题，那么对每种限制构造对应的指数型母函数：
那么将这几个相乘，最终\(\frac{x^5}{5!}\)前面的系数即为答案。
给出\(n\)个元素从\(1\)到\(n\)，并且存在\(n\)个位置。现在问使得所有的元素都不在其原来位置上的方案数。
先考虑递推：设\(D_n\)为\(n\)个数的错排答案，那么考虑第\(n\)个数：
这两种情况不重不漏的计算出了所有的情况，那么递推式为\(D_n=(n-1)\cdot (D_{n-1}+D_{n-2})\)。
考虑利用指数型母函数求其通项：
将递推式变换得到：
\[
\begin{aligned}
D_n-nD_{n-1}=&-[D_{n-1}-(n-1)D_{n-2}]\=&(-1)^{n-1}(D_1-D_0)
\end{aligned}
\]
因为\(D_0=0,D_1=1\)，有\(D_n-nD_{n-1}=(-1)^n\)。
然后设出相关生成函数：
\[
G_e(x)=D_0+D_1\frac{x}{1}+\cdots
\]
按照之前的办法，通过递推式来求解通项：
\[
\begin{aligned}
&\frac{x}{1}:D_1=D_0-1\&\frac{x^2}{2!}:D_2=2D_1+1\&\cdots
\end{aligned}
\]
对应相乘就有：
\[
G_e(x)=xG_e(x)+e^{-x}
\]
解得
\[G_e(x)=\frac{e^{-x}}{1-x}=\frac{(1-x+\frac{x^2}{2!}-\cdots)}{1-x}\]
那么就相当于两个函数相乘，最终有
\[
D_n=n!\cdot (\frac{1}{0!}-\frac{1}{1!}+\frac{1}{2!}-\cdots \pm \frac{1}{n!})
\]
同样，用类似的方法，通过指数型母函数也能得到递推方程的通项公式。
在算法竞赛中，多项式相乘可以通过\(FFT\)优化达到\(O(nlogn)\)的复杂度。
主要说一下线性齐次常系数递推关系，非齐次的话一般就是在其次的基础上加一个特殊解就行了。
如果序列\(\{a_n\}\)满足
\[
a_n+c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k}=0
\]
并且\(a_0=d_0,a_1=d_1,\cdots a_{k-1}=d_{k-1},c_i,d_i\)都为常数。
那么上式就为\(\{a_n\}\)的\(k\)阶线性常系数齐次递推关系。
特点：
假设现在有\(a_n+c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k}=0\)，那么现在想要求出其通项，还是利用之前提到的方法（我就不细写了），设\(G(x)\)为序列\(\{a_n\}\)的母函数，那么就有：
\[
G(x)=\frac{P(x)}{1+C_1x+\cdots+C_kx^k}
\]
这里\(P(x)\)为另一个多项式，先暂且不管。
我们来分析分母，根据之前的经验，我们希望将其化为\(\prod (1-a_ix)\)的形式，那么这样就很方便求通项了。
先提取一个\(x_k\)出来，并且令\(m=x^{-1}\)，那么有\(C(m)=(m^k+C_1m^{k-1}+\cdots+C_k\))。
之后进行因式分解为：
\[
C(m)=(m-a_1)^{k_1}(m-a_2)^{k_2}\cdots (m-a_i)^{k_i},k_1+k_2+\cdots+k_i=k.
\]
之后我们将\(x_k\)对应乘进去，就得到分母的表达式：
\[
(1-a_1x)^{k_1}(1-a_2x)^{k_1}\cdots (1-a_ix)^{k_i}
\]
这样转换为之前的形式，求解就较为方便了。
观察\(C(m)\)，发现它与递推式很像。那么在此给出特征多项式的定义：
对于一个线性常系数齐次递推式（以之前的方程为例），其特征多项式为：
\[
x^k+a_1x^{k-1}+\cdots+a_k
\]
相应地，对于\(k\)阶常系数线性递推方程，其特征方程为：
\[
x^k+a_1x^{k-1}+\cdots+a_k=0
\]
特征方程的根为特征根。
拿之前汉诺塔为例：
我们已知递推关系为\(h(n)=2\cdot h(n-1)-1\)，变换一下为\(h(n)-2\cdot h(n-1)=-1\)。
因为右端不为\(0\)，我们减一下，有：
\[
h(n)-3\cdot h(n-1)+2\cdot h(n-2)=0
\]
得到其递推方程：
\[
x^2-3x+2=0
\]
因式分解为：
\[
(x-1)\cdot (x-2)=0
\]
那么回顾之前的式子，我们没有管分子，所以用待定系数法表示出通项：
\[
h(n)=1^nA+2^nB
\]
显然\(h(0)=0,h(1)=1\)，代入求解即可得\(h(n)=2^n-1\)。
总结一下步骤：
可见，通过母函数，能够快速求解一类递推关系的问题，通过特征多项式，将母函数和通解相联系。
现在已知递推关系：\(a_n-4a_{n-1}+4a_{n-2}=0,a_0=1,a_1=4\)，求解通项。
按照之前方法来推，最终得到：
\[
G(x)=\frac{ax+b}{(1-2x)^2}
\]
拆开为：
\[
G(x)=\frac{A}{1-2x}+\frac{B}{(1-2x)^2}
\]
那么
\[
G(x)=A(1+2x+2^2x^2+\cdots)+B(1+2x+\cdots)(1+2x+2^2x^2+\cdots)
\]
可以得到\(a_n=2^n\cdot A+(n+1)\cdot 2^n\cdot B\)
那么之后求解系数即可。
所以对于有重根的情况，假设现在有\(e\)重根\(q\)，可以直接得到其对应的解为
\[
(A_0+A_1n+\cdots+A_{e-1}n^{e-1})q^n
\]
这里我列举了一个例子方便理解，要证明的话较为复杂，稍微严谨点的证明如下(太菜了不敢乱说话)
设\(q\)为特征方程的\(e\)重根，那么最终的\(G(x)=\sum_{j=1}^{e}\frac{A_j}{(1-qx)^j}\)。
根据这个写出第\(n\)项的表达式：
\[
a_n=\sum_{j=1}^{e}A_jq^nC(n+j-1,j-1)
\]
这里\(C(n+j-1,j-1)\)是关于\(n\)的\(j-1\)次多项式，那么最终的式子是关于\(n\)的\(e-1\)次多项式。
同样用待定系数法表示出来有：
\[
a_n=q^n(A_0+A_1n+\cdots+A_{e-1}x^{e-1})
\]
得证。
递推式为：
\[
F_n=F_{n-1}+F_{n-2},F_1=F_2=1
\]
根据递推式可以推出一些恒等式：
将\(F_i\)用\(F_{i+1}-F_{i-1}\)表示，那么\(F_i^2=F_iF_{i+1}-F_iF_{i-1}\)，所有累加起来即可得到等式右边。
用\(F_{i+2}-F_{i+1}\)表示\(F_i\)即可。
\(F_{2i+1}=F_{2i+2}-F_{2i}\)，然后累加起来即可。
证明的话可以将斐波那契线性递推写成矩阵的形式就一目了然了。
数学归纳法可证。
除开恒等式外，还有一些其它的性质：
斐波那契的通项，用母函数随便求啦。
卡特兰数有一些经典的模型：进出栈问题、二叉树构成、划分三角形等等。
一般的特征就是：在问题中始终存在一个\(\geq\)关系，比如进出栈问题，保证入栈数不小于出栈数；括号问题，左括号数不小于右括号数等等。
卡特兰数的递推式
\[
c_n=\sum_{i=0}^{n-1}c_ic_{n-i-1}
\]
求解通项，比较简便的话可以用格路模型来解，为：
\[
c_{n}={2n\choose n}-{2n\choose n-1}
\]
下面给出母函数的求解法：
首先设出对应生成函数:
\[
G(x)=c_0+c_1x+c_2x^2+\cdots
\]
根据递推式，将其平方得：
\[
G^2(x)=\sum_{i=0}^{\infty}\sum_{j=0}^{i}c_jc_{i-j}x^i=\sum_{i=0}^{\infty}c_{i+1}x^i
\]
有：
\[
xG^2(x)=G(x)-1
\]
最终求解得到：
\[
G(x)=\frac{1-\sqrt{1-4x}}{2x}
\]
然后对\(\sqrt{1-4x}=(1-4x)^{\frac{1}{2}}\)用牛顿二项式展开得：
\[
\begin{aligned}
&1+\sum_{i=1}^{\infty}\frac{\frac{1}{2}\cdot (-\frac{1}{2})\cdot \cdots \cdot (\frac{1}{2}-i + 1)}{i!}(-4x)^i\=&1+\sum_{i=1}^{\infty}(-1)^{i-1}\frac{1\cdot 3\cdot \cdots \cdot (2i-3)}{2^ii!}(-4x)^i\=&1+\sum_{i=1}^{\infty}(-1)^{i-1}\frac{(2i-2)!}{2\cdot 4\cdot\cdots\cdot (2i-2)\cdot 2^ii!}(-4x)^i\=&1+\sum_{i=1}^{\infty}(-1)^{i-1}\frac{(2i-2)!}{(i-1)!\cdot 2^{2i-1}i!}(-4x)^i\\end{aligned}
\]
分子为：
\[
\begin{aligned}
&-\sum_{i=1}^{\infty}(-1)^{i-1}\frac{(2i-2)!}{(i-1)!\cdot 2^{2i-1}i!}(-4x)^i\=&\sum_{i=1}^{\infty}\frac{2\cdot (2i-2)!}{(i-1)!\cdot i!}x^i\=&\sum_{i=1}^{\infty}{2i-2\choose i-1}\frac{2}{i}x^i\=&\sum_{i=0}^{\infty}{2i\choose i}\frac{2}{i+1}x^{i+1}\\end{aligned}
\]
最后再除以一个\(2x\)，式子就变为：
\[
\sum_{i=0}^{\infty}\frac{1}{i+1}{2i\choose i}x^i
\]
所以得到卡特兰数得通项为：
\[
c_n=\frac{1}{n+1}{2n\choose n}
\]
第一类斯特林数表示的是将\(n\)个数分为\(k\)个圆环的方案数，两个圆环不同当且仅当一个圆环通过旋转不能得到另一圆环。
其中，第一类斯特林数也分为两类：无符号斯特林数和有符号斯特林数，无符号斯特林数记为\(\left[^n_k\right]\)，有符号斯特林数一般记为\(s(n,k)\)(我貌似也不是很清楚记法...)。
第一类斯特林数有如下递推公式：
\[
\begin{aligned}
\begin{bmatrix}
n+1 \\ k
\end{bmatrix}
=n\cdot\begin{bmatrix}
n \\ k
\end{bmatrix}
+\begin{bmatrix}
n \\ k-1
\end{bmatrix}
\end{aligned}
\]
分别表示当前第\(n+1\)个数和之前的划分在一起还是单独成一个圈，和其它元素在一起的话那么有\(n\)种可能。
对于有符号的第一类斯特林数，递推公式为：
\[
s(n+1,k)=n\cdot s(n,k)+s(n,k-1)
\]
无符号第一类斯特林数对应递增阶乘展开式的各项系数：
\[
x_{(n)}=\prod_{i=0}^{n-1}(x-i)=\sum_{i=0}^{n}\begin{bmatrix}
n \\ i
\end{bmatrix}x^i
\]
有符号第一类斯特林数对应递减阶乘展开式的各项系数：
\[
x^{(n)}=\prod_{i=0}^{n-1}(x+i)=\sum_{i=0}^{n}s(n,i)x^i
\]
性质
显然：\(\begin{bmatrix} 0 \\ 0 \end{bmatrix}=\begin{bmatrix} n \\ n \end{bmatrix}=1,\begin{bmatrix}n \\ 0\end{bmatrix}=\begin{bmatrix}0 \\ n\end{bmatrix}=0,n>0\)
还有一些其它的恒等式：
这就类似于一个环的排列。
$
\begin{bmatrix}
n \ n-1
\end{bmatrix}=C(n,2)
$
$
\begin{bmatrix}
n \ n-2
\end{bmatrix}=2C(n,3)+3C(n,4)
$
第一个简单，第二个等式相当于分类考虑，把两种情况加起来即可。
原文：https://www.cnblogs.com/heyuhhh/p/11992463.html