《离散数学》指清华大学出版社《离散数学（第三版）》

本文主要整理自考试范围中书上的内容，添加了少许个人的理解，受限于个人水平，一些内容还没有完全搞清楚，敬请谅解；

同时也作为以后算法竞赛中参考的纸质资料，以解决相关问题；

如有疏漏，敬请评论区指正；

定义 10.2：关于k阶常系数线性齐次递推方程的定义

设递推方程满足 { H ( n ) − a 1 H ( n − 1 ) − a 2 H ( n − 2 ) − . . . − a k H ( n − k ) = f ( n ) H ( 0 ) = b 0 , H ( 1 ) = b 1 , H ( 2 ) = b 2 , . . . , H ( k − 1 ) = b k − 1 \begin{cases} H(n)-a_1H(n-1)-a_2H(n-2)-...-a_kH(n-k)=f(n)\\ H(0)=b_0,H(1)=b_1,H(2)=b_2,...,H(k-1)=b_{k-1} \end{cases} {H(n)−a1​H(n−1)−a2​H(n−2)−...−ak​H(n−k)=f(n)H(0)=b0​,H(1)=b1​,H(2)=b2​,...,H(k−1)=bk−1​​ 其中 a 1 , a 2 , . . . , a k a_1,a_2,...,a_k a1​,a2​,...,ak​ 为常数， a k ≠ 0 a_k\neq 0 ak​​=0 ，这个方程称为k阶常系数线性递推方程。 其中k阶为k项，常系数指系数为常数，线性为 H ( i ) H(i) H(i) 的次数为1； 当 f ( n ) = 0 f(n)=0 f(n)=0 时称这个方程为齐次方程。

定义 10.3：关于特征方程与特征根

给定常系数线性齐次递推方程如下 { H ( n ) − a 1 H ( n − 1 ) − a 2 H ( n − 2 ) − . . . − a k H ( n − k ) = 0 H ( 0 ) = b 0 , H ( 1 ) = b 1 , H ( 2 ) = b 2 , . . . , H ( k − 1 ) = b k − 1 ( 10.2 ) \begin{cases} H(n)-a_1H(n-1)-a_2H(n-2)-...-a_kH(n-k)=0&\\ H(0)=b_0,H(1)=b_1,H(2)=b_2,...,H(k-1)=b_{k-1} \end{cases}(10.2) {H(n)−a1​H(n−1)−a2​H(n−2)−...−ak​H(n−k)=0H(0)=b0​,H(1)=b1​,H(2)=b2​,...,H(k−1)=bk−1​​(10.2) 方程 x k − a 1 x k − 1 − . . . − a k = 0 x^k-a_1x^{k-1}-...-a_k=0 xk−a1​xk−1−...−ak​=0 称为该递推方程的特征方程，特征方程的根称为该方程的特征根。

定理 10.1：关于递推方程与特征根

设 q q q 是非零复数，则 q n q^n qn 是递推方程(10.2)的解（ H ( n ) = q n H(n)=q^n H(n)=qn）当且仅当 q q q 是它的特征根。

定理 10.2：关于递推方程与特征根

设 h 1 ( n ) h_1(n) h1​(n) 和 h 2 ( n ) h_2(n) h2​(n) 是递推方程(10.2)的解， c 1 , c 2 c_1,c_2 c1​,c2​ 为任意常数，则 c 1 h 1 ( n ) + c 2 h 2 ( n ) c_1h_1(n)+c_2h_2(n) c1​h1​(n)+c2​h2​(n) 也是这个递推方程的解。

定义 10.4：关于通解

若对于递推方程(10.2)的每个解 h ( n ) h(n) h(n)​ 都存在一组常数 c 1 ‘ , c 2 ‘ , . . . , c k ‘ c_1^`,c_2^`,...,c_k^` c1‘​,c2‘​,...,ck‘​

使得 h ( n ) = c 1 ‘ q 1 n + c 2 ‘ q 2 n + . . . + c k ‘ q k n h(n)=c_1^`q_1^n+c_2^`q_2^n+...+c_k^`q_k^n h(n)=c1‘​q1n​+c2‘​q2n​+...+ck‘​qkn​​ 成立，则称 c 1 q 1 n + c 2 q 2 n + . . . + c k q k n c_1q_1^n+c_2q_2^n+...+c_kq_k^n c1​q1n​+c2​q2n​+...+ck​qkn​​ 为该递推方程的通解；

定理 10.3：无重特征根与通解

设 q 1 , q 2 , . . . , q k q_1,q_2,...,q_k q1​,q2​,...,qk​ 是递推方程(10.2)不等的特征根，则 H ( n ) = c 1 q 1 n + c 2 q 2 n + . . . + c k q k n H(n)=c_1q_1^n+c_2q_2^n+...+c_kq_k^n H(n)=c1​q1n​+c2​q2n​+...+ck​qkn​ 为该递推方程的通解。

定理 10.4：有重特征根与通解

设 q 1 , q 2 , . . . , q t q_1,q_2,...,q_t q1​,q2​,...,qt​ 是递推方程(10.2)不等的特征根，且 q i q_i qi​ 的重数为 e i e_i ei​ ，则 H ( n ) = ∑ i = 1 t ( c i 1 + c i 2 n + c i 3 n 2 + . . . + c i e i n e i − 1 ) q i n H(n)=\sum_{i=1}^t(c_{i1}+c_{i2}n+c_{i3}n^2+...+c_{ie_i}n^{e_i-1})q_i^n H(n)=∑i=1t​(ci1​+ci2​n+ci3​n2+...+ciei​​nei​−1)qin​ 为该递推方程的通解。

求解递推方程有以下步骤：

求解 Fibonacci 数列的递推方程。

递推方程是 f n − f n − 1 − f n − 2 = 0 f_n-f_{n-1}-f_{n-2}=0 fn​−fn−1​−fn−2​=0 ，初值是 f 0 = 1 , f 1 = 1 f_0=1,f_1=1 f0​=1,f1​=1 ； 得到特征方程 x 2 − x − 1 = 0 x^2-x-1=0 x2−x−1=0 ； 解得特征根 1 + 5 2 , 1 − 5 2 \frac{1+\sqrt5}{2},\frac{1-\sqrt5}{2} 21+5 ​​,21−5 ​​ ； 设通解为 f n = c 1 ( 1 + 5 2 ) n + c 2 ( 1 − 5 2 ) n f_n=c_1(\frac{1+\sqrt5}{2})^n+c_2(\frac{1-\sqrt5}{2})^n fn​=c1​(21+5 ​​)n+c2​(21−5 ​​)n ； 代入初值 f 0 = 1 , f 1 = 1 f_0=1,f_1=1 f0​=1,f1​=1 ，有

{ c 1 + c 2 = 1 c 1 ( 1 + 5 2 ) + c 2 ( 1 − 5 2 ) = 1 \begin{cases} c_1+c_2=1\\ c_1(\frac{1+\sqrt5}{2})+c_2(\frac{1-\sqrt5}{2})=1 \end{cases} {c1​+c2​=1c1​(21+5 ​​)+c2​(21−5 ​​)=1​

解得 c 1 = 1 5 1 + 5 2 , c 2 = − 1 5 1 − 5 2 c_1=\frac{1}{\sqrt5}\frac{1+\sqrt5}{2},c_2=-\frac{1}{\sqrt5}\frac{1-\sqrt5}{2} c1​=5 ​1​21+5 ​​,c2​=−5 ​1​21−5 ​​ ； 所以递推方程的通解为

f n = 1 5 ( 1 + 5 2 ) n + 1 − 1 5 ( 1 − 5 2 ) n + 1 f_n=\frac{1}{\sqrt5}(\frac{1+\sqrt5}{2})^{n+1}-\frac{1}{\sqrt5}(\frac{1-\sqrt5}{2})^{n+1} fn​=5 ​1​(21+5 ​​)n+1−5 ​1​(21−5 ​​)n+1

求解以下递推方程

{ H ( n ) + H ( n − 1 ) − 3 H ( n − 2 ) − 5 H ( n − 3 ) − 2 H ( n − 4 ) = 0 H ( 0 ) = 1 , H ( 1 ) = 0 , H ( 2 ) = 1 , H ( 3 ) = 2 \begin{cases} H(n)+H(n-1)-3H(n-2)-5H(n-3)-2H(n-4)=0\\ H(0)=1,H(1)=0,H(2)=1,H(3)=2 \end{cases} {H(n)+H(n−1)−3H(n−2)−5H(n−3)−2H(n−4)=0H(0)=1,H(1)=0,H(2)=1,H(3)=2​

特征方程是 x 4 + x 3 − 3 x 2 − 5 x − 2 = 0 x^4+x^3-3x^2-5x-2=0 x4+x3−3x2−5x−2=0 ； 特征根为 − 1 ， − 1 ， − 1 ， 2 -1，-1，-1，2 −1，−1，−1，2 ； 设通解为 H ( n ) = ( c 1 + c 2 n + c 3 n 2 ) ( − 1 ) n + c 4 2 n H(n)=(c_{1}+c_{2}n+c_{3}n^2)(-1)^n+c_42^n H(n)=(c1​+c2​n+c3​n2)(−1)n+c4​2n ； 代入初值得

{ c 1 + c 4 = 1 − c 1 − c 2 − c 3 + 2 c 4 = 0 c 1 + 2 c 2 + 4 c 3 + 4 c 4 = 1 − c 1 − 3 c 2 − 9 c 3 + 8 c 4 = 2 \begin{cases} c_1+c_4=1\\ -c_1-c_2-c_3+2c_4=0\\ c_1+2c_2+4c_3+4c_4=1\\ -c_1-3c_2-9c_3+8c_4=2 \end{cases} ⎩⎪⎪⎪⎨⎪⎪⎪⎧​c1​+c4​=1−c1​−c2​−c3​+2c4​=0c1​+2c2​+4c3​+4c4​=1−c1​−3c2​−9c3​+8c4​=2​

解得 c 1 = 7 9 , c 2 = − 1 3 , c 3 = 0 , c 4 = 2 9 c_1=\frac 7 9,c_2=-\frac 1 3,c_3=0,c_4=\frac 2 9 c1​=97​,c2​=−31​,c3​=0,c4​=92​ ； 所以通解为 H ( n ) = 7 9 ( − 1 ) n − 1 3 n ( − 1 ) n + 2 9 2 n H(n)=\frac 7 9(-1)^n-\frac 1 3n(-1)^n+\frac 2 9 2^n H(n)=97​(−1)n−31​n(−1)n+92​2n

常系数线性非齐次递推方程的标准形是 H ( n ) − a 1 H ( n − 1 ) − . . . − a k H ( n − k ) = f ( n )   ( 10.3 ) H(n)-a_1H(n-1)-...-a_kH(n-k)=f(n)\text{ }(10.3) H(n)−a1​H(n−1)−...−ak​H(n−k)=f(n) (10.3)其中 n ⩾ k , a k ≠ 0 , f ( n ) ≠ 0 n\geqslant k,a_k\neq0,f(n)\neq0 n⩾k,ak​​=0,f(n)​=0 。

定理 10.5：通解的结构

设 H ( n ) ‾ \overline{H(n)} H(n)​ 是对应齐次方程(10.2)的通解， H ∗ ( n ) H^*(n) H∗(n) 是方程（10.3）的一个特解，则 H ( n ) = H ( n ) ‾ + H ∗ ( n ) H(n)=\overline{H(n)}+H^*(n) H(n)=H(n)​+H∗(n) 是递推方程（10.3）的通解。

有了此定理，求解常系数线性非齐次递推方程只需要另外求解出方程的特解：

可按以下一般顺序：

以下是构造特解的一些规律：

例题10.8 找出以下递推方程的特解：

a n − 2 a n − 1 = 2 n 2 a_n-2a_{n-1}=2n^2 an​−2an−1​=2n2

设 a n ∗ = P 1 n 2 + P 2 n + P 3 a_n^*=P_1n^2+P_2n+P_3 an∗​=P1​n2+P2​n+P3​ ； 代入递推方程并整理，得

− P 1 n 2 + ( 4 P 1 − P 2 ) n + ( − 2 P 1 + 2 P 2 − P 3 ) = 2 n 2 -P_1n^2+(4P_1-P_2)n+(-2P_1+2P_2-P_3)=2n^2 −P1​n2+(4P1​−P2​)n+(−2P1​+2P2​−P3​)=2n2

对应系数相等得到线性方程组

{ − P 1 = 2 4 P 1 − P 2 = 0 − 2 P 1 + 2 P 2 − P 3 = 0 \begin{cases} -P_1=2\\ 4P_1-P_2=0\\ -2P_1+2P_2-P_3=0 \end{cases} ⎩⎪⎨⎪⎧​−P1​=24P1​−P2​=0−2P1​+2P2​−P3​=0​

解得 P 1 = − 2 , P 2 = − 8 , P 3 = − 12 P_1=-2,P_2=-8,P_3=-12 P1​=−2,P2​=−8,P3​=−12 ； 所以 a n ∗ = − 2 n 2 − 8 n − 12 a_n^*=-2n^2-8n-12 an∗​=−2n2−8n−12 ；

例题10.9 找出以下递推方程的特解： W ( n ) = W ( n − 1 ) + n − 1 W(n)=W(n-1)+n-1 W(n)=W(n−1)+n−1

设 W ∗ ( n ) = P 1 n 2 + P 2 n W^*(n)=P_1n^2+P_2n W∗(n)=P1​n2+P2​n ； 代入递推方程并整理，得

2 P 1 n + P 2 − P 1 = n − 1 2P_1n+P_2-P_1=n-1 2P1​n+P2​−P1​=n−1

从而得到方程组

{ 2 P 1 = 1 P 2 − P 1 = − 1 \begin{cases} 2P_1=1\\ P_2-P_1=-1 \end{cases} {2P1​=1P2​−P1​=−1​

解得 P 1 = 1 / 2 , P 2 = − 1 / 2 P_1=1/2,P_2=-1/2 P1​=1/2,P2​=−1/2 ； 所以 W ∗ ( n ) = n 2 / 2 − n / 2 W^*(n)=n^2/2-n/2 W∗(n)=n2/2−n/2 ；

例题10.11 找出以下递推方程的特解：

a n = 6 a n − 1 + 8 n − 1 a_n=6a_{n-1}+8^{n-1} an​=6an−1​+8n−1

设 a n ∗ = P 8 n a_n^*=P8^{n} an∗​=P8n ； 代入递推方程得 P 8 n = 6 P 8 n − 1 + 8 n − 1 P8^n=6P8^{n-1}+8^{n-1} P8n=6P8n−1+8n−1 ； 消去 8 n − 1 8^{n-1} 8n−1 项，解得 P = 1 / 2 P=1/2 P=1/2 ； 所以特解为 a n ∗ = 8 n / 2 a_n^*=8^{n}/2 an∗​=8n/2 ；

例题10.12 求递推方程 H ( n ) − 5 H ( n − 1 ) + 6 H ( n − 2 ) = 2 n H(n)-5H(n-1)+6H(n-2)=2^n H(n)−5H(n−1)+6H(n−2)=2n 的特解；

2为特征根，因此令特解 H ∗ ( n ) = P n 2 n H^*(n)=Pn2^n H∗(n)=Pn2n ； 代入特征方程得 P n 2 n − 5 P ( n − 1 ) 2 n − 1 + 6 P ( n − 2 ) 2 n − 2 = 2 n Pn2^n-5P(n-1)2^{n-1}+6P(n-2)2^{n-2}=2^n Pn2n−5P(n−1)2n−1+6P(n−2)2n−2=2n ； 对应系数相等得方程 − P / 2 = 1 -P/2=1 −P/2=1 ； 解得 P ，所以特解为 H ∗ ( n ) = − n 2 n + 1 H^*(n)=-n2^{n+1} H∗(n)=−n2n+1 ；

例如：对于递推方程 a n + 2 a n − 1 = n + 3 n a_n+2a_{n-1}=n+3^n an​+2an−1​=n+3n ； 我们可以设特解为 a n ∗ = P 1 + P 2 n + P 3 3 n a^*_n=P_1+P_2n+P_33^n an∗​=P1​+P2​n+P3​3n ； 代入原方程解得 P 1 = − 1 , P 2 = − 2 , P 3 = 3 P_1=-1,P_2=-2,P_3=3 P1​=−1,P2​=−2,P3​=3 ； 所以特解为 a n ∗ = − 1 − 2 n + 3 n + 1 a^*_n=-1-2n+3^{n+1} an∗​=−1−2n+3n+1 ；

定义 10.5：关于牛顿二项式系数

设 r 为实数，n 为整数，引入形式符号 ( r n ) = { 0 n < 0 1 n = 0 r ( r − 1 ) . . . ( r − n + 1 ) n ! n > 0 \begin{pmatrix} r\\ n \end{pmatrix}= \begin{cases} 0&n\lt0\\ 1&n=0\\ \frac{r(r-1)...(r-n+1)}{n!}&n\gt0 \end{cases} (rn​)=⎩⎪⎨⎪⎧​01n!r(r−1)...(r−n+1)​​n0​ 称为牛顿二项式系数

例如：

( − 2 5 ) = ( − 2 ) ( − 3 ) ( − 4 ) ( − 5 ) ( − 6 ) 5 ! = − 6 \begin{pmatrix}-2\\5\end{pmatrix}=\frac{(-2)(-3)(-4)(-5)(-6)}{5!}=-6 (−25​)=5!(−2)(−3)(−4)(−5)(−6)​=−6 ( 1 / 2 4 ) = ( 1 2 ) ( 1 2 − 1 ) ( 1 2 − 2 ) ( 1 2 − 3 ) 4 ! = − 5 128 \begin{pmatrix}1/2\\4\end{pmatrix}=\frac{(\frac1 2)(\frac 1 2-1)(\frac 1 2 -2)(\frac 1 2-3)}{4!}=-\frac 5 {128} (1/24​)=4!(21​)(21​−1)(21​−2)(21​−3)​=−1285​ ( 4 3 ) = ( 4 ) ( 3 ) ( 2 ) 3 ! = 4 \begin{pmatrix}4\\3\end{pmatrix}=\frac{(4)(3)(2)}{3!}=4 (43​)=3!(4)(3)(2)​=4

也就是说，分母为 n ! n! n! ，分子便有从 r − 0 r-0 r−0 开始的 n 项；

r 为自然数时，牛顿二项式系数就成为普通的二项式系数；

定理10.6：关于牛顿二项式定理

设 a 为实数，则对于一切实数 x , y , ∣ x / y ∣ < 1 x,y,\lvert x/y\rvert\lt1 x,y,∣x/y∣an​} 的生成函数

我们除了定义之外还常用以下的函数展开式（不必太过关注定义域）：

1 1 − x = ∑ n = 0 ∞ x n \frac 1 {1-x}=\sum_{n=0}^\infty x^n 1−x1​=n=0∑∞​xn 1 1 + x = ∑ n = 0 ∞ ( − 1 ) n x n \frac 1 {1+x}=\sum_{n=0}^\infty (-1)^nx^n 1+x1​=n=0∑∞​(−1)nxn

例题 10.20(1) 求序列 { a n } \{a_n\} {an​} 的生成函数， a n = 7 ∗ 3 n a_n=7*3^n an​=7∗3n ；

G ( x ) = ∑ n = 0 ∞ 7 ∗ 3 n x n = 7 ∑ n = 0 ∞ ( 3 x ) n = 7 1 − 3 x G(x)=\sum_{n=0}^\infty7*3^nx^n=7\sum_{n=0}^\infty(3x)^n=\frac 7 {1-3x} G(x)=n=0∑∞​7∗3nxn=7n=0∑∞​(3x)n=1−3x7​

例题 10.21 已知序列 { a n } \{a_n\} {an​} 的生成函数为 G ( x ) = 2 + 3 x − 6 x 2 1 − 2 x G(x)=\frac{2+3x-6x^2}{1-2x} G(x)=1−2x2+3x−6x2​ ，求 { a n } \{a_n\} {an​} 的通项；

G ( x ) = 2 1 − 2 x + 3 x = 2 ∑ i = 0 ∞ ( 2 x ) n + 3 x G(x)=\frac 2 {1-2x}+3x=2\sum_{i=0}^\infty(2x)^n+3x G(x)=1−2x2​+3x=2i=0∑∞​(2x)n+3x

所以

a n = { 2 n + 1 n ≠ 1 2 2 + 3 n = 1 a_n=\begin{cases} 2^{n+1}&n\neq1\\ 2^2+3&n=1\\ \end{cases} an​={2n+122+3​n​=1n=1​

注：因为多出来的 + 3 x +3x +3x 项一定是 a 1 a_1 a1​ 提供的，所以该项需要特判；

S = { n 1 ⋅ a 1 , n 2 ⋅ a 2 , . . . , n k ⋅ a k } S=\{n_1\cdotp a_1,n_2\cdotp a_2,...,n_k\cdotp a_k\} S={n1​⋅a1​,n2​⋅a2​,...,nk​⋅ak​} 的r-组合数就是不定方程

{ x 1 + x 2 + . . . + x k = r x i ⩽ n i i = 1 , 2 , . . . , k \begin{cases} x_1+x_2+...+x_k=r\\ x_i\leqslant n_i &i=1,2,...,k \end{cases} {x1​+x2​+...+xk​=rxi​⩽ni​​i=1,2,...,k​

的非负整数解的个数；

同时就是生成函数 G ( y ) = ( 1 + y + . . . + y n 1 ) ( 1 + y + . . . + y n 2 ) . . . ( 1 + y + . . . + y n k ) G(y)=(1+y+...+y^{n_1})(1+y+...+y^{n_2})...(1+y+...+y^{n_k}) G(y)=(1+y+...+yn1​)(1+y+...+yn2​)...(1+y+...+ynk​) 的展开式中 y r y^r yr 项的系数；

x 1 + x 2 + . . . x k = r x_1+x_2+...x_k=r x1​+x2​+...xk​=r （xi为自然数）解的个数为生成函数 G ( y ) = ( 1 + y + y 2 + . . . ) k G(y)=(1+y+y^2+...)^k G(y)=(1+y+y2+...)k 中 y r y^r yr 项的系数； 有 N = ( k + r − 1 r ) N=\begin{pmatrix}k+r-1\\r\end{pmatrix} N=(k+r−1r​) ；

x 1 + x 2 + . . . x k = r , l i ⩽ x i ⩽ r i x_1+x_2+...x_k=r,l_i\leqslant x_i\leqslant r_i x1​+x2​+...xk​=r,li​⩽xi​⩽ri​

生成函数 G ( y ) = ( y l 1 + y l 1 + 1 + . . . + y r 1 ) ( y l 2 + y l 2 + 1 + . . . + y r 2 ) . . . ( y l k + y l k + 1 + . . . + y r k ) G(y)=(y^{l_1}+y^{l_1+1}+...+y^{r_1})(y^{l_2}+y^{l_2+1}+...+y^{r_2})...(y^{l_k}+y^{l_k+1}+...+y^{r_k}) G(y)=(yl1​+yl1​+1+...+yr1​)(yl2​+yl2​+1+...+yr2​)...(ylk​+ylk​+1+...+yrk​)

p 1 x 1 + p 2 x 2 + . . . + p k x k = r p_1x_1+p_2x_2+...+p_kx_k=r p1​x1​+p2​x2​+...+pk​xk​=r（xi为自然数） 生成函数 G ( y ) = ( 1 + y p 1 + y 2 p 1 + . . . ) ( 1 + y p 2 + y 2 p 2 + . . . ) . . . ( 1 + y p k + y 2 p k + . . . ) G(y)=(1+y^{p_1}+y^{2p_1}+...)(1+y^{p_2}+y^{2p_2}+...)...(1+y^{p_k}+y^{2p_k}+...) G(y)=(1+yp1​+y2p1​+...)(1+yp2​+y2p2​+...)...(1+ypk​+y2pk​+...)

基本模型：将 N 无序拆分成正整数 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1​,a2​,...,an​ ；

G ( y ) = ( 1 + y a 1 ) ( 1 + y a 2 ) . . . ( 1 + y a n ) G(y)=(1+y^{a_1})(1+y^{a_2})...(1+y^{a_n}) G(y)=(1+ya1​)(1+ya2​)...(1+yan​) 中 y N y^N yN 项的系数；

G ( y ) = ( 1 + y a 1 + y 2 a 1 + . . . ) ( 1 + y a 2 + y 2 a 2 + . . . ) . . . ( 1 + y a n + y 2 a n + . . . ) = 1 ( 1 − y a 1 ) ( 1 − y a 2 ) . . . ( 1 − y a n ) G(y)=(1+y^{a_1}+y^{2a_1}+...)(1+y^{a_2}+y^{2a_2}+...)...(1+y^{a_n}+y^{2a_n}+...)=\frac 1 {(1-y^{a_1})(1-y^{a_2})...(1-y^{a_n})} G(y)=(1+ya1​+y2a1​+...)(1+ya2​+y2a2​+...)...(1+yan​+y2an​+...)=(1−ya1​)(1−ya2​)...(1−yan​)1​

定义 10.7：关于指数生成函数

设 { a n } \{a_n\} {an​} 为序列，称 G e ( x ) = ∑ n = 0 ∞ a n x n n ! G_e(x)=\sum^\infty_{n=0}a_n\frac {x^n} {n!} Ge​(x)=n=0∑∞​an​n!xn​ 为 { a n } \{a_n\} {an​} 的指数生成函数

例题 10.27 给定正整数 m ， a n = P ( m , n ) a_n=P(m,n) an​=P(m,n) ，则 { a n } \{a_n\} {an​} 的生成函数为

G e ( x ) = ∑ n = 0 ∞ P ( m , n ) x n n ! = ∑ n = 0 ∞ m ! n ! ( m − n ) ! x n = ∑ n = 0 ∞ ( m n ) x n = ( 1 + x ) m G_e(x)=\sum^\infty_{n=0}P(m,n)\frac {x^n}{n!}=\sum_{n=0}^\infty\frac{m!}{n!(m-n)!}x^n=\sum_{n=0}^\infty\begin{pmatrix}m\\n\end{pmatrix}x^n=(1+x)^m Ge​(x)=n=0∑∞​P(m,n)n!xn​=n=0∑∞​n!(m−n)!m!​xn=n=0∑∞​(mn​)xn=(1+x)m

由此可见，对于给定 m ， ( 1 + x ) m (1+x)^m (1+x)m 既是集合组合数序列 { C ( m , n ) } \{C(m,n)\} {C(m,n)} 的普通生成函数，也是集合排列数序列 { P ( m , n ) } \{P(m,n)\} {P(m,n)} 的指数生成函数；

设数列 { a n } , { b n } \{a_n\},\{b_n\} {an​},{bn​} 的指数生成函数分别为 A e ( x ) A_e(x) Ae​(x) 和 B e ( x ) B_e(x) Be​(x) ，则

A e ( x ) ⋅ B e ( x ) = ∑ n = 0 ∞ c n x n n ! A_e(x)\cdotp B_e(x)=\sum_{n=0}^\infty c_n\frac {x^n}{n!} Ae​(x)⋅Be​(x)=n=0∑∞​cn​n!xn​

其中

c n = ∑ k = 0 n ( n k ) a k b n − k c_n=\sum_{k=0}^n\begin{pmatrix}n\\k\end{pmatrix}a_kb_{n-k} cn​=k=0∑n​(nk​)ak​bn−k​

定理 10.8：指数生成函数求解多重集的排列问题

设 S = { n 1 ⋅ a 1 , n 2 ⋅ a 2 , . . . , n k ⋅ a k } S=\{n_1\cdotp a_1,n_2\cdotp a_2,...,n_k\cdotp a_k\} S={n1​⋅a1​,n2​⋅a2​,...,nk​⋅ak​} 为多重集，则 S 的 r-排列数的指数生成函数为 G e ( x ) = f n 1 ( x ) f n 2 ( x ) . . . f n k ( x ) G_e(x)=f_{n_1}(x)f_{n_2}(x)...f_{n_k}(x) Ge​(x)=fn1​​(x)fn2​​(x)...fnk​​(x) 其中 f n i ( x ) = 1 + x + x 2 2 ! + . . . + x n i n i ! , n = 1 , 2 , . . . , k f_{n_i}(x)=1+x+\frac{x^2}{2!}+...+\frac{x^{n_i}}{n_i!},n=1,2,...,k fni​​(x)=1+x+2!x2​+...+ni​!xni​​,n=1,2,...,k

其中 x r r ! \frac {x^r}{r!} r!xr​ 项的系数即为所求；

例 由1, 2, 3, 4 组成的五位数中，要求1出现不超过2次，但不能不出现，2出现不超过1次，3出现可达3次，4出现偶数次. 求这样的五位数个数；

G e ( x ) = ( x + x 2 2 ! ) ( 1 + x ) ( 1 + x + x 2 2 ! + x 3 3 ! ) ( 1 + x 2 2 ! + x 4 4 ! ) G_e(x)=(x+\frac {x^2}{2!})(1+x)(1+x+\frac {x^2}{2!}+\frac {x^3}{3!})(1+\frac {x^2}{2!}+\frac {x^4}{4!}) Ge​(x)=(x+2!x2​)(1+x)(1+x+2!x2​+3!x3​)(1+2!x2​+4!x4​) = x + 5 x 2 2 ! + 18 x 3 3 ! + 64 x 4 4 ! + 512 x 5 5 ! + . . . =x+5\frac{x^2}{2!}+18\frac{x^3}{3!}+64\frac{x^4}{4!}+512\frac{x^5}{5!}+... =x+52!x2​+183!x3​+644!x4​+5125!x5​+...

即答案为 512；

例 红、白、蓝涂色 1 × n 1\times n 1×n 的方格，要求偶数个为白色，问有多少方案？

设方案数为 a n a_n an​ ；

G e ( x ) = ( 1 + x + x 2 2 ! + . . . ) 2 ( 1 + x 2 2 ! + x 4 4 ! + . . . ) G_e(x)=(1+x+\frac {x^2}{2!}+...)^2(1+\frac {x^2}{2!}+\frac {x^4}{4!}+...) Ge​(x)=(1+x+2!x2​+...)2(1+2!x2​+4!x4​+...) = 1 2 ( e x + e − x ) e 2 x = 1 2 ( e 3 x + e x ) =\frac 1 2(e^x+e^{-x})e^{2x}=\frac 1 2(e^{3x}+e^x) =21​(ex+e−x)e2x=21​(e3x+ex) = 1 2 ( ∑ n = 0 ∞ ( 3 x ) n n ! + ∑ n = 0 ∞ x n n ! ) =\frac 1 2(\sum_{n=0}^\infty\frac {(3x)^n}{n!}+\sum_{n=0}^\infty\frac {x^n}{n!}) =21​(n=0∑∞​n!(3x)n​+n=0∑∞​n!xn​)

故

a n = 3 n + 1 2 a_n=\frac {3^n+1}{2} an​=23n+1​

定义 10.8：关于Catalan数

一个凸 n+1边形，通过不相交于n+1 边形内部的对角线把 n+1 边形划分成三角形，划分方案个数记作hn，称为Catalan数

{ h n = ∑ k = 1 n − 1 h k h n − k h 1 = 1 \begin{cases} h_n=\sum_{k=1}^{n-1}h_kh_{n-k}\\ h_1=1 \end{cases} {hn​=∑k=1n−1​hk​hn−k​h1​=1​

解为

h n = 1 n ( 2 n − 2 n − 1 ) h_n=\frac 1 n \begin{pmatrix}2n-2\\ n-1\end{pmatrix} hn​=n1​(2n−2n−1​)

\

版权声明：本文为CSDN博主「Tan_Yuu」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/Tan_Yuu/article/details/117930803