【组合数学】生成函数 ( 线性性质 | 乘积性质 )

参考博客 :

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

一、生成函数线性性质

生成函数 线性性质 1 :

b n = α a n b_n = \alpha a_n bn​=αan​ , 则 B ( x ) = α A ( x ) B(x) = \alpha A(x) B(x)=αA(x)

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

如果 b n b_n bn​ 数列 是 a n a_n an​ 数列 的 α \alpha α 倍 , 那么对应的 生成函数也存在对应的关系 ;

证明方法 : 将两边展开 , 根据定义代入即可 ;

二、生成函数线性性质2

生成函数 线性性质 2 :

c n = a n + b n c_n = a_n + b_n cn​=an​+bn​ , 则 C ( x ) = A ( x ) + B ( x ) C(x) = A(x) + B(x) C(x)=A(x)+B(x)

数列 a n a_n an​ 的生成函数是 A ( x ) A(x) A(x) , 数列 b n b_n bn​ 的生成函数是 B ( x ) B(x) B(x) , 数列 c n c_n cn​ 的生成含税是 C ( x ) C(x) C(x) ,

数列和 的 生成函数 , 等于 生成函数的和 ;

一个数列是 其它数列的线性组合 , 那么将其 生成函数进行相应的组合 , 也能求出 大的数列的生成函数 ;

证明方法 : 将两边展开 , 根据定义代入即可 ;

三、生成函数乘积性质

生成函数 乘积性质 :

c n = ∑ i = 0 n a i b n − i c_n = \sum\limits_{i=0}^n a_i b_{n-i} cn​=i=0∑n​ai​bn−i​ , 则有 C ( x ) = A ( x ) ⋅ B ( x ) C(x) = A(x) \cdot B(x) C(x)=A(x)⋅B(x)

数列 a n a_n an​ 的生成函数是 A ( x ) A(x) A(x) , 数列 b n b_n bn​ 的生成函数是 B ( x ) B(x) B(x) , 数列 c n c_n cn​ 的生成含税是 C ( x ) C(x) C(x) ,

数列 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+⋯

数列 c n c_n cn​ 的生成函数 : C ( x ) = c 0 + c 1 x + c 2 x 2 + ⋯ C(x) = c_0 + c_1x + c_2x^2 + \cdots C(x)=c0​+c1​x+c2​x2+⋯

右边的 两个生成函数 A ( x ) A(x) A(x) 和 B ( x ) B(x) B(x) 相乘 :

( a 0 + a 1 x + a 2 x 2 + ⋯   ) × ( b 0 + b 1 x + b 2 x 2 + ⋯   ) (a_0 + a_1x + a_2x^2 + \cdots) \times ( b_0 + b_1x + b_2x^2 + \cdots ) (a0​+a1​x+a2​x2+⋯)×(b0​+b1​x+b2​x2+⋯)

按照多项式乘法 ,

x 0 x^0 x0 , 0 0 0次方项 , 即常数项, 构成方法有 1 1 1 种 , 两个生成函数中的常数项 , 相乘之后是 a 0 b 0 a_0 b_0 a0​b0​ ,

x 1 x^1 x1 , 1 1 1次方项 , 构成方法有 2 2 2 种 ,

• A ( x ) A(x) A(x) 中的 a 1 x a_1x a1​x 与 B ( x ) B(x) B(x) 中的 b 0 b_0 b0​ , 构成 x 1 x^1 x1 一次方项 a 1 b 0 x a_1b_0x a1​b0​x ;
• A ( x ) A(x) A(x) 中的 a 0 a_0 a0​ 与 B ( x ) B(x) B(x) 中的 b 1 x b_1x b1​x , 构成 x 1 x^1 x1 一次方项 a 0 b 1 x a_0b_1x a0​b1​x ;

x 1 x^1 x1 , 1 1 1次方项的系数是 a 1 b 0 + a 0 b 1 a_1b_0 + a_0b_1 a1​b0​+a0​b1​ , 完整的 1 1 1次方项是 ( a 1 b 0 + a 0 b 1 ) x (a_1b_0 + a_0b_1)x (a1​b0​+a0​b1​)x

x 2 x^2 x2 , 2 2 2 次方项 , 构成方法有 3 3 3 种 ,

• A ( x ) A(x) A(x) 中的 a 0 a_0 a0​ 与 B ( x ) B(x) B(x) 中的 b 2 x 2 b_2x^2 b2​x2 , 构成 x 2 x^2 x2 , 2 2 2次方项 a 0 b 2 x 2 a_0b_2x^2 a0​b2​x2 ;
• A ( x ) A(x) A(x) 中的 a 2 x 2 a_2x^2 a2​x2 与 B ( x ) B(x) B(x) 中的 b 0 b_0 b0​ , 构成 x 2 x^2 x2 , 2 2 2次方项 a 2 b 0 x 2 a_2b_0x^2 a2​b0​x2 ;
• A ( x ) A(x) A(x) 中的 a 1 x a_1x a1​x 与 B ( x ) B(x) B(x) 中的 b 1 x b_1x b1​x , 构成 x 2 x^2 x2 , 2 2 2次方项 a 1 b 1 x 2 a_1b_1x^2 a1​b1​x2 ;

x 2 x^2 x2 , 2 2 2次方项的系数是 a 0 b 2 + a 2 b 0 + a 1 b 1 a_0b_2 + a_2b_0 + a_1b_1 a0​b2​+a2​b0​+a1​b1​ , 完整的 2 2 2次方项是 ( a 0 b 2 + a 2 b 0 + a 1 b 1 ) x 2 (a_0b_2 + a_2b_0 + a_1b_1)x^2 (a0​b2​+a2​b0​+a1​b1​)x2

规律 : x x x 的 n n n 次方项 , 其系数是 ∑ i = 0 n a i b n − i \sum\limits_{i=0}^n a_i b_{n-i} i=0∑n​ai​bn−i​ , 由 n + 1 n+1 n+1 项组成 , 每一项的 a i , b n − i a_i,b_{n-i} ai​,bn−i​ 下标之和是 n n n ;