IDEA激活码
文章目录
- 一、生成函数移位性质 1 ( 向后移位 )
- 二、生成函数移位性质 2 ( 向前移位 )
参考博客 :
- 【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
- 【组合数学】生成函数 ( 线性性质 | 乘积性质 )
一、生成函数移位性质 1 ( 向后移位 )
生成函数移位性质 1 ( 向后移位 ) :
b
(
n
)
=
{
0
,
n
<
l
a
n
−
l
,
n
≥
l
b(n) = \begin{cases} 0, & n < l \\\\ a_{n-l}, & n \geq l \end{cases}
b(n)=⎩⎪⎨⎪⎧0,an−l,n<ln≥l , 则
B
(
x
)
=
x
l
A
(
x
)
B(x) = x^l A(x)
B(x)=xlA(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
n
,
⋯
}
a_n = \{a_0, a_1 , \cdots , a_n , \cdots\}
an={a0,a1,⋯,an,⋯} , 生成函数为
A
(
x
)
A(x)
A(x) ;
数列
b
n
b_n
bn 与
a
n
a_n
an 的关系是 ,
b
n
b_n
bn 在
a
n
a_n
an 的前面增加了
l
l
l 个
0
0
0 ;
数列
a
n
a_n
an :
a
0
,
a
1
,
⋯
,
a
n
,
⋯
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ a_0, a_1 , \cdots , a_n , \cdots
a0,a1,⋯,an,⋯
数列
b
n
b_n
bn :
0
,
0
,
⋯
,
0
⏟
l
个
0
,
\begin{matrix} \underbrace{ 0, 0, \cdots , 0 } \\ l 个 0 \end{matrix} ,
0,0,⋯,0l个0,
a
0
,
a
1
,
⋯
,
a
n
,
⋯
a_0, a_1 , \cdots , a_n , \cdots
a0,a1,⋯,an,⋯
数列
b
n
b_n
bn 的生成函数 , 前
l
l
l 项的系数都是
0
0
0 , 所以可以省略 ,
- 第
l
l
l 项 ,B
(
x
)
B(x)
B(x) 的生成函数项是a
0
x
l
a_0x^l
a0xl , 对应的A
(
x
)
A(x)
A(x) 中的生成函数项是a
0
a_0
a0 - 第
l
+
1
l+1
l+1 项 ,B
(
x
)
B(x)
B(x) 的生成函数项是a
1
x
l
+
1
a_1x^{l+1}
a1xl+1 , 对应的A
(
x
)
A(x)
A(x) 中的生成函数项是a
1
x
a_1x
a1x
B
(
x
)
B(x)
B(x) 生成函数 中每项只是在 数列
a
n
a_n
an 的 生成函数
A
(
x
)
A(x)
A(x) 每项的基础上 , 乘以
x
l
x^l
xl 即可 ;
二、生成函数移位性质 2 ( 向前移位 )
生成函数移位性质 2 ( 向前移位 ) :
b
n
=
a
n
+
1
b_n = a_{n+1}
bn=an+1 , 则
B
(
x
)
=
A
(
x
)
−
∑
n
=
0
l
−
1
a
n
x
n
x
l
B(x) = \cfrac{A(x) - \sum\limits_{n=0}^{l-1} a_nx^n }{x^l}
B(x)=xlA(x)−n=0∑l−1anxn
由 已知数列
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
n
,
⋯
}
a_n = \{a_0, a_1 , \cdots , a_n , \cdots\}
an={a0,a1,⋯,an,⋯} , 生成函数为
A
(
x
)
A(x)
A(x) ;
数列
b
n
b_n
bn 与
a
n
a_n
an 的关系是 ,
b
n
b_n
bn 在
a
n
a_n
an 的基础上向后移动了
l
l
l 位 ,
b
0
b_0
b0 与
a
l
a_l
al 值相同 ,
b
1
b_1
b1 与
a
l
+
1
a_{l+1}
al+1 值相同 ;
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \,
数列
a
n
a_n
an :
a
0
,
a
1
,
⋯
,
a
l
,
a
l
+
1
⋯
a_0, a_1 , \cdots , a_l , a_{l+1} \cdots
a0,a1,⋯,al,al+1⋯
数列
b
n
b_n
bn :
b
0
,
b
1
,
⋯
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ b_0 , b_1 , \cdots
b0,b1,⋯
根据
A
(
x
)
A(x)
A(x) 求
B
(
x
)
B(x)
B(x) :
在
A
(
x
)
A(x)
A(x) 的基础上 , 减去前
l
l
l 项 , 即 从
0
0
0 到
l
−
1
l-1
l−1 项 ,
a
0
,
a
1
x
,
a
2
x
2
,
⋯
a
l
−
1
x
l
−
1
a_0 , a_1x , a_2x^2 , \cdots a_{l-1}x^{l-1}
a0,a1x,a2x2,⋯al−1xl−1 , 因此有了
A
(
x
)
−
∑
n
=
0
l
−
1
a
n
x
n
A(x) - \sum\limits_{n=0}^{l-1} a_nx^n
A(x)−n=0∑l−1anxn ;
A
(
x
)
A(x)
A(x) 生成函数 的 剩余的项 , 每一项都比
B
(
x
)
B(x)
B(x) 多
x
l
x^l
xl 倍 , 除以
x
l
x^l
xl 即可 ;
在上述
A
(
x
)
−
∑
n
=
0
l
−
1
a
n
x
n
A(x) - \sum\limits_{n=0}^{l-1} a_nx^n
A(x)−n=0∑l−1anxn 基础上 , 除以
x
l
x^l
xl , 得到
B
(
x
)
=
A
(
x
)
−
∑
n
=
0
l
−
1
a
n
x
n
x
l
B(x) = \cfrac{A(x) - \sum\limits_{n=0}^{l-1} a_nx^n }{x^l}
B(x)=xlA(x)−n=0∑l−1anxn ;
