离散数学15：递推方程与生成函数 |
您所在的位置：网站首页 › 生成函数求解递推关系 › 离散数学15：递推方程与生成函数 |
离散数学15：递推方程与生成函数
|
递推方程
递推方程有无数个解, 但是在给定初值下的解是唯一的. 常系数线性齐次递推方程 —— 特征方程。 特征方程的根的情况通解无重根 C 1 α 1 n + C 2 α 2 n + . . . + C N α N n C_1\alpha_1^n+C_2\alpha_2^n+...+C_N\alpha_N^n C1α1n+C2α2n+...+CNαNn有k重根 ( C 1 n k − 1 + C 2 n k − 2 + . . . + C k ) α n (C_1n^{k-1}+C_2n^{k-2}+...+C_k)\alpha^n (C1nk−1+C2nk−2+...+Ck)αn 常系数线性非齐次递推方程 —— 齐次通解+特解 f ( n ) f(n) f(n)形式特解 n k n^k nk D 0 n k + D 1 n k − 1 + . . . + D k D_0n^k+D_1n^{k-1}+...+D_k D0nk+D1nk−1+...+Dk C α n C\alpha^n Cαn（α是特征根） D n k α n Dn^k\alpha^n Dnkαn C β n Cβ^n Cβn（β不是特征根） D α n D\alpha^n Dαn
对于数列 { a 0 , a 1 , . . . , a n , . . . } \{a_0,a_1,...,a_n,...\} {a0,a1,...,an,...}，令 G ( x ) = a 0 + a 1 x + a 2 x 2 + . . . + a n x n + . . . G(x)=a_0+a_1x+a_2x^2+...+a_nx^n+... G(x)=a0+a1x+a2x2+...+anxn+...，将其称为 { a n } \{a_n\} {an}的生成函数。 利用生成函数求多重集 S = { n 1 ⋅ a 1 , n 2 ⋅ a 2 , . . . , n k ⋅ a k } S=\{n_1·a_1,\ n_2·a_2,...,\ n_k·a_k\} S={n1⋅a1, n2⋅a2,..., nk⋅ak}的 r r r组合数： 构造函数 G ( y ) = ( 1 + y + y 2 + . . . + y n 1 ) ( 1 + y + y 2 + . . . + y n 2 ) . . . ( 1 + y + y 2 + . . . + y n k ) G(y)=(1+y+y^2+...+y^{n_1})(1+y+y^2+...+y^{n_2})...(1+y+y^2+...+y^{n_k}) G(y)=(1+y+y2+...+yn1)(1+y+y2+...+yn2)...(1+y+y2+...+ynk)展开后 y r y^r yr的系数即为 r r r组合数。 指数生成函数对于数列 { a 0 , a 1 , . . . , a n , . . . } \{a_0,a_1,...,a_n,...\} {a0,a1,...,an,...}，令 G e ( x ) = ∑ n = 0 ∞ a n x n n ! G_e(x)=\sum\limits_{n=0}^{\infin}a_n\frac{x^n}{n!} Ge(x)=n=0∑∞ann!xn，将其称为 { a n } \{a_n\} {an}的指数生成函数。 利用生成函数求多重集 S = { n 1 ⋅ a 1 , n 2 ⋅ a 2 , . . . , n k ⋅ a k } S=\{n_1·a_1,\ n_2·a_2,...,\ n_k·a_k\} S={n1⋅a1, n2⋅a2,..., nk⋅ak}的 r r r排列数： 构造函数 G e ( y ) = ( 1 + y + y 2 2 ! + . . . + y n 1 n 1 ! ) ( 1 + y + y 2 2 ! + . . . + y n 2 n 2 ! ) . . . ( 1 + y + y 2 2 ! + . . . + y n k n k ! ) G_e(y)=(1+y+\frac{y^2}{2!}+...+\frac{y^{n_1}}{n_1!})(1+y+\frac{y^2}{2!}+...+\frac{y^{n_2}}{n_2!})...(1+y+\frac{y^2}{2!}+...+\frac{y^{n_k}}{n_k!}) Ge(y)=(1+y+2!y2+...+n1!yn1)(1+y+2!y2+...+n2!yn2)...(1+y+2!y2+...+nk!ynk)展开后 y r y^r yr的系数再乘以 r ! r! r!即为 r r r排列数，也就是 y r r ! \frac{y^r}{r!} r!yr的系数。 |
【本文地址】
今日新闻 |
推荐新闻 |