IDEA激活码
文章目录
- 一、生成函数性质总结
- 二、生成函数与序列的对应
参考博客 :
- 【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
- 【组合数学】生成函数 ( 线性性质 | 乘积性质 )
- 【组合数学】生成函数 ( 移位性质 )
- 【组合数学】生成函数 ( 求和性质 )
- 【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )
一、生成函数性质总结
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)
加法 :
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)
2 . 生成函数移位性质 :
向后移位 :
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)
向前移位 :
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
3 . 生成函数 乘积性质 :
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)
生成函数求和性质 :
向前求和 :
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)
向后求和 :
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)
4 . 生成函数换元性质 :
b
n
=
α
n
a
n
b_n = \alpha^n a_n
bn=αnan , 则
B
(
x
)
=
A
(
α
x
)
B(x) =A( \alpha x)
B(x)=A(αx)
5 . 生成函数求导性质 :
b
n
=
n
a
n
b_n = n a_n
bn=nan , 则
B
(
x
)
=
x
A
′
(
x
)
B(x) =xA'( x)
B(x)=xA′(x)
6 . 生成函数积分性质 :
b
n
=
a
n
n
+
1
b_n = \cfrac{a_n}{n+1}
bn=n+1an , 则
B
(
x
)
=
1
x
∫
0
x
A
(
x
)
d
x
B(x) =\cfrac{1}{x} \int^{x}_{0} A( x)dx
B(x)=x1∫0xA(x)dx
二、生成函数与序列的对应
给定序列
{
a
n
}
\{a_n\}
{an} 或
a
n
a_n
an 的递推方程 , 求生成函数
G
(
x
)
G(x)
G(x) , 需要使用级数的性质 和 一些重要的级数 ;
常用的生成函数取值 :
1
1
1 数列相关 :
{
a
n
}
\{a_n\}
{an} ,
a
n
=
1
n
a_n = 1^n
an=1n ;
A
(
x
)
=
∑
n
=
0
∞
x
n
=
1
1
−
x
\begin{aligned} A(x) & = \sum_{n=0}^{\infty} x^n = \frac{1}{1-x} \end{aligned}
A(x)=n=0∑∞xn=1−x1
{
a
n
}
\{a_n\}
{an} ,
a
n
=
(
−
1
)
n
a_n = (-1)^n
an=(−1)n ;
A
(
x
)
=
∑
n
=
0
∞
(
−
1
)
n
x
n
=
1
1
+
x
\begin{aligned} A(x) & = \sum_{n=0}^{\infty} (-1)^n x^n = \frac{1}{1+x} \end{aligned}
A(x)=n=0∑∞(−1)nxn=1+x1
{
a
n
}
\{a_n\}
{an} ,
a
n
=
k
n
a_n = k^n
an=kn ,
k
k
k 为正整数 ;
A
(
x
)
=
∑
n
=
0
∞
k
n
x
n
=
1
1
−
k
x
\begin{aligned} A(x) & = \sum_{n=0}^{\infty} k^n x^n = \frac{1}{1-kx} \end{aligned}
A(x)=n=0∑∞knxn=1−kx1
二项式系数相关 :
{
a
n
}
\{a_n\}
{an} ,
a
n
=
(
m
n
)
a_n = \dbinom{m}{n}
an=(nm) ;
A
(
x
)
=
∑
n
=
0
∞
(
m
n
)
x
n
=
(
1
+
x
)
m
\begin{aligned} A(x) & = \sum_{n=0}^{\infty} \dbinom{m}{n} x^n = ( 1 + x ) ^m \end{aligned}
A(x)=n=0∑∞(nm)xn=(1+x)m
组合数相关 :
{
a
n
}
\{a_n\}
{an} ,
a
n
=
(
m
+
n
−
1
n
)
a_n = \dbinom{m+n-1}{n}
an=(nm+n−1) ,
m
,
n
m,n
m,n 为正整数 ;
A
(
x
)
=
∑
n
=
0
∞
(
m
+
n
−
1
n
)
x
n
=
1
(
1
−
x
)
m
\begin{aligned} A(x) & = \sum_{n=0}^{\infty} \dbinom{m+n-1}{n} x^n = \frac{1}{{(1-x)}^m} \end{aligned}
A(x)=n=0∑∞(nm+n−1)xn=(1−x)m1
{
a
n
}
\{a_n\}
{an} ,
a
n
=
(
−
1
)
n
(
m
+
n
−
1
n
)
a_n = (-1)^n \dbinom{m+n-1}{n}
an=(−1)n(nm+n−1) ,
m
,
n
m,n
m,n 为正整数 ;
A
(
x
)
=
∑
n
=
0
∞
(
−
1
)
n
(
m
+
n
−
1
n
)
x
n
=
1
(
1
+
x
)
m
\begin{aligned} A(x) & = \sum_{n=0}^{\infty} (-1)^n \dbinom{m+n-1}{n} x^n = \frac{1}{{(1+x)}^m} \end{aligned}
A(x)=n=0∑∞(−1)n(nm+n−1)xn=(1+x)m1
{
a
n
}
\{a_n\}
{an} ,
a
n
=
(
n
+
1
n
)
a_n = \dbinom{n+1}{n}
an=(nn+1) ,
n
n
n 为正整数 ;
A
(
x
)
=
∑
n
=
0
∞
(
n
+
1
n
)
x
n
=
∑
n
=
0
∞
(
n
+
1
)
x
n
=
1
(
1
−
x
)
2
\begin{aligned} A(x) & = \sum_{n=0}^{\infty} \dbinom{n+1}{n} x^n \\ & = \sum_{n=0}^{\infty} (n+1) x^n \\ & = \frac{1}{{(1-x)}^2} \end{aligned}
A(x)=n=0∑∞(nn+1)xn=n=0∑∞(n+1)xn=(1−x)21
