参考博客 :

生成函数应用场景 :

多重集 r r r 组合计数 , 之前 只能计数特殊情况下的组合数 , 也就是选取数 r r r 小于多重集每一项的重复度 , 才有 组合数 N = C ( k + r − 1 , r ) N= C(k + r - 1, r) N=C(k+r−1,r) , 如果 r r r 大于重复度 , 就需要使用生成函数进行求解 ;

不定方程的解个数 , 之前只能求解 没有约束的情况 , 如果对变量有约束 , 如 x 1 x_1 x1​ 只能在某个区间取值 , 这种情况下 , 就必须使用生成函数进行求解 ;

整数拆分 , 将一个正数拆分多若干整数之和 , 拆分方案个数 , 也可以通过生成函数进行计算 ;

回顾多重集排列组合 :

递推方程 : a n − 5 a n − 1 + 6 a n − 2 = 0 a_n - 5a_{n-1} + 6a_{n-2} = 0 an​−5an−1​+6an−2​=0

初值 : a 0 = 1 , a 1 = 2 a_0 = 1, a_1 = 2 a0​=1,a1​=2

{ a n } \{a_n\} {an​} 数列为 { a 0 , a 1 , a 2 , a 3 , ⋯   , a n , ⋯   } \{ a_0 , a_1, a_2, a_3 , \cdots , a_n , \cdots\} {a0​,a1​,a2​,a3​,⋯,an​,⋯}

a n a_n an​对应的生成函数是 G ( x ) = a 0 + a 1 x + a 2 x 2 + a 3 x 3 + ⋯ G(x) = a_0 + a_1 x + a_2 x^2 + a_3x^3 + \cdots G(x)=a0​+a1​x+a2​x2+a3​x3+⋯

根据递推方程 , 同时为了使得后面的项可以约掉 , 使用 − 5 x -5x −5x 乘以 G ( x ) G(x) G(x) 生成函数 , 使用 + 6 x 2 +6x^2 +6x2 乘以 G ( x ) G(x) G(x) , 得到如下三个式子 ,

− 5 x -5x −5x 乘以 G ( x ) G(x) G(x) 得到的第一项就是 x x x 的一次方项 , 将该项对应到 G ( x ) G(x) G(x) 中的 x x x 一次方项下面 ,

+ 6 x 2 +6x^2 +6x2 乘以 G ( x ) G(x) G(x) 得到的第一项就是 x x x 的二次方项 , 将该项对应到 G ( x ) G(x) G(x) 中的 x x x 二次方项下面 ;

                         G ( x ) = a 0 + a 1 x + a 2 x 2 + a 3 x 3 + ⋯ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ G(x) = a_0 + a_1 x + a_2 x^2 + a_3x^3 + \cdots                         G(x)=a0​+a1​x+a2​x2+a3​x3+⋯

                 − 5 x   G ( x ) =      − 5 a 0 x − 5 a 1 x 2 − 5 a 2 x 3 − ⋯ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ -5x \ G(x) = \ \ \ \ -5a_0x - 5a_1x^2 - 5a_2x^3 - \cdots                 −5x G(x)=    −5a0​x−5a1​x2−5a2​x3−⋯

                   6 x 2   G ( x ) =                  +   6 a 0 x 2 + 6 a x 3 + ⋯ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 6x^2 \,G(x) = \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ + \,6a_0x^2 + 6a_x^3 + \cdots                   6x2G(x)=                +6a0​x2+6ax3​+⋯

( 1 − 5 x + 6 x 2 ) G ( x ) = a 0 + ( a 1 − 5 a 0 ) x (1-5x+6x^2)G(x) =a_0 + (a_1 - 5a_0)x (1−5x+6x2)G(x)=a0​+(a1​−5a0​)x

上述横线下的式子是 横线上面 三个式子相加的结果 ;

观察上述右侧 第三列 , 图中红框部分 ;

上述幂次对齐后 , 出现的等号右侧的第三列 + a 2 x 2 − 5 a 1 x 2 +   6 a 0 x 2 + a_2 x^2 -5a_1x^2 + \,6a_0x^2 +a2​x2−5a1​x2+6a0​x2 , 将其中 x 2 x^2 x2 提取出来得到 ( a 2 − 5 a 1 + 6 a 0 ) x 2 (a_2 - 5a_1 + 6a_0)x^2 (a2​−5a1​+6a0​)x2 , 正好对应递推方程 a n − 5 a n − 1 + 6 a n − 2 = 0 a_n - 5a_{n-1} + 6a_{n-2} = 0 an​−5an−1​+6an−2​=0 ,

因此有 a 2 − 5 a 1 + 6 a 0 = 0 a_2 - 5a_1 + 6a_0 = 0 a2​−5a1​+6a0​=0 , 进而可以得到 ( a 2 − 5 a 1 + 6 a 0 ) x 2 = 0 (a_2 - 5a_1 + 6a_0)x^2 = 0 (a2​−5a1​+6a0​)x2=0

由此可以看出 , 如果三个式子全部相加 , 下图 右侧蓝色矩形框内 , 全部都是 0 0 0 ;

目前右侧只剩下 a 0 + a 1 x − 5 a 0 x a_0 + a_1x -5a_0x a0​+a1​x−5a0​x 三项 ; 其中的 a 0 = 1 , a 1 = − 2 a_0 = 1 , a_1 = -2 a0​=1,a1​=−2 是初值 ;

最终等式右侧是 : 1 − 2 x − 5 x = 1 − 7 x 1 - 2x - 5x = 1-7x 1−2x−5x=1−7x

将上述式子代入到 ( 1 − 5 x + 6 x 2 ) G ( x ) = a 0 + ( a 1 − 5 a 0 ) x (1-5x+6x^2)G(x) =a_0 + (a_1 - 5a_0)x (1−5x+6x2)G(x)=a0​+(a1​−5a0​)x 中 , 使用 1 − 2 x − 5 x = 1 − 7 x 1 - 2x - 5x = 1-7x 1−2x−5x=1−7x 替换等式右侧的式子 , 得到 :

( 1 − 5 x + 6 x 2 ) G ( x ) = 1 − 7 x (1-5x+6x^2)G(x) =1-7x (1−5x+6x2)G(x)=1−7x

G ( x ) = 1 − 7 x 1 − 5 x + 6 x 2 G(x) = \cfrac{1-7x}{1-5x+6x^2} G(x)=1−5x+6x21−7x​

使用 给定 生成函数 , 求对应的级数 的 方法 , 将上述式子展开 , 参考 【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 ) 二、给定生成函数求级数 方法 ,

先将分母进行因式分解 , 然后设置两个待定系数 , 通分后 , 根据 x x x 项系数写出方程组 , 最终解该方程组 , 最终可以得到 :

G ( x ) = 1 − 7 x 1 − 5 x + 6 x 2 = 5 1 − 2 x − 4 1 − 3 x G(x) = \cfrac{1-7x}{1-5x+6x^2} = \cfrac{5}{1-2x} - \cfrac{4}{1-3x} G(x)=1−5x+6x21−7x​=1−2x5​−1−3x4​

5 1 − 2 x \cfrac{5}{1-2x} 1−2x5​ 对应的级数是 : ∑ n = 0 ∞ 5 ( 2 x ) n = 5 ∑ n = 0 ∞ 2 n x n \sum\limits_{n=0}^\infty 5 (2x)^n = 5\sum\limits_{n=0}^\infty 2^n x^n n=0∑∞​5(2x)n=5n=0∑∞​2nxn

4 1 − 3 x \cfrac{4}{1-3x} 1−3x4​ 对应的级数是 : ∑ n = 0 ∞ ( − 4 ) ( 3 x ) n = − 4 ∑ n = 0 ∞ 3 n x n \sum\limits_{n=0}^\infty (-4) (3x)^n = -4\sum\limits_{n=0}^\infty 3^n x^n n=0∑∞​(−4)(3x)n=−4n=0∑∞​3nxn

最终生成函数的级数形式为 : G ( x ) = 5 ∑ n = 0 ∞ 2 n x n − 4 ∑ n = 0 ∞ 3 n x n G(x) = 5\sum\limits_{n=0}^\infty 2^n x^n - 4\sum\limits_{n=0}^\infty 3^n x^n G(x)=5n=0∑∞​2nxn−4n=0∑∞​3nxn

递推方程的通解 : a n = 5 ⋅ 2 n − 4 ⋅ 3 n a_n = 5 \cdot 2^n - 4 \cdot 3^n an​=5⋅2n−4⋅3n

基本思路 : 有原来的递推方程 , 导出关于生成函数的递推方程 ;