IDEA激活码
文章目录
- 一、指数生成函数
- 二、排列数指数生成函数 = 组合数普通生成函数
- 三、指数生成函数示例
参考博客 : 按照顺序看
- 【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
- 【组合数学】生成函数 ( 线性性质 | 乘积性质 )
- 【组合数学】生成函数 ( 移位性质 )
- 【组合数学】生成函数 ( 求和性质 )
- 【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )
- 【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★
- 【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 )
- 【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )
- 【组合数学】生成函数 ( 使用生成函数求解多重集 r 组合数 )
- 【组合数学】生成函数 ( 使用生成函数求解不定方程解个数 )
- 【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 )
- 【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 2 | 扩展到整数解 )
- 【组合数学】生成函数 ( 正整数拆分 | 无序 | 有序 | 允许重复 | 不允许重复 | 无序不重复拆分 | 无序重复拆分 )
- 【组合数学】生成函数 ( 正整数拆分 | 无序不重复拆分示例 )
- 【组合数学】生成函数 ( 正整数拆分 | 正整数拆分基本模型 | 有限制条件的无序拆分 )
- 【组合数学】生成函数 ( 正整数拆分 | 重复有序拆分 | 不重复有序拆分 | 重复有序拆分方案数证明 )
一、指数生成函数
多重集的 组合数 , 使用 生成函数 进行计算 ;
多重集的 排列数 , 使用 指数生成函数 进行计算 ;
序列
{
a
n
}
\{ a_n \}
{an} , 其通项公式是
a
n
a_n
an ,
{
a
n
}
\{ a_n \}
{an} 的 一般生成函数是
G
(
x
)
=
∑
n
=
0
∞
a
n
x
n
G(x) = \sum\limits_{n=0}^{\infty}a_n x^n
G(x)=n=0∑∞anxn ,
{
a
n
}
\{ a_n \}
{an} 的 指数生成函数是
G
e
(
x
)
=
∑
n
=
0
∞
a
n
x
n
n
!
G_e(x) = \sum\limits_{n=0}^{\infty}a_n \cfrac{x^n}{n!}
Ge(x)=n=0∑∞ann!xn
\ \ \ \,
★ ( 重点公式 )
{
a
n
}
\{ a_n \}
{an} 的 指数生成函数 是在一般生成函数的基础上 除以了
n
!
n!
n! ;
二、排列数指数生成函数 = 组合数普通生成函数
排列数 :
P
(
n
,
r
)
=
n
!
(
n
−
r
)
!
P(n,r) = \cfrac{n!}{(n-r)!}
P(n,r)=(n−r)!n! ,
n
n
n 个元素中取
r
r
r 个元素 , 不允许重复的排列数 ;
组合数 :
C
(
n
,
r
)
=
n
!
r
!
(
n
−
r
)
!
C(n,r) = \cfrac{n!}{r!(n-r)!}
C(n,r)=r!(n−r)!n! ,
n
n
n 个元素中取
r
r
r 个元素 , 不允许重复的组合数 ;
组合数对应的生成函数 是
G
(
x
)
=
∑
n
=
0
∞
(
m
n
)
x
n
G(x) = \sum\limits_{n=0}^{\infty}\dbinom{m}{n} x^n
G(x)=n=0∑∞(nm)xn , 收敛后是
(
1
+
x
)
n
(1+x)^n
(1+x)n
排列数对应的生成函数 是
G
(
x
)
=
∑
n
=
0
∞
P
(
m
,
n
)
x
n
G(x) = \sum\limits_{n=0}^{\infty}P(m, n) x^n
G(x)=n=0∑∞P(m,n)xn , 根据
n
!
C
(
m
,
n
)
=
P
(
m
,
n
)
n! C(m,n) = P(m, n)
n!C(m,n)=P(m,n) , 该排列数的生成函数 , 每一项都除以
n
!
n!
n! , 就可以得到对应的组合数的生成函数 ;
排列计数对应的指数生成函数 是
G
e
(
x
)
=
∑
n
=
0
∞
P
(
m
,
n
)
x
n
n
!
G_e(x) = \sum\limits_{n=0}^{\infty}P(m, n) \cfrac{x^n}{n!}
Ge(x)=n=0∑∞P(m,n)n!xn , 根据 根据
C
(
m
,
n
)
=
P
(
m
,
n
)
n
!
C(m,n) =\cfrac{ P(m, n)}{n!}
C(m,n)=n!P(m,n) , 可以得出如下结论 :
排列计数的指数生成函数
=
=
= 组合计数的普通生成函数
三、指数生成函数示例
数列
b
n
=
1
b_n=1
bn=1 , 求
{
b
n
}
\{ b_n \}
{bn} 的指数生成函数 ;
数列是
{
1
,
1
,
1
,
⋯
}
\{1, 1 ,1 , \cdots\}
{1,1,1,⋯}
普通生成函数
G
(
x
)
=
1
+
x
+
x
2
+
⋯
=
∑
n
=
0
∞
x
n
G(x) = 1 + x + x^2 + \cdots = \sum\limits_{n=0}^{\infty}x^n
G(x)=1+x+x2+⋯=n=0∑∞xn
指数生成函数
G
e
(
x
)
=
∑
n
=
0
∞
x
n
n
!
=
e
x
G_e(x) = \sum\limits_{n=0}^{\infty}\cfrac{x^n}{n!}=e^x
Ge(x)=n=0∑∞n!xn=ex
