IDEA激活码
文章目录
- 一、证明指数生成函数求解多重集排列
参考博客 : 按照顺序看
- 【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
- 【组合数学】生成函数 ( 线性性质 | 乘积性质 )
- 【组合数学】生成函数 ( 移位性质 )
- 【组合数学】生成函数 ( 求和性质 )
- 【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )
- 【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★
- 【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 )
- 【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )
- 【组合数学】生成函数 ( 使用生成函数求解多重集 r 组合数 )
- 【组合数学】生成函数 ( 使用生成函数求解不定方程解个数 )
- 【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 )
- 【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 2 | 扩展到整数解 )
- 【组合数学】生成函数 ( 正整数拆分 | 无序 | 有序 | 允许重复 | 不允许重复 | 无序不重复拆分 | 无序重复拆分 )
- 【组合数学】生成函数 ( 正整数拆分 | 无序不重复拆分示例 )
- 【组合数学】生成函数 ( 正整数拆分 | 正整数拆分基本模型 | 有限制条件的无序拆分 )
- 【组合数学】生成函数 ( 正整数拆分 | 重复有序拆分 | 不重复有序拆分 | 重复有序拆分方案数证明 )
- 【组合数学】指数生成函数 ( 指数生成函数概念 | 排列数指数生成函数 = 组合数普通生成函数 | 指数生成函数示例 )
一、证明指数生成函数求解多重集排列
多重集
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) 展开 , 其中的
r
r
r 系数就是多重集的排列数 ; ★
证明上述指数生成函数用途 :
将上述 指数生成函数 展开 ,
指数生成函数项
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) , 由
k
k
k 个因式相乘得到 ,
每个因式都会提供一个
x
m
1
m
1
!
\cfrac{x^{m_1}}{m_1!}
m1!xm1 成分 ,
x
m
1
m
1
!
\cfrac{x^{m_1}}{m_1!}
m1!xm1 来自第一个因式 ,
x
m
2
m
2
!
\cfrac{x^{m_2}}{m_2!}
m2!xm2 来自第二个因式 ,
⋮
\vdots
⋮
x
m
k
m
k
!
\cfrac{x^{m_k}}{m_k!}
mk!xmk 来自第
k
k
k 个因式 ,
上述因式相乘
x
m
1
m
1
!
⋅
x
m
2
m
2
!
⋯
x
m
k
m
k
!
\cfrac{x^{m_1}}{m_1!} \cdot \cfrac{x^{m_2}}{m_2!} \cdots \cfrac{x^{m_k}}{m_k!}
m1!xm1⋅m2!xm2⋯mk!xmk
其中
m
1
+
m
2
+
⋯
+
m
r
=
r
,
m_1 + m_2 + \cdots + m_r = r \ \ \ ,
m1+m2+⋯+mr=r ,
0
≤
m
i
≤
n
i
,
0 \leq m_i \leq n_i \ \ ,
0≤mi≤ni ,
i
=
0
,
1
,
2
,
⋯
,
k
i= 0,1,2, \cdots , k
i=0,1,2,⋯,k
x
m
1
m
1
!
⋅
x
m
2
m
2
!
⋯
x
m
k
m
k
!
\cfrac{x^{m_1}}{m_1!} \cdot \cfrac{x^{m_2}}{m_2!} \cdots \cfrac{x^{m_k}}{m_k!}
m1!xm1⋅m2!xm2⋯mk!xmk 对应了指数生成函数展开后的分项 ;
x
m
1
m
1
!
⋅
x
m
2
m
2
!
⋯
x
m
k
m
k
!
\ \ \ \ \cfrac{x^{m_1}}{m_1!} \cdot \cfrac{x^{m_2}}{m_2!} \cdots \cfrac{x^{m_k}}{m_k!}
m1!xm1⋅m2!xm2⋯mk!xmk
=
x
m
1
+
m
2
+
⋯
+
m
k
m
1
!
m
2
!
⋯
m
k
!
=\cfrac{x^{m_1 + m_2 + \cdots + m_k}}{m_1!m_2!\cdots m_k!}
=m1!m2!⋯mk!xm1+m2+⋯+mk
=
x
r
m
1
!
m
2
!
⋯
m
k
!
⋅
r
!
r
!
=\cfrac{x^{r}}{m_1!m_2!\cdots m_k!} \cdot \cfrac{r!}{r!}
=m1!m2!⋯mk!xr⋅r!r!
=
x
r
r
!
⋅
r
!
m
1
!
m
2
!
⋯
m
k
!
=\cfrac{x^{r}}{r!} \cdot \cfrac{r!}{m_1!m_2!\cdots m_k!}
=r!xr⋅m1!m2!⋯mk!r!
r
!
m
1
!
m
2
!
⋯
m
k
!
\cfrac{r!}{m_1!m_2!\cdots m_k!}
m1!m2!⋯mk!r! 是多重集
r
r
r 个元素的全排列数
选了
r
r
r 个元素 , 选择的方法数是
m
1
+
m
2
+
⋯
+
m
r
=
r
m_1 + m_2 + \cdots + m_r = r
m1+m2+⋯+mr=r 非负整数解个数 , 配置完成后 , 再 进行全排列 , 就可以得到
r
r
r 排列 ;
( 先选择 , 再进行全排列 )
a
r
=
∑
r
!
m
1
!
m
2
!
⋯
m
k
!
a_r = \sum\cfrac{r!}{m_1!m_2!\cdots m_k!}
ar=∑m1!m2!⋯mk!r!
上述求和 , 每个分项都是满足
m
1
+
m
2
+
⋯
+
m
r
=
r
m_1 + m_2 + \cdots + m_r = r
m1+m2+⋯+mr=r 方程的非负整数解 , 每个非负整数解都对应了多重集的
S
S
S 的
r
r
r 组合 ;
组合的全排列数是
r
!
m
1
!
m
2
!
⋯
m
k
!
\cfrac{r!}{m_1!m_2!\cdots m_k!}
m1!m2!⋯mk!r! ,
上述求和
a
r
=
∑
r
!
m
1
!
m
2
!
⋯
m
k
!
a_r = \sum\cfrac{r!}{m_1!m_2!\cdots m_k!}
ar=∑m1!m2!⋯mk!r! 是 针对所有满足方程的一切非负整数解进行求和 ;
