参考博客 :

• 【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
• 【组合数学】生成函数 ( 线性性质 | 乘积性质 )
• 【组合数学】生成函数 ( 移位性质 )

一、生成函数求和性质 1 ( 向前求和 )

---

生成函数求和性质 1 :

b n = ∑ i = 0 n a i b_n = \sum\limits_{i=0}^{n}a_i bn​=i=0∑n​ai​ , 则 B ( x ) = A ( x ) 1 − x B(x) = \cfrac{A(x)}{1-x} B(x)=1−xA(x)​

数列 a n a_n an​ 的生成函数是 A ( x ) A(x) A(x) , 数列 b n b_n bn​ 的生成函数是 B ( x ) B(x) B(x) ,

数列 a n = { a 0 , a 1 , a 2 , ⋯   } a_n = \{ a_0 , a_1, a_2 , \cdots \} an​={a0​,a1​,a2​,⋯} , 数列 b n = { b 0 , b 1 , b 2 , ⋯   } b_n = \{ b_0 , b_1, b_2 , \cdots \} bn​={b0​,b1​,b2​,⋯} ;

数列 a n a_n an​ 的生成函数 A ( x ) = a 0 + a 1 x + a 2 x 2 + ⋯ A(x) = a_0 + a_1x + a_2x^2 + \cdots A(x)=a0​+a1​x+a2​x2+⋯

数列 b n b_n bn​ 的生成函数 B ( x ) = b 0 + b 1 x + b 2 x 2 + ⋯ B(x) = b_0 + b_1x + b_2x^2 + \cdots B(x)=b0​+b1​x+b2​x2+⋯

b n b_n bn​ 数列中的第 n n n 项 , 等于 a n a_n an​ 数列中的前 n n n 项的和 ;

推导 b n b_n bn​ 数列的项 :

b 0 = a 0 b_0 = a_0 b0​=a0​

b 1 = a 0 + a 1 b_1 = a_0 + a_1 b1​=a0​+a1​

b 2 = a 0 + a 1 + a 2 b_2 = a_0 + a_1 + a_2 b2​=a0​+a1​+a2​

⋮ \vdots ⋮

b n = a 0 + a 1 + a 2 + ⋯ + a n b_n = a_0 + a_1 + a_2 + \cdots + a_n bn​=a0​+a1​+a2​+⋯+an​

推导生成函数的项 :

B ( x ) B(x) B(x) 中的 x 0 x^0 x0 项 ( 常数项 ) : b 0     = a 0 b_0 \ \ \ = a_0 b0​   =a0​

B ( x ) B(x) B(x) 中的 x 1 x^1 x1 项 ( 常数项 ) : b 1 x   = ( a 0 + a 1 ) x b_1x \ = (a_0 + a_1)x b1​x =(a0​+a1​)x

B ( x ) B(x) B(x) 中的 x 2 x^2 x2 项 ( 常数项 ) : b 2 x 2 = ( a 0 + a 1 + a 2 ) x 2 b_2x^2 = (a_0 + a_1 + a_2)x^2 b2​x2=(a0​+a1​+a2​)x2

⋮ \vdots ⋮

B ( x ) B(x) B(x) 中的 x n x^n xn 项 ( 常数项 ) : b n x n = ( a 0 + a 1 + a 2 + ⋯ + a n ) x n b_nx^n = (a_0 + a_1 + a_2 + \cdots + a_n)x^n bn​xn=(a0​+a1​+a2​+⋯+an​)xn

将上述 B ( x ) B(x) B(x) 中的各项相加 : 相加的策略是纵向相加 , 如下图所示 :

第 1 1 1 列相加 : a 0 + a 0 x + a 0 x 2 + ⋯ + a 0 x n = a 0 1 1 − x a_0 + a_0 x + a_0x^2 + \cdots + a_0x^n = a_0\cfrac{1}{1-x} a0​+a0​x+a0​x2+⋯+a0​xn=a0​1−x1​

第 2 2 2 列相加 : a 1 x + a 1 x 2 + ⋯ + a 1 x n = a 1 x 1 1 − x a_1 x + a_1x^2 + \cdots + a_1x^n = a_1x\cfrac{1}{1-x} a1​x+a1​x2+⋯+a1​xn=a1​x1−x1​

⋮ \vdots ⋮

第 n n n 列相加 : a n x n = a n x n 1 1 − x a_nx^n = a_nx^n\cfrac{1}{1-x} an​xn=an​xn1−x1​

最终得到 :

B ( x ) = a 0 1 1 − x + a 1 x 1 1 − x + ⋯ + a n x n 1 1 − x + ⋯ B(x) = a_0\cfrac{1}{1-x} + a_1x\cfrac{1}{1-x} + \cdots + a_nx^n\cfrac{1}{1-x} + \cdots B(x)=a0​1−x1​+a1​x1−x1​+⋯+an​xn1−x1​+⋯

将其中的 1 1 − x \cfrac{1}{1-x} 1−x1​ 提取出来 , 就可以得到 :

B ( x ) = 1 1 − x ( a 0 + a 1 x + + ⋯ + a n x n + ⋯   ) B(x) = \cfrac{1}{1-x} ( a_0 + a_1x + + \cdots + a_nx^n + \cdots ) B(x)=1−x1​(a0​+a1​x++⋯+an​xn+⋯)

B ( x ) = 1 1 − x A ( x ) B(x) = \cfrac{1}{1-x} A(x) B(x)=1−x1​A(x)

二、生成函数求和性质 2 ( 向后求和 )

---

生成函数求和性质 2 :

b n = ∑ i = n ∞ a i b_n = \sum\limits_{i=n}^{\infty}a_i bn​=i=n∑∞​ai​ , 并且 A ( 1 ) = ∑ i = n ∞ a i A(1) =\sum\limits_{i=n}^{\infty}a_i A(1)=i=n∑∞​ai​ 收敛 , 则 B ( x ) = A ( 1 ) − x A ( x ) 1 − x B(x) = \cfrac{A(1) - xA(x)}{1-x} B(x)=1−xA(1)−xA(x)​