IDEA激活码
文章目录
- 一、指数生成函数性质
- 二、指数生成函数求解多重集排列
参考博客 : 按照顺序看
- 【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
- 【组合数学】生成函数 ( 线性性质 | 乘积性质 )
- 【组合数学】生成函数 ( 移位性质 )
- 【组合数学】生成函数 ( 求和性质 )
- 【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )
- 【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★
- 【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 )
- 【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )
- 【组合数学】生成函数 ( 使用生成函数求解多重集 r 组合数 )
- 【组合数学】生成函数 ( 使用生成函数求解不定方程解个数 )
- 【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 )
- 【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 2 | 扩展到整数解 )
- 【组合数学】生成函数 ( 正整数拆分 | 无序 | 有序 | 允许重复 | 不允许重复 | 无序不重复拆分 | 无序重复拆分 )
- 【组合数学】生成函数 ( 正整数拆分 | 无序不重复拆分示例 )
- 【组合数学】生成函数 ( 正整数拆分 | 正整数拆分基本模型 | 有限制条件的无序拆分 )
- 【组合数学】生成函数 ( 正整数拆分 | 重复有序拆分 | 不重复有序拆分 | 重复有序拆分方案数证明 )
- 【组合数学】指数生成函数 ( 指数生成函数概念 | 排列数指数生成函数 = 组合数普通生成函数 | 指数生成函数示例 )
一、指数生成函数性质
两个数列
{
a
n
}
,
{
b
n
}
\{a_n\} , \{b_n\}
{an},{bn} 对应的指数生成函数分别是
A
e
(
x
)
,
B
e
(
x
)
A_e(x) , B_e(x)
Ae(x),Be(x) ,
将上述两个 指数生成函数 相乘 , 看做一个函数 , 可以展开成另外一个数列的级数形式 ,
A
e
(
x
)
⋅
B
e
(
x
)
=
∑
n
=
0
∞
c
n
x
n
n
!
A_e(x) \cdot B_e(x) = \sum\limits_{n=0}^{\infty} c_n \cfrac{x^n}{n!}
Ae(x)⋅Be(x)=n=0∑∞cnn!xn
其中 ,
c
n
=
∑
k
=
0
∞
(
n
k
)
a
k
b
n
−
k
c_n =\sum\limits_{k=0}^{\infty}\dbinom{n}{k}a_kb_{n-k}
cn=k=0∑∞(kn)akbn−k
( 代入即可求出该结果 )
二、指数生成函数求解多重集排列
多重集
S
=
{
n
1
⋅
a
1
,
n
2
⋅
a
2
,
⋯
,
n
k
⋅
a
k
}
S=\{ n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k \}
S={n1⋅a1,n2⋅a2,⋯,nk⋅ak}
多重集
S
S
S 的
r
r
r 排列数 组成数列
{
a
r
}
\{ a_r \}
{ar} , 对应的指数生成函数是 :
G
e
(
x
)
=
f
n
1
(
x
)
f
n
2
(
x
)
⋯
f
n
k
(
x
)
G_e(x) = f_{n_1}(x) f_{n_2}(x) \cdots f_{n_k}(x)
Ge(x)=fn1(x)fn2(x)⋯fnk(x) ★
其中每个生成函数项
f
n
i
(
x
)
f_{n_i}(x)
fni(x) 是
f
n
i
(
x
)
=
1
+
x
+
x
2
2
!
+
⋯
+
x
n
i
n
i
!
f_{n_i}(x) = 1 + x + \cfrac{x^2}{2!} + \cdots + \cfrac{x^{n_i}}{n_i!}
fni(x)=1+x+2!x2+⋯+ni!xni ★
将
G
e
(
x
)
G_e(x)
Ge(x) 展开 , 其中的
x
r
r
!
\cfrac{x^r}{r!}
r!xr 的系数就是多重集的排列数 , 特别注意如果不是
x
r
r
!
\cfrac{x^r}{r!}
r!xr 形式 , 需要强制转化成上述性质 , 一定要除以
r
!
r!
r! ; ★★★★★
选取问题参考 :
n
n
n 元集
S
S
S , 从
S
S
S 集合中选取
r
r
r 个元素 ;
根据 元素是否允许重复 , 选取过程是否有序 , 将选取问题分为四个子类型 :
| 元素不重复 | 元素可以重复 | |
|---|---|---|
| 有序选取 | 集合排列
P ( n , r ) P(n,r) P(n,r) |
多重集排列 |
| 无序选取 | 集合组合
C ( n , r ) C(n,r) C(n,r) |
多重集组合 |
选取问题中 :
- 不可重复的元素 , 有序的选取 , 对应 集合的排列 ;
P
(
n
,
r
)
=
n
!
(
n
−
r
)
!
P(n,r) = \dfrac{n!}{(n-r)!}
P(n,r)=(n−r)!n! - 不可重复的元素 , 无序的选取 , 对应 集合的组合 ;
C
(
n
,
r
)
=
P
(
n
,
r
)
r
!
=
n
!
r
!
(
n
−
r
)
!
C(n,r) = \dfrac{P(n,r)}{r!} = \dfrac{n!}{r!(n-r)!}
C(n,r)=r!P(n,r)=r!(n−r)!n! - 可重复的元素 , 有序的选取 , 对应 多重集的排列 ;
全
排
列
=
n
!
n
1
!
n
2
!
⋯
n
k
!
全排列 = \cfrac{n!}{n_1! n_2! \cdots n_k!}
全排列=n1!n2!⋯nk!n! , 非全排列k
r
,
r
≤
n
i
k^r , \ \ r\leq n_i
kr, r≤ni - 可重复的元素 , 无序的选取 , 对应 多重集的组合 ;
N
=
C
(
k
+
r
−
1
,
r
)
N= C(k + r - 1, r)
N=C(k+r−1,r)
