我们今天学习组合数学的最后一个章节，递推方程和生成函数.
这一章节应该算是整本书最长的章节了
11.1 递推方程的定义及实例
递推方程的定义(注意不能是刷表法)
汉诺塔算法:相关代码以及\(T(n)=2T(n-1)+1.\)
斐波那契数列:\(f_n=\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^{n+1}-\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^{n+1}.\)
相关应用:蜜蜂家族构成问题，二进制串无连续0计数问题.
11.2 递推方程的公式解法
\(k\)阶常系数线性递推方程，齐次方程，定义类似高数中的初值问题.
设给定常系数线性齐次递推方程如下:
则方程\(x^k-a_1x^{k-1}-\ldots -a_k=0\)称为其特征方程，特征方程的根称为特征根.
若\(q\)是非零复数，则\(q^n\)是递推方程的解当且仅当\(q\)为其特征根.
于是有\(c_1q_1^n+\ldots+c_kq_k^n\)为该递推方程的解.
若\(q_1,q_2\ldots,q_n\)彼此不等，则上述解为递推方程的通解.
若\(q_i\)的重数为\(m_i\),则对应的项改为\((c_{i1}+c_{i2}n+\ldots+c_{im_i}n^{m_i-1})q_i^n\).
对于非齐次的递推方程而言，则需要在通解基础上加上一个特解.
若\(f(n)\)为\(n\)的\(t\)次多项式，则特解一般也为\(n\)的\(t\)次多项式，若递推方程的特征根为\(1\)，则需要提高特解的多项式次数.
若\(f(n)\)为指数函数\(A\beta^n\)，若\(\beta\)不是特征根,则特解为\(P\beta^n\);若是\(m\)重特征根，则特解为\(Pn^m\beta^n.\)
注意:特解需要先代入回原方程进行求解再通过初值进行通解的求解.
例:顺序插入排序算法的\(W(n)=\frac{n(n-1)}{2}.\)
11.3 递推方程的其它解法
换元法:将原来关于某个变元的递推方程通过函数变换转变为关于其他变元的常系数递推方程
迭代归纳法:从原始递推方程开始，利用方程所表达的数列中后项对前项的依赖关系，把表达式中的后项用相等的前项中的表达式代入，直到表达式中没有函数式中为止.
差消法:用于将二阶以上的递推方程化简为一阶递推方程，再进行迭代.
递归树:用于说明迭代思想，带权二叉树，每个节点用\(W(n)=2W(n/2)+n-1\)中的\(n-1\)代替，再向下迭代，直至树叶的权为\(1.\)使用分层计算算出权.
二分归并排序算法:将被排序的数组划分为相等的两个子数组，然后递归使用同样的算法分别对两个子数组排序，最后将两个排好序的子数组归并成一个数组.
代码如下:
其\(W(n)=n\mathrm{log}n-n+1\)
快速排序:请看以下代码，通过划分来实现.
其\(T(n)=O(n\mathrm{log}n)\)
对于\(T(n),\)其依赖于\(T(1),T(2),\ldots,T(n-1)\)等所有的项，称作全部历史递推方程.
分治算法的迭代求解.
在求解斐波那契数列通项时，我们有
从而提高计算的时间复杂度.
11.4 生成函数及其应用
牛顿二项式系数:
于是有牛顿二项式定理:\((x+y)^{\alpha}=\sum\limits_{n=0}^{+\infty}\dbinom{\alpha}{n}x^ny^{\alpha-n},\alpha,x,y \in R,|x/y|<1.\)
可以导出以下公式:
(1) \(\frac{1}{1-x}=1+x+x^2+\ldots,\)
(2) \(\frac{1}{(1-x)^2}=\sum\limits_{n=0}^{+\infty}(n+1)x^n.\)
(3) \((1+x)^{\frac{1}{2}}=1+\sum\limits_{n=0}^{+\infty}\frac{(-1)^{n-1}}{2^{2n-1}n}\dbinom{2n-2}{n-1}x^n.\)
给定序列\(\{a_n\},\)构造函数\(G(x)=a_0+a_1x+a_2x^2+\ldots +a_nx^n.\)称为其生成函数.
例如,\(\{\dbinom{m}{n}\}\)的生成函数为\((1+x)^m.\)
注意:如果序列是分段的，但它的生成函数不一定分段.
用生成函数求解关于\(\{a_n\}\)的递推方程的步骤：
(1) 先设定\(\{a_n\}\)的生成函数\(G(x).\)
(2) 利用递推方程的依赖关系导出关于生成函数\(G(x)\)的方程.
(3) 通过求解方程得到\(G(x)\)的函数表达式.
(4) 将\(G(x)\)展开为幂级数，其中\(x^n\)项的系数就是\(a_n.\)
生成函数的相关应用:
设\(S=\{n_1 \cdot a_1,n_2 \cdot a_2,\ldots,n_k \cdot a_k\}\)为多重集，\(S\)的一个\(r\)组合就是一个子多重集\(\{x_1 \cdot a_1,x_2 \cdot a_2,\ldots,x_k \cdot a_k\},\)于是得到不定方程\(x_1+x_2+\ldots +x_k=r.\)
考虑函数\(G(y)=(1+y+\ldots +y^{n_1})(1+y+\ldots +y^{n_2})\ldots(1+y+\ldots +y^{n_k})\)考虑\(y^r\)的系数，就是不定方程的解的个数.
进一步，考虑对变量取值存在限制的不定方程，\(x_1+x_2+\ldots +x_k=r,l_i \le x_i \le t_i,\)考虑\(G(y)=(y^{l_1}+y^{l_1+1}+\ldots +y^{t_1})\ldots (y^{l_k}+y^{l_k+1}+\ldots +y^{t_k}),\)其\(y^r\)的系数为不定方程的解个数.
进一步，考虑变量系数不为\(1\)的不定方程\(p_1x_1+p_2x_2+\ldots +p_kx_k=r\)，对应的生成函数为\(G(y)=(1+y^{p_1}+y^{2p_1}+\ldots)\ldots(1+y^{p_k}+y^{2p_k}+\ldots)\)
进一步，我们可以得出对变量取值存在限制，同时系数不全为\(1\)的情况.
相关实例:坐标平面的整点个数，正整数拆分(是否有序，是否允许重复)
我们首先考虑无序拆分，有等式\(a_1x_1+\ldots +a_nx_n=N.\)若不允许重复，\(G(y)=(1+y^{a_1})\ldots(1+y^{a_n}).\)
若允许重复，有\(G(y)=(1+y^{a_1}+y^{2a_1}\ldots)\ldots(1+y^{a_n}+y^{2a_n}+\ldots)\)
例11.4.7 给定\(r,\)求将正整数\(N\)无序并允许重复地拆分成\(k\)个部分的方法数,\(k \le r.\)
我们得到一个费勒斯图，然后将其沿\(y=x\)对称，得到新的费勒斯图，即转化为将\(N\)无序并可重复地拆分成不超过\(r\)的数的方案数.
例11.4.8设将\(n\)无序拆分为恰好\(r\)个部分的方案有\(p_r(n)\)种，证明\(p_r(n) \sim \frac{n^{r-1}}{r!(r-1)!}.\)
这道题的证明要好好看.
接着我们考虑有序拆分，有以下定理.
设\(N\)为正整数，将\(N\)允许重复地有序拆分成\(r\)个部分的方案数为\(C_{N-1}^{r-1}.\)
得到其推论:对\(N\)做任意重复地有序拆分，方案数为\(2^{N-1}.\)
对于不允许重复的有序拆分问题，可以先将\(N\)不允许重复地进行无序拆分，再针对每种无序拆分方案，计数其全排列数.
11.5 指数生成函数及其应用
给定序列\(\{a_n\},\)记\(G_e(x)=\sum\limits_{n=0}^{+\infty}a_n\frac{x^n}{n!}\)为其指数生成函数.
于是可知\((1+x)^m\)既是\(\{C_{m}^n\}\)的生成函数，也是\(\{P_m^n\}\)的指数生成函数.
使用指数生成函数可以求解多重集的排列问题.
设\(S=\{n_1 \cdot a_1,n_2 \cdot a_2,\ldots,n_k \cdot a_k\}\)为多重集，则\(S\)的\(r\)排列数的指数生成函数为\(G_e(x)=f_{n_1}(x)f_{n_2}(x)\ldots f_{n_k}(x),f_{n_i}(x)=1+x+\frac{x^2}{2!}+\ldots +\frac{x^{n_i}}{n_i!}\)
例11.5.4 由\(A,B,C,D,E,F\)组成长度为\(n\)的序列，如果要求在排列中\(A\)与\(B\)出现的次数之和为偶数，问:这样的序列有多少个？
解:由于\(A\)和\(B\)出现的次数之和为偶数，则它们的次数同奇偶，即同时为\(\frac{e^x+e^{-x}}{2}\)或\(\frac{e^x-e^{-x}}{2},\)得到\(G_e(x)=(\frac{e^x+e^{-x}}{2})^2e^{4x}+(\frac{e^x-e^{-x}}{2})^2e^{4x}=\frac{1}{2}e^{6x}+\frac{1}{2}e^{2x}.\)于是得出\(a_n=\frac{6^n+2^n}{2}.\)
11.6 卡塔兰数与斯特林数
给定一个凸\(n+1\)边形，通过在内部不相交的对角线把它划分成三角形，不同的划分方案数称作卡塔兰(\(\mathrm{Catalan}\))数，记作\(h_n.\)
其递推方程为:
其通项公式为:\(h_n=\frac{1}{n}\dbinom{2n-2}{n-1}.\)
应用:矩阵链相乘、出栈进栈问题.
考虑\(x(x-1)(x-2)\ldots (x-n+1)\)的展开式\(S_nx^n-S_{n-1}x^{n-1}+S_{n-2}x^{n-2}\ldots +(-1)^{n-1}S_1x.\)
将\(x^r\)的系数的绝对值\(S_r\)记作\(\displaystyle\genfrac{[}{]}{0pt}{}{n}{r},\)称作第一类斯特林(\(\mathrm{Stirling}\)数).
则它满足下列递推方程与恒等式:
(1)
(2) \(\displaystyle\genfrac{[}{]}{0pt}{}{n}{n}\)=1
(3) \(\displaystyle\genfrac{[}{]}{0pt}{}{n}{n-1}=\dbinom{n}{2}=\frac{n(n-1)}{2}\)
(4) \(\sum\limits_{r=1}^{n}\displaystyle\genfrac{[}{]}{0pt}{}{n}{r}=n!.\)
第一类斯特林数通常与\(n\)个不同对象划分的计数相关，在这些划分中\(n\)个对象被分成\(r\)个环排列.
将\(n\)个不同的球恰好放到\(r\)个相同的盒子里的方法数称作第二类斯特林(Stirling)数，记作\(\displaystyle\genfrac{\{}{\}}{0pt}{}{n}{k}.\)
则它满足下列递推方程和恒等式:
(1)
(2) \(\displaystyle\genfrac{\{}{\}}{0pt}{}{n}{2}=2^{n-1}-1.\)
(3) \(\displaystyle\genfrac{\{}{\}}{0pt}{}{n}{n-1}=\dbinom{n}{2}.\)
(4) \(\displaystyle\genfrac{\{}{\}}{0pt}{}{n}{n}=1\)
(5) \(\sum\dbinom{n}{n_1n_2 \ldots n_m}=m!\displaystyle\genfrac{\{}{\}}{0pt}{}{n}{m},\)其中\(\sum\)是对\(n_1+n_2+\ldots +n_m=n\)的正整数解求和.
(6) \(\sum\limits_{k=1}^{m}\dbinom{m}{k}\displaystyle\genfrac{\{}{\}}{0pt}{}{m}{k}k!=m^n.\)
(7) \(\displaystyle\genfrac{\{}{\}}{0pt}{}{n+1}{r}=\sum\limits_{i=0}^{n}\dbinom{n}{i}\displaystyle\genfrac{\{}{\}}{0pt}{}{i}{r-1}.\)
(8) \(\sum\limits_{r=0}^{m}(-1)^rC_m^{r}(m-r)^n=m!\displaystyle\genfrac{\{}{\}}{0pt}{}{n}{m}\)
于是，我们得到一张总结表.
例11.6.2设\(A,B\)为集合，其中\(|A|=n,|B|=m,\)问:
(1) 从\(A\)到\(B\)的关系有多少个？
(2) \(A\)上关系有多少个？其中等价关系有多少个？
(3) 从\(A\)到\(B\)的函数有多少个？其中单射函数有多少个？满射函数有多少个？双射函数有多少个？
答案:(1) \(2^{mn}\)
(2) \(2^{n^2},\sum\limits_{k=1}^{n}\displaystyle\genfrac{\{}{\}}{0pt}{}{n}{k}\)
(3) \(m^n,P_m^n,m!\displaystyle\genfrac{\{}{\}}{0pt}{}{n}{m},n!\)
注意:第二问注意从划分的角度来看，第三问注意考虑已知的组合模型.
11.7 基本的计数模型
选取问题:
不重复选取：集合的排列组合公式
无序重复选取:\(A(y)=(1+y+\ldots +y^{n_1})(1+y+\ldots +y^{n_2})\ldots(1+y+\ldots +y^{n_k}).\)若\(r \le n_i,N=C_{r+k-1}^r\)
有序重复选取:指数生成函数为\(A_e(y)=(1+\frac{y}{1!}+\frac{y^2}{2!}+\ldots +\frac{y^{n_1}}{n_1!})\ldots(1+\frac{y}{1!}+\frac{y^2}{2!}+\ldots +\frac{y^{n_k}}{n_k!}).\)若\(r \le n_i,N=k^r.\)若\(r=n_1+n_2 +\ldots +n_k,r=\dbinom{n}{n_1n_2\ldots n_k}.\)
不定方程的整数解问题:
有限制、系数不为1的问题:生成函数
方程\(x_1+x_2+x_3+\ldots +x_k=r\)的非负整数解个数为\(C_{r+k-1}^r,\)正整数解的个数为\(C_{k-1}^{r-1}.\)
非降路径问题:
\((a,b)\)到\((m,n)\)的非降路径条数:\(\dbinom{m+n-a-b}{m-a}\)
其余的采用分步或者一一对应的方法.
正整数的拆分问题:
一般采用生成函数
若有限制的拆分，则转化为费勒斯图再一一对应.
放球问题:见上表
下学期，也请各位继续关注：
《System beats!》
《大二病也要学离散！》
《数算の旅》
《某信息学的概率统计》
还有——
《我的算法竞赛不可能这么可爱》
本期到此结束！
