IDEA激活码
文章目录
- 一、生成函数线性性质
- 二、生成函数线性性质2
- 三、生成函数乘积性质
参考博客 :
- 【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
一、生成函数线性性质
生成函数 线性性质 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∑naibn−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+a1x+a2x2+⋯
数列
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+b1x+b2x2+⋯
数列
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+c1x+c2x2+⋯
右边的 两个生成函数
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+a1x+a2x2+⋯)×(b0+b1x+b2x2+⋯)
按照多项式乘法 ,
x
0
x^0
x0 ,
0
0
0次方项 , 即常数项, 构成方法有
1
1
1 种 , 两个生成函数中的常数项 , 相乘之后是
a
0
b
0
a_0 b_0
a0b0 ,
x
1
x^1
x1 ,
1
1
1次方项 , 构成方法有
2
2
2 种 ,
-
A
(
x
)
A(x)
A(x) 中的a
1
x
a_1x
a1x 与B
(
x
)
B(x)
B(x) 中的b
0
b_0
b0 , 构成x
1
x^1
x1 一次方项a
1
b
0
x
a_1b_0x
a1b0x ; -
A
(
x
)
A(x)
A(x) 中的a
0
a_0
a0 与B
(
x
)
B(x)
B(x) 中的b
1
x
b_1x
b1x , 构成x
1
x^1
x1 一次方项a
0
b
1
x
a_0b_1x
a0b1x ;
x
1
x^1
x1 ,
1
1
1次方项的系数是
a
1
b
0
+
a
0
b
1
a_1b_0 + a_0b_1
a1b0+a0b1 , 完整的
1
1
1次方项是
(
a
1
b
0
+
a
0
b
1
)
x
(a_1b_0 + a_0b_1)x
(a1b0+a0b1)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
b2x2 , 构成x
2
x^2
x2 ,2
2
2次方项a
0
b
2
x
2
a_0b_2x^2
a0b2x2 ; -
A
(
x
)
A(x)
A(x) 中的a
2
x
2
a_2x^2
a2x2 与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
a2b0x2 ; -
A
(
x
)
A(x)
A(x) 中的a
1
x
a_1x
a1x 与B
(
x
)
B(x)
B(x) 中的b
1
x
b_1x
b1x , 构成x
2
x^2
x2 ,2
2
2次方项a
1
b
1
x
2
a_1b_1x^2
a1b1x2 ;
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
a0b2+a2b0+a1b1 , 完整的
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
(a0b2+a2b0+a1b1)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∑naibn−i , 由
n
+
1
n+1
n+1 项组成 , 每一项的
a
i
,
b
n
−
i
a_i,b_{n-i}
ai,bn−i 下标之和是
n
n
n ;
