参考博客 : 按照顺序看

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

一、指数生成函数求解多重集排列示例

使用 $1,2,3,4$ 四个数字组成五位数 , 要求
$1$ 出现次数不能超过 $2$ 次 , 但必须出现 ,
$2$ 出现次数不超过 $1$ 次 ,
$3$ 出现次数最多 $3$ 次 ,
$4$ 出现偶数次 ,
求上述五位数的个数 ;

这就是一个求解 多重集排列 的题目 , 使用 指数生成函数 ;

一共有 $5$ 个位置 , 使用 $1,2,3,4$ 向这 $5$ 个位置中填充 ,

选取个数分析 :

$1$ 出现不超过 $2$ 次 , 不能不出现 , 也就是必须大于 $0$ , 则可选取的个数是 $1,2$ ,

$2$ 出现不超过 $1$ 次 , 可选取个数 $0,1$ ,

$3$ 出现可以达到 $3$ 次 , 可选取的个数 $0,1,2,3$ ,

$4$ 出现偶数次 , 可选取个数是 $0,2,4,6,8,\cdots$ , 这里注意一共选择 $5$ 个 , 最终求解多重集时 , 主要是看 $x^5$ 前的次幂数 , 因此这里的 可选取个数就是单个因式中的 $x$ 次幂数 , 没必要超过 $5$ , 选择 $0,2,4$ 即可 ;

按照下面的模型 , 写出指数生成函数 ;

多重集 $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$ 系数就是多重集的排列数 ; ★

指数生成函数写法 :

① 确定生成函数项个数 : 多重集元素种类个数

② 确定生成函数项中的分项个数 : 选取值 个数 ;

③ 分项格式 : $\frac{x^n}{n!}$

④ 分项次幂 : 选取值 ;

总共有 $4$ 种元素 $1,2,3,4$ , 因此生成函数是 $4$ 个生成函数项相乘 ;

$1$ 元素对应的生成函数项 :

• 选取值 : $1,2$
• 最终结果 : $\frac{x^1}{1!}+\frac{x^2}{2!}=x+\frac{x^2}{2!}$

$2$ 元素对应的生成函数项 :

• 选取值 : $0,1$
• 最终结果 : $\frac{x^0}{0!}+\frac{x^1}{1!}=1+x$

$3$ 元素对应的生成函数项 :

• 选取值 : $0,1,2,3$
• 最终结果 : $\frac{x^0}{0!}+\frac{x^1}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}$

$4$ 元素对应的生成函数项 :

• 选取值 : $0,2,4,6,\cdots$ , 这里只选取 $5$ 个 , 求 $x$ 的次幂的 $5$ 前的系数 , 这里只需要选取到 $0,2,4$ 即可 , $5$ 以上的数完全不需要 , 可以忽略 ;
• 最终结果 : $\frac{x^0}{0!}+\frac{x^2}{2!}+\frac{x^4}{4!}=1+\frac{x^2}{2!}+\frac{x^4}{4!}$

将上述指数生成函数中四个 指数生成函数项相乘 , 计算出 $x^5$ 前的系数 , 就是多重集的排列数 ;

$G_e(x)=(x+\frac{x^2}{2!})(1+x)(1+x+\frac{x^2}{2!}+\frac{x^3}{3!})(1+\frac{x^2}{2!}+\frac{x^4}{4!})$

$=x+5\frac{x^2}{2!}+18\frac{x^3}{3!}+64\frac{x^4}{4!}+215\frac{x^5}{5!}\cdots$

后面的就不算了 , 其中 $x^5$ 的项是 $215\frac{x^5}{5!}$ , 因此题目中要求的 $5$ 位数的个数是 $215$ 个 ;

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/109384301