IDEA激活码
文章目录
- 一、生成函数求和性质 1 ( 向前求和 )
- 二、生成函数求和性质 2 ( 向后求和 )
参考博客 :
- 【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
- 【组合数学】生成函数 ( 线性性质 | 乘积性质 )
- 【组合数学】生成函数 ( 移位性质 )
一、生成函数求和性质 1 ( 向前求和 )
生成函数求和性质 1 :
b
n
=
∑
i
=
0
n
a
i
b_n = \sum\limits_{i=0}^{n}a_i
bn=i=0∑nai , 则
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+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+⋯
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
b1x =(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
b2x2=(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
bnxn=(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+a0x+a0x2+⋯+a0xn=a01−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}
a1x+a1x2+⋯+a1xn=a1x1−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}
anxn=anxn1−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)=a01−x1+a1x1−x1+⋯+anxn1−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+a1x++⋯+anxn+⋯)
B
(
x
)
=
1
1
−
x
A
(
x
)
B(x) = \cfrac{1}{1-x} A(x)
B(x)=1−x1A(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)
