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

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

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

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

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

定义：设k是给定的正整数，如果序列{an}\{a_n\}满足 an+c1an−1+c2an−2+⋯+ckan−k=f(n)n>k,ck≠0(7.1)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 其中c1,c2,⋯ ,ckc_1,c_2,\dotsb,c_k是常数，则该方程成为序列{an}\{a_n\}的k阶常系数线性递推关系。若f(n)=0f(n)=0，则线性递推关系成为齐次的。

定义：方程 xk+c1xk−1+c2xk−2+⋯+ck−1x+ck=0(7.2)x^k+c_1 x^{k-1}+c_2 x^{k -2}+\dotsb+c_{k-1}x+c_k=0\tag{7.2} 称为递推关系的特征方程，其根称为递推关系的特征根。

齐次：没有常数项，表达式： an+c1an−1+c2an−2+⋯+ckan−k=0(7.3)a_n+c_1 a_{n-1}+c_2 a_{n-2}+\dotsb+c_k a_{n-k}=0\tag{7.3}

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

证明：必要性。若an=rna_n=r^n是递推关系的一个解，那么有 rn+c1∗rn−1+⋯+ckrn−k=0rn−k(rk+c1rk−1+⋯+ck)=0rk+c1rk−1+⋯+ck=0⇒r是特征根\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是递推关系的特征根。那么有 rk+c1rk−1+⋯+ck=0r^k+c_1 r^{k-1}+\dotsb+c_k=0 在方程的两端同乘以rn−kr^{n-k}，便得 rn+c1∗rn−1+⋯+ckrn−k=0r^n+c_1*r^{n-1}+\dotsb+c_k r^{n-k}=0

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

推论： >设{an1},{an2},⋯ ,{ant}\{a_n^1\},\{a_n^2\},\dotsb,\{a_n^t\}是齐次递推关系的t个不同的解，若对齐次递推关系的每一个解，都存在常数A1′,A2′,⋯ ,At′A_1',A_2',\dotsb,A_t'，使得 >an=A1′an1+A2′an2+⋯+At′anta_n=A_1'a_n^1+A_2'a_n^2+\dotsb+A_t'a_n^t >成立，则称A1′an1+A2′an2+⋯+At′antA_1'a_n^1+A_2'a_n^2+\dotsb+A_t'a_n^t为齐次递推关系的通解，其中A1′,A2′,⋯ ,At′A_1',A_2',\dotsb,A_t'为任意常数。

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

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

证明：设{hn}\{h_n\}是齐次递推关系的任意一个解，那么{hn}\{h_n\}由k个初值h0=d0,h1=d1,⋯ ,hk−1=dk−1,h_0=d_0,h_1=d_1,\dotsb,h_{k-1}=d_{k-1},唯一确定。于是有 {h0=A1+A2+⋯+Ak=d0h1=A1r1+A2r2+⋯+Akrk=d1⋯hk−1=A1r1k−1+A2r2k−1+⋯+Akrkk−1=dk−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} 此一次方程组的系数行列式为范德蒙矩阵行列 ∣11⋯1r1r2⋯rk⋯⋯⋯⋯r1k−1r2k−1⋯rkk−1∣=∏1≤j<i≤k(ri−rj)≠0\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个一次线性不相关方程来唯一确定。

例题：求解递归关系 {an−9an−1+26an−2−24an−3=0,n≥3a0=6,a1=17,a2=53(7.5)\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}

解：特征方程为 x3−9x2+26x−24=0x^3-9x^2+26x-24=0 解方程得： x1=2,x2=3,x3=4x_1=2,x_2=3,x_3=4 故通解为： an=A12n+A23n+A34na_n=A_1 2^n+A_2 3^n+A_3 4^n 根据初始条件联立方程组： {A1+A2+A3=6A1∗2+A2∗3+A3∗4=17A1∗4+A2∗9+A3∗16=53\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} 得A1=3,A2=1,A3=2A_1=3,A_2=1,A_3=2，因此 an=3∗2n+3n+2∗4na_n=3*2^n+3^n+2*4^n

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

凑单法解题1

Figure 1: 凑单法解题1

凑单法解题2

Figure 2: 凑单法解题2

A(x)=31−2x+11−3x+21−4xan=3∗2n+3n+2∗4n,n≥0A(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

例题：求解递归关系 {an−4an−1+4an−2=0,n≥2a0=1,a1=3(7.6)\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} 其特征方程为x2−4x+4=0⇒x1=x2=2x^2-4x+4=0 \Rightarrow x_1=x_2=2，此时有 an=A12n+A22n=(A1+A2)2na_n=A_1 2^n+A_2 2^n=(A_1+A_2)2^n 为了满足初始条件a0=1,a1=3a_0=1,a_1=3，有 {A1+A2=12A1+2A2=3\begin{cases} A_1+A_2=1\\ 2A_1+2A_2=3\\ \end{cases} 但这是不可能的。引出有重根的情形。

定理7.2：设r1,r2,⋯ ,rsr_1,r_2,\dotsb,r_s是k阶齐次递推关系的s(s<k)s(s<k)个不同的特征根,其重数分别为h1,h2,⋯ ,hsh_1,h_2,\dotsb,h_s，且h1+h2+⋯+hs=kh_1+h_2+\dotsb+h_s=k那么齐次递推关系的通解是 an=αn1+αn2+⋯+αns.(7.7)a_n=\alpha_n^1+\alpha_n^2+\dotsb+\alpha_n^s.\tag{7.7} 其中，αni=(b0i+b1in+b2in2+⋯+bhiinhi−1)rin,i=1,2,⋯ ,s\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公式的特殊情况。

重回上个例题： an=(A+Bn)2n{A=12(A+B)=3⇒A=1,B=0.5⇒an=(1+0.5n)∗2na_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

例题：求解递推关系 {an=−an−1+3an−2+5an−3+2an−4,n≥4a0=1,a1=0,a2=1,a3=2(7.8)\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} 解：其特征方程为 x4+x3−3x2−5x−2=0x^4+x^3-3x^2-5x-2=0 其特征根为：x1=x2=x3=−1,x4=2x_1=x_2=x_3=-1,x_4=2 其通解为： an=(t1+t2n+t3n2)(−1)n+t42na_n=(t_1+t_2 n +t_3 n^2)(-1)^n+t_4 2^n 联立方程组： {t1+t4=1(t1+t2+t3)∗(−1)+t4∗2=0(t1+t2∗2+t3∗4)+t4∗4=1(t1+t2∗3+t3∗9)∗(−1)+t4∗8=2⇒t1=7/9,t2=−1/3,t3=0,t4=2/9\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 由此可得： an=(7/9−1/3∗n)(−1)n+2/9∗2n,n≥0a_n=(7/9-1/3*n)(-1)^n+2/9*2^n,n \ge 0

非齐次：必有常数项，表达式： an+c1an−1+c2an−2+⋯+ckan−k=f(n)≠0(7.9)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)(7.9)的通解是该递推关系的一个特解加上其相应的齐次递推关系的通解。

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

证明：设an′,an∗a_n',a_n^\ast分别为式(7.9)(7.9)的特解和式(7.3)(7.3)的通解。则 an′+c1an−1′+c2an−2′+⋯+ckan−k′=f(n)an∗+c1an−1∗+c2an−2∗+⋯+ckan−k∗=0a_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 因此有 (an′+an∗)+c1(an−1′+an−1∗)+c2(an−2′+an−2∗)+⋯+ck(an−k′+an−k∗)=f(n)(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) 若ana_n为式7.97.9的任意一个解，易知an−an′=an∗a_n-a_n'=a_n^\ast是式(7.3)的通解，所以 an=an′+an∗(7.10)a_n=a_n'+a_n^\ast\tag{7.10}

不难看出，一般递推的关系的特解比较难求，而通解可以通过定理7.2求得。而且非齐次递推关系的特解通常是没有普遍的解法的。只有在某些简单的情况下可用待定系数法求出an′a_n'。 >定理7.4：特解形式。若线性非齐次递推关系 >an+c1an−1+c2an−2+⋯+ckan−k=f(n),ck≠0f(n)=(btnt+bt−1nt−1+⋯+b1n+b0)sna_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)f(n)满足特定条件，则递推关系的特解可以有以下特定形式： > >1. 当f(n)f(n)中无sns^n指数项时，对应的特解形式为an′=Ptnt+Pt−1nt−1+⋯+P1n+P0a_n'=P_t n^t+P_{t-1} n^{t-1}+\dotsb+P_1 n+P_0，其中P0,P1,⋯ ,PtP_0,P_1,\dotsb,P_t为待定系数。 >2. 当f(n)中，sf(n)中，s不是对应的齐次递推关系的特征根，则对应的特解是(Ptnt+Pt−1nt−1+⋯+P1n+P0)sn(P_t n^t+P_{t-1} n^{t-1}+\dotsb+P_1 n+P_0)s^n，其中P0,P1,⋯ ,PtP_0,P_1,\dotsb,P_t为待定系数。 >3. 当f(n)中，sf(n)中，s是特征方程的mm重特征根，则对应的特解是nm(Ptnt+Pt−1nt−1+⋯+P1n+P0)snn^m(P_t n^t+P_{t-1} n^{t-1}+\dotsb+P_1 n+P_0)s^n，其中P0,P1,⋯ ,PtP_0,P_1,\dotsb,P_t为待定系数。

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

f(n)=5⋅4nf(n)=5\cdot 4^n，其中4不是特征方程的根。特解形式为P0⋅4nP_0\cdot 4^n，带入递推关系得： P04n−P04n−1−6P04n−2=5⋅4n⇒P0=403P_0 4^n-P_0 4^{n-1}-6P_0 4^{n-2}=5\cdot 4^n\\ \Rightarrow P_0=\frac{40}{3} 该递推关系的通解为： an=A3n+B(−2)n+4034na_n=A3^n+B(-2)^n+\frac{40}{3}4^n 带入初始条件得 an=−6753n+7615(−2)n+4034na_n=\frac{-67}{5}3^n+\frac{76}{15}(-2)^n+\frac{40}{3}4^n

引子：在下列展开式 (x1+x2+x3)3=x13+x23+x33+3x12x2+3x12x3+3x1x23+3x1x32+3x22x3+3x2x32+6x1x2x3(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 中，每项都是x1n1x2n2x3n3x_1^{n_1}x_2^{n_2}x_3^{n_3}的形式，其中n1,n2,n3n_1,n_2,n_3都是非负整数，且n1+n2+n3=3n_1+n_2+n_3=3。项x1n1x2n2x3n3x_1^{n_1}x_2^{n_2}x_3^{n_3}得系数为 3!n1!n2!n3!\frac{3!}{n_1!n_2!n_3!} 等同于在求范围内的排列数。

定理8.1 设n为正整数，则 (x1+x2+⋯+xm)n=∑n1+n2+⋯+nm=nC(n,n1,n2,⋯ ,nm)x1n1x2n2⋯xmnm(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} 其中n1,n2,⋯ ,nmn_1,n_2,\dotsb,n_m为非负整数。

证明：系数为多重集xinix_i^{n_i}的全排列。 C(n,n1)C(n−n1,n2)⋯C(n−n1−⋯−nm−1,nm)=n!(n−n1)!n1!(n−n1)!(n−n1−n2)!n2!⋯(n−n1−⋯−nm−1)!(n−n1−⋯−nm)!nm!=n!n1!n2!⋯nm!(n−n1−⋯−nm)!∵n=n1+n2+⋯+nm∴原式=n!n1!n2!⋯nm!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}

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

例题展开(2x1−3x2+5x3)6(2x_1-3x_2+5x_3)^6，则x13x2x32x_1^3x_2x_3^2的系数为 (3+1+2)!3!1!2!⋅23⋅(−3)⋅52=−36000\frac{(3+1+2)!}{3!1!2!}\cdot 2^3\cdot(-3)\cdot5^2=-36000

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

证明：展开式的项x1n1x2n2⋯xmnm,(n1+n2+⋯+nm=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)C(n+m-1,n)。当令x1=x2=⋯=xm=1x_1=x_2=\dotsb=x_m=1时，系数和为(1+1+⋯+1)n=mn(1+1+\dotsb+1)^n=m^n

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

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

定义： [xn]=x(x−1)⋯(x−n+1)=s(n,n)xn−s(n,n−1)xn−1+⋯+(−1)n−1s(n,1)x+(−1)ns(n,0)[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),⋯ ,s(n,n)s(n,0),s(n,1),\dotsb,s(n,n)为第一类Stirling数。

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

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

定义：数 Cn=1n+1C(2n,n),n=0,1,2,⋯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
CnC_n 1 1 2 5 14 42 132 429 1430 4862 16796