参考博客 :

• 【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
• 【组合数学】生成函数 ( 线性性质 | 乘积性质 )
• 【组合数学】生成函数 ( 移位性质 )
• 【组合数学】生成函数 ( 求和性质 )
• 【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )
• 【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★
• 【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 )
• 【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )

一、使用生成函数求解多重集 r 组合数

$S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots ,n_k\cdot a_k\}$ 是多重集 , 其含有 $k$ 个种类的元素 , $n_1,n_2,\cdots ,n_k$ 是每种元素的重复度 ,

该 多重集的 $r$ 组合数 , 是 不定方程 $x_1+x_2+\cdots +x_k=r$ 的非负整数解 , 前提是 $x_i\le n_i$ , 每个元素所取的个数 $x_i$ , 不能超过其重复度 $n_i$ ;

相当于 $a_1$ 取 $x_1$ 个 , $a_2$ 取 $x_2$ 个 , $\cdots$ , $a_k$ 取 $x_k$ 个 , 总共取 $r$ 个 ;

$n_i$ 是无穷个数时 , 多重集的 $r$ 组合数是 $C(k+r-1,r)$

回顾多重集排列组合 :

• 可重复的元素 , 有序的选取 , 对应 多重集的排列 ; $全排列=\frac{n!}{n_1!n_2!\cdots n_k!}$ , 非全排列 $k^r,r\le n_i$
• 可重复的元素 , 无序的选取 , 对应 多重集的组合 ; $N=C(k+r-1,r)$

上述的 多重集 $r$ 组合数 $C(k+r-1,r)$ 是在重复度不受限制的情况下的选取结果 , 如果重复度受限制 , 就需要使用生成函数进行计算 ;

如添加如下限制 : $a_1$ 最多能取 $3$ 个 , $a_2$ 最少取 $4$ 个 , 最多取 $10$ 个 ;

生成函数 :

$G(y)=$ $(1+y+\cdots +y^{n_1})$ $(1+y+\cdots +y^{n_2})$ $\cdots$ $(1+y+\cdots +y^{n_k})$

多重集中的每个元素的取值个数作为 $y$ 的次幂 , 如 $a_1$ 元素的取值个数是 $0$ 到 $n_1$ , 则该项对应的 生成函数项是 从 $y$ 的 $0$ 次幂 , 到 $y$ 的 $n_1$ 次幂 相加 ; 构成项 $(1+y+\cdots +y^{n_1})$ ;

将所有元素的上述 生成函数项 乘到一起 , 就构成上述生成函数 ;

按照多项式乘法 , 多重集中取 $r$ 个元素 ,

从第一个因式 $(1+y+\cdots +y^{n_1})$ 拿出 $y^{x_1}$ ,

从第二个因式 $(1+y+\cdots +y^{n_2})$ 拿出 $y^{x_2}$ ,

$⋮$

从第 $k$ 个因式 $(1+y+\cdots +y^{n_k})$ 拿出 $y^{x_k}$ ,

如果上述乘积 $y^{x_1}{y}^{x_2}\cdots y^{x_k}$ 的结果 是 $y^r$ , 即 $y^{x_1}{y}^{x_2}\cdots y^{x_k}=y^r$ , 相当于指数 $x_1+x_2+\cdots +x_k=r$ , 也就是不定方程的非负整数解 ;

二、使用生成函数求解多重集 r 组合数 示例

多重集 $S=\{3\cdot a,4\cdot b,5\cdot c\}$ , 求该多重集的 $10$ 组合数 ;

上述多重集元素的 重复度 $3,4,5$ 都不超过 $10$ ;

对应 $a$ 元素 , 其 重复度取值范围是 $0$ ~ $3$ , 对应的生成函数项是 $y^0+y^1+y^2+y^3$

对应 $b$ 元素 , 其 重复度取值范围是 $0$ ~ $4$ , 对应的生成函数项是 $y^0+y^1+y^2+y^3+y^4$

对应 $c$ 元素 , 其重 复度取值范围是 $0$ ~ $5$ , 对应的生成函数项是 $y^0+y^1+y^2+y^3+y^4+y^5$

将上述项相乘 , 得到完整的生成函数 ;

$G(x)=(y^0+y^1+y^2+y^3)(y^0+y^1+y^2+y^3+y^4)(y^0+y^1+y^2+y^3+y^4+y^5)$

$=(1+y^1+y^2+y^3)(1+y^1+y^2+y^3+y^4)(1+y^1+y^2+y^3+y^4+y^5)$

$=(1+2y^1+3y^2+4y^3+4y^4+3y^5+2y^6+y^7)(1+y^1+y^2+y^3+y^4+y^5)$

统计上述两项相乘 , $y$ 的次幂值为 $10$ 的项 :

第一个因式的 $3y^5$ 与第二个因式的 $y^5$ , 相乘为 $3y^{10}$

第一个因式的 $2y^6$ 与第二个因式的 $y^4$ , 相乘为 $2y^{10}$

第一个因式的 $y^7$ 与第二个因式的 $y^3$ , 相乘为 $y^{10}$

$y^{10}$ 项前的系数是 $3+2+1=6$

因此上述 多重集的 $10$ 组合 ,选择方案有 $6$ 种 ;

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

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