【组合数学】指数生成函数 ( 证明指数生成函数求解多重集排列 )

文章目录

一、证明指数生成函数求解多重集排列

参考博客 : 按照顺序看

【组合数学】生成函数简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
【组合数学】生成函数 ( 线性性质 | 乘积性质 )
【组合数学】生成函数 ( 移位性质 )
【组合数学】生成函数 ( 求和性质 )
【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )
【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★
【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 )
【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )
【组合数学】生成函数 ( 使用生成函数求解多重集 r 组合数 )
【组合数学】生成函数 ( 使用生成函数求解不定方程解个数 )
【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 )
【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 2 | 扩展到整数解 )
【组合数学】生成函数 ( 正整数拆分 | 无序 | 有序 | 允许重复 | 不允许重复 | 无序不重复拆分 | 无序重复拆分 )
【组合数学】生成函数 ( 正整数拆分 | 无序不重复拆分示例 )
【组合数学】生成函数 ( 正整数拆分 | 正整数拆分基本模型 | 有限制条件的无序拆分 )
【组合数学】生成函数 ( 正整数拆分 | 重复有序拆分 | 不重复有序拆分 | 重复有序拆分方案数证明 )
【组合数学】指数生成函数 ( 指数生成函数概念 | 排列数指数生成函数 = 组合数普通生成函数 | 指数生成函数示例 )

一、证明指数生成函数求解多重集排列

多重集

S={ n_1 cdot a_1 , n_2 cdot a_2 , cdots , n_k cdot a_k }

多重集

的

排列数组成数列

{ a_r }

, 对应的指数生成函数是 :

G_e(x) = f_{n_1}(x) f_{n_2}(x) cdots f_{n_k}(x)

★

其中每个生成函数项

f_{n_i}(x)

是

f_{n_i}(x) = 1 x cfrac{x^2}{2!} cdots cfrac{x^{n_i}}{n_i!}

★

将

G_e(x)

展开 , 其中的

系数就是多重集的排列数 ; ★

证明上述指数生成函数用途 :

将上述指数生成函数展开 ,

指数生成函数项

G_e(x) = f_{n_1}(x) f_{n_2}(x) cdots f_{n_k}(x)

, 由

个因式相乘得到 ,

每个因式都会提供一个

cfrac{x^{m_1}}{m_1!}

成分 ,

cfrac{x^{m_1}}{m_1!}

来自第一个因式 ,

cfrac{x^{m_2}}{m_2!}

来自第二个因式 ,

vdots

cfrac{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!}

其中

m_1 m_2 cdots m_r = r ,

0 leq m_i leq n_i ,

i= 0,1,2, cdots , k

cfrac{x^{m_1}}{m_1!} cdot cfrac{x^{m_2}}{m_2!} cdots cfrac{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!}

=cfrac{x^{m_1 m_2 cdots m_k}}{m_1!m_2!cdots m_k!}

=cfrac{x^{r}}{m_1!m_2!cdots m_k!} cdot cfrac{r!}{r!}

=cfrac{x^{r}}{r!} cdot cfrac{r!}{m_1!m_2!cdots m_k!}

cfrac{r!}{m_1!m_2!cdots m_k!}

是多重集

个元素的全排列数

选了

个元素 , 选择的方法数是

m_1 m_2 cdots m_r = r

非负整数解个数 , 配置完成后 , 再进行全排列 , 就可以得到

排列 ;

( 先选择 , 再进行全排列 )

a_r = sumcfrac{r!}{m_1!m_2!cdots m_k!}

上述求和 , 每个分项都是满足

m_1 m_2 cdots m_r = r

方程的非负整数解 , 每个非负整数解都对应了多重集的

的

组合 ;

组合的全排列数是

cfrac{r!}{m_1!m_2!cdots m_k!}

上述求和

a_r = sumcfrac{r!}{m_1!m_2!cdots m_k!}

是针对所有满足方程的一切非负整数解进行求和 ;

博客函数模型配置数学

0 人点赞