文章目录

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

参考博客 : 按照顺序看

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

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

---

多重集 $S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots ,n_k\cdot a_k\}$

多重集 $S$ 的 $r$ 排列数 组成数列 $\{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+\frac{x^2}{2!}+\cdots +\frac{x^{n_i}}{n_i!}$ ★

将 $G_e(x)$ 展开 , 其中的 $r$ 系数就是多重集的排列数 ; ★

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

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

指数生成函数项 $G_e(x)=f_{n_1}(x)f_{n_2}(x)\cdots f_{n_k}(x)$ , 由 $k$ 个因式相乘得到 ,

每个因式都会提供一个 $\frac{x^{m_1}}{m_1!}$ 成分 ,

$\frac{x^{m_1}}{m_1!}$ 来自第一个因式 ,

$\frac{x^{m_2}}{m_2!}$ 来自第二个因式 ,

$⋮$

$\frac{x^{m_k}}{m_k!}$ 来自第 $k$ 个因式 ,

上述因式相乘 $\frac{x^{m_1}}{m_1!}\cdot \frac{x^{m_2}}{m_2!}\cdots \frac{x^{m_k}}{m_k!}$

其中 $m_1+m_2+\cdots +m_r=r,$

$0\le m_i\le n_i,$ $i=0,1,2,\cdots ,k$

$\frac{x^{m_1}}{m_1!}\cdot \frac{x^{m_2}}{m_2!}\cdots \frac{x^{m_k}}{m_k!}$ 对应了指数生成函数展开后的分项 ;

$\frac{x^{m_1}}{m_1!}\cdot \frac{x^{m_2}}{m_2!}\cdots \frac{x^{m_k}}{m_k!}$

$=\frac{x^{m_1+m_2+\cdots +m_k}}{m_1!m_2!\cdots m_k!}$

$=\frac{x^r}{m_1!m_2!\cdots m_k!}\cdot \frac{r!}{r!}$

$=\frac{x^r}{r!}\cdot \frac{r!}{m_1!m_2!\cdots m_k!}$

$\frac{r!}{m_1!m_2!\cdots m_k!}$ 是多重集 $r$ 个元素的全排列数

选了 $r$ 个元素 , 选择的方法数是 $m_1+m_2+\cdots +m_r=r$ 非负整数解个数 , 配置完成后 , 再 进行全排列 , 就可以得到 $r$ 排列 ;

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

$a_r=\sum \frac{r!}{m_1!m_2!\cdots m_k!}$

上述求和 , 每个分项都是满足 $m_1+m_2+\cdots +m_r=r$ 方程的非负整数解 , 每个非负整数解都对应了多重集的 $S$ 的 $r$ 组合 ;

组合的全排列数是 $\frac{r!}{m_1!m_2!\cdots m_k!}$ ,

上述求和 $a_r=\sum \frac{r!}{m_1!m_2!\cdots m_k!}$ 是 针对所有满足方程的一切非负整数解进行求和 ;

总结

以上是生活随笔为你收集整理的【组合数学】指数生成函数 ( 证明指数生成函数求解多重集排列 )的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。