组合数学-递归与母函数（下）

Apr 17, 2020 · 组合数学  ·
分享到:

递归与母函数（下）

递推关系是计数的一个强有力的工具，特别是在做算法分析时是必需的。递推关系的求解主要是利用母函数。当然母函数尚有其他用处，但这主要是介绍解递推关系上的应用。

通常序列\(a_0,a_1,\dotsb,a_n,\dotsb\)与某个问题序列\(P_0,P_1,\dotsb,P_n,\dotsb\)的计数问题相对应，若已知序列的母函数，则可确定该序列，从而可以解决相应的计数问题。

注意：母函数==生成函数

线性常系数递推关系

定义：设k是给定的正整数，如果序列\(\{a_n\}\)满足 \[a_n+c_1 a_{n-1}+c_2 a_{n-2}+\dotsb+c_k a_{n-k}=f(n)\tag{7.1}\\ n>k,c_k\neq0\] 其中\(c_1,c_2,\dotsb,c_k\)是常数，则该方程成为序列\(\{a_n\}\)的k阶常系数线性递推关系。若\(f(n)=0\)，则线性递推关系成为齐次的。

定义：方程 \[x^k+c_1 x^{k-1}+c_2 x^{k -2}+\dotsb+c_{k-1}x+c_k=0\tag{7.2}\] 称为递推关系的特征方程，其根称为递推关系的特征根。

k阶常系数线性齐次递推关系

齐次：没有常数项，表达式： \[a_n+c_1 a_{n-1}+c_2 a_{n-2}+\dotsb+c_k a_{n-k}=0\tag{7.3}\]

引理1：r设为非零数，则\(a_n=r^n\)是齐次递推关系的一个解当且仅当r是递推关系的特征根。

证明：必要性。若\(a_n=r^n\)是递推关系的一个解，那么有 \[\begin{aligned} r^n+c_1*r^{n-1}+\dotsb+c_k r^{n-k}&=0\\ r^{n-k}(r^k+c_1 r^{k-1}+\dotsb+c_k)&=0\\ r^k+c_1 r^{k-1}+\dotsb+c_k&=0\\ \Rightarrow r是特征根 \end{aligned}\]

充分性：若r是递推关系的特征根。那么有 \[r^k+c_1 r^{k-1}+\dotsb+c_k=0\] 在方程的两端同乘以\(r^{n-k}\)，便得 \[r^n+c_1*r^{n-1}+\dotsb+c_k r^{n-k}=0\]

引理2：线性。\(A_1,A_2\)是任意常数，若\(\{a_n\},\{b_n\}\)都是齐次递推关系的解，那么\(\{A_1 a_n+A_2 b_n\}\)也是齐次递推关系的解。

推论： >设\(\{a_n^1\},\{a_n^2\},\dotsb,\{a_n^t\}\)是齐次递推关系的t个不同的解，若对齐次递推关系的每一个解，都存在常数\(A_1',A_2',\dotsb,A_t'\)，使得 >\[a_n=A_1'a_n^1+A_2'a_n^2+\dotsb+A_t'a_n^t\] >成立，则称\(A_1'a_n^1+A_2'a_n^2+\dotsb+A_t'a_n^t\)为齐次递推关系的通解，其中\(A_1',A_2',\dotsb,A_t'\)为任意常数。

非常类似于微分方程的解。

定理7.1：设\(r_1,r_2,\dotsb,r_k\)是齐次递推关系的\(k\)个不同的特征根，那么 \[a_n=A_1 r_1^n+A_2 r_2^n+\dotsb+A_k r_k^n\tag{7.4}\] 是齐次递推关系的通解。此定理只有在k阶特征方程解出k个不同根才有效。

证明：设\(\{h_n\}\)是齐次递推关系的任意一个解，那么\(\{h_n\}\)由k个初值\(h_0=d_0,h_1=d_1,\dotsb,h_{k-1}=d_{k-1},\)唯一确定。于是有 \[\begin{cases} h_0=A_1+A_2+\dotsb+A_k=d_0\\ h_1=A_1 r_1+A_2 r_2+\dotsb+A_k r_k=d_1\\ \dotsb\\ h_{k-1}=A_1 r_1^{k-1}+A_2 r_2^{k-1}+\dotsb+A_k r_k^{k-1}=d_{k-1}\\ \end{cases}\] 此一次方程组的系数行列式为范德蒙矩阵行列 \[\begin{vmatrix} 1&1&\dotsb&1\\ r_1&r_2&\dotsb&r_k\\ \dotsb&\dotsb&\dotsb&\dotsb\\ r_1^{k-1}&r_2^{k-1}&\dotsb&r_k^{k-1}\\ \end{vmatrix}=\prod_{1\le j<i \le k}(r_i-r_j) \neq 0\] 因此k个自由度需要k个一次线性不相关方程来唯一确定。

例题：求解递归关系 \[\begin{cases} a_n-9a_{n-1}+26a_{n-2}-24a_{n-3}=0, &n \ge 3\\ \tag{7.5} a_0=6,a_1=17,a_2=53 \end{cases}\]

解：特征方程为 \[x^3-9x^2+26x-24=0\] 解方程得： \[x_1=2,x_2=3,x_3=4\] 故通解为： \[a_n=A_1 2^n+A_2 3^n+A_3 4^n\] 根据初始条件联立方程组： \[\begin{cases} A_1+A_2+A_3=6\\ A_1*2+A_2*3+A_3*4=17\\ A_1*4+A_2*9+A_3*16=53\\ \end{cases}\] 得\(A_1=3,A_2=1,A_3=2\)，因此 \[a_n=3*2^n+3^n+2*4^n\]

如果用原来的凑单法会相当麻烦：

凑单法解题1 凑单法解题2 \[A(x)=\frac{3}{1-2x}+\frac{1}{1-3x}+\frac{2}{1-4x}\\ a_n=3*2^n+3^n+2*4^n,n \ge 0 \]

例题：求解递归关系 \[\begin{cases} a_n-4a_{n-1}+4a_{n-2}=0, &n \ge 2\\ \tag{7.6} a_0=1,a_1=3\\ \end{cases}\] 其特征方程为\(x^2-4x+4=0 \Rightarrow x_1=x_2=2\)，此时有 \[a_n=A_1 2^n+A_2 2^n=(A_1+A_2)2^n\] 为了满足初始条件\(a_0=1,a_1=3\)，有 \[\begin{cases} A_1+A_2=1\\ 2A_1+2A_2=3\\ \end{cases}\] 但这是不可能的。引出有重根的情形。

定理7.2：设\(r_1,r_2,\dotsb,r_s\)是k阶齐次递推关系的\(s(s<k)\)个不同的特征根,其重数分别为\(h_1,h_2,\dotsb,h_s\)，且\(h_1+h_2+\dotsb+h_s=k\)那么齐次递推关系的通解是 \[a_n=\alpha_n^1+\alpha_n^2+\dotsb+\alpha_n^s.\tag{7.7}\] 其中，\(\alpha_n^i=(b_0^i+b_1^in+b_2^i n^2+\dotsb+b_{h_i}^i n^{h_i-1})r_i^n,i=1,2,\dotsb,s\)。

证明略。

很显然，没有重根的是这个定理7.2公式的特殊情况。

重回上个例题： \[a_n=(A+Bn)2^n\\ \begin{cases} A=1\\ 2(A+B)=3\\ \end{cases}\\ \Rightarrow A=1,B=0.5\\ \Rightarrow a_n=(1+0.5n)*2^n\]

例题：求解递推关系 \[\begin{cases} a_n=-a_{n-1}+3a_{n-2}+5a_{n-3}+2a_{n-4},n \ge 4\\ \tag{7.8} a_0=1,a_1=0,a_2=1,a_3=2\\ \end{cases}\] 解：其特征方程为 \[x^4+x^3-3x^2-5x-2=0\] 其特征根为：\(x_1=x_2=x_3=-1,x_4=2\) 其通解为： \[a_n=(t_1+t_2 n +t_3 n^2)(-1)^n+t_4 2^n\] 联立方程组： \[\begin{cases} t_1+t_4=1\\ (t_1+t_2+t_3)*(-1)+t_4*2=0\\ (t_1+t_2*2+t_3*4)+t_4*4=1\\ (t_1+t_2*3+t_3*9)*(-1)+t_4*8=2\\ \end{cases}\\ \Rightarrow t_1=7/9,t_2=-1/3,t_3=0,t_4=2/9\] 由此可得： \[a_n=(7/9-1/3*n)(-1)^n+2/9*2^n,n \ge 0\]

常系数线性非齐次递推关系

非齐次：必有常数项，表达式： \[a_n+c_1 a_{n-1}+c_2 a_{n-2}+\dotsb+c_k a_{n-k}=f(n) \neq 0 \tag{7.9}\]

定理7.3：k阶常系数线性非齐次递推关系\((7.9)\)的通解是该递推关系的一个特解加上其相应的齐次递推关系的通解。

这个关系非常类似非齐次微分方程中特解和通解的关系的情况。

证明：设\(a_n',a_n^\ast\)分别为式\((7.9)\)的特解和式\((7.3)\)的通解。则 \[a_n'+c_1 a_{n-1}'+c_2 a_{n-2}'+\dotsb+c_k a_{n-k}'=f(n)\\ a_n^\ast+c_1 a_{n-1}^\ast+c_2 a_{n-2}^\ast+\dotsb+c_k a_{n-k}^\ast=0\] 因此有 \[(a_n'+a_n^\ast)+c_1(a_{n-1}'+a_{n-1}^\ast)+c_2(a_{n-2}'+a_{n-2}^\ast)+\dotsb\\ +c_k(a_{n-k}'+a_{n-k}^\ast)=f(n)\] 若\(a_n\)为式\(7.9\)的任意一个解，易知\(a_n-a_n'=a_n^\ast\)是式(7.3)的通解，所以 \[a_n=a_n'+a_n^\ast\tag{7.10}\]

不难看出，一般递推的关系的特解比较难求，而通解可以通过定理7.2求得。而且非齐次递推关系的特解通常是没有普遍的解法的。只有在某些简单的情况下可用待定系数法求出\(a_n'\)。 >定理7.4：特解形式。若线性非齐次递推关系 >\[a_n+c_1 a_{n-1}+c_2 a_{n-2}+\dotsb+c_k a_{n-k}=f(n),c_k \neq 0\\ f(n)=(b_t n^t+b_{t-1} n^{t-1}+\dotsb+b_1 n+b_0)s^n\] >的非齐次项\(f(n)\)满足特定条件，则递推关系的特解可以有以下特定形式： > >1. 当\(f(n)\)中无\(s^n\)指数项时，对应的特解形式为\(a_n'=P_t n^t+P_{t-1} n^{t-1}+\dotsb+P_1 n+P_0\)，其中\(P_0,P_1,\dotsb,P_t\)为待定系数。 >2. 当\(f(n)中，s\)不是对应的齐次递推关系的特征根，则对应的特解是\((P_t n^t+P_{t-1} n^{t-1}+\dotsb+P_1 n+P_0)s^n\)，其中\(P_0,P_1,\dotsb,P_t\)为待定系数。 >3. 当\(f(n)中，s\)是特征方程的\(m\)重特征根，则对应的特解是\(n^m(P_t n^t+P_{t-1} n^{t-1}+\dotsb+P_1 n+P_0)s^n\)，其中\(P_0,P_1,\dotsb,P_t\)为待定系数。

例题求解递推关系 \[\begin{cases} a_n-a_{n-1}-6a_{n-2}=5\cdot4^n\\ \tag{7.11} a_0=5,a_1=3 \end{cases}\] 解：其特征方程为 \[x^2-x-6=(x-3)(x+2)=0\] 其特征根为\(x=3,-2\)，通解形式为：\(A3^n+B(-2)^n\)。

\(f(n)=5\cdot 4^n\)，其中4不是特征方程的根。特解形式为\(P_0\cdot 4^n\)，带入递推关系得： \[P_0 4^n-P_0 4^{n-1}-6P_0 4^{n-2}=5\cdot 4^n\\ \Rightarrow P_0=\frac{40}{3}\] 该递推关系的通解为： \[a_n=A3^n+B(-2)^n+\frac{40}{3}4^n\] 带入初始条件得 \[a_n=\frac{-67}{5}3^n+\frac{76}{15}(-2)^n+\frac{40}{3}4^n\]

非线性递推关系举例

多项式系数

引子：在下列展开式 \[(x_1+x_2+x_3)^3=x_1^3+x_2^3+x_3^3+3x_1^2x_2+3x_1^2x_3\\ +3x_1x_2^3+3x_1x_3^2+3x_2^2x_3+3x_2x_3^2+6x_1x_2x_3\] 中，每项都是\(x_1^{n_1}x_2^{n_2}x_3^{n_3}\)的形式，其中\(n_1,n_2,n_3\)都是非负整数，且\(n_1+n_2+n_3=3\)。项\(x_1^{n_1}x_2^{n_2}x_3^{n_3}\)得系数为 \[\frac{3!}{n_1!n_2!n_3!}\] 等同于在求范围内的排列数。

定理8.1 设n为正整数，则 \[(x_1+x_2+\dotsb+x_m)^n\\ =\sum_{n_1+n_2+\dotsb+n_m=n}C(n, n_1,n_2,\dotsb,n_m)x_1^{n_1}x_2^{n_2}\dotsb x_m^{n_m}\] 其中\(n_1,n_2,\dotsb,n_m\)为非负整数。

证明：系数为多重集\(x_i^{n_i}\)的全排列。 \[C(n,n_1)C(n-n_1,n_2)\dotsb C(n-n_1-\dotsb-n_{m-1},n_m)\\ \begin{aligned} &=\frac{n!}{(n-n_1)!n_1!}\frac{(n-n_1)!}{(n-n_1-n_2)!n_2!}\dotsb\frac{(n-n_1-\dotsb-n_{m-1})!}{(n-n_1-\dotsb-n_m)!n_m!}\\ &=\frac{n!}{n_1!n_2!\dotsb n_m!(n-n_1-\dotsb-n_m)!}\\ &\because n=n_1+n_2+\dotsb+n_m\\ &\therefore 原式=\frac{n!}{n_1!n_2!\dotsb n_m!} \end{aligned} \]

例题求展开\((x_1+x_2+\dotsb+x_5)^7\)，则\(x_1^2x_3x_4^3x_5\)的系数。 \[\frac{(2+1+3+1)!}{2!1!3!1!}=420\]

例题展开\((2x_1-3x_2+5x_3)^6\)，则\(x_1^3x_2x_3^2\)的系数为 \[\frac{(3+1+2)!}{3!1!2!}\cdot 2^3\cdot(-3)\cdot5^2=-36000\]

定理8.2 展开式\((x_1+x_2+\dotsb+x_m)^n\)的项数等于\(C(n+m-1,n)\)，而且这些项的系数之和等于\(m^n\)。

证明：展开式的项\(x_1^{n_1}x_2^{n_2}\dotsb x_m^{n_m},(n_1+n_2+\dotsb+n_m=n)\) 与从m个元素中取n个允许重复的组合一一对应，故其项数为\(C(n+m-1,n)\)。当令\(x_1=x_2=\dotsb=x_m=1\)时，系数和为\((1+1+\dotsb+1)^n=m^n\)

例题多项式\((x_1+x_2+x_3)^3\)的展开式中恰有 \[C(n+m-1,n)=C(3+3-1,3)=C(5,3)=10\] 项。

Stirling数

有两类Stirling数，称之为第一类Stirling数和第二类Stirling数

定义： \[[x_n]=x(x-1)\dotsb(x-n+1)\\ =s(n,n)x^n-s(n,n-1)x^{n-1}+\dotsb+(-1)^{n-1}s(n,1)x+(-1)^n s(n,0)\] 称\(s(n,0),s(n,1),\dotsb,s(n,n)\)为第一类Stirling数。

定义可知：\(s(n,0)=0 \quad s(n,n)=1\)。

定义：n个有区别的球放到m个相同的盒子中，要求无一空盒，其不同的方案数用\(S(n,m)\)表示，称为第二类Stirling数。

Catalan数

定义：数 \[C_n=\frac{1}{n+1}C(2n,n),n=0,1,2,\dotsb\] 为第n个Catalan数。

n 0 1 2 3 4 5 6 7 8 9 10
\(C_n\) 1 1 2 5 14 42 132 429 1430 4862 16796