参考博客 :

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

一、正整数拆分基本模型

无序拆分基本模型 :

将 正整数 $N$ 无序拆分成正整数 , $a_1,a_2,\cdots ,a_n$ 是拆分后的 $n$ 个数 ,

该拆分是无序的 , 上述拆分的 $n$ 个数的个数可能是不一样的 ,

假设 $a_1$ 有 $x_1$ 个 , $a_2$ 有 $x_2$ 个 , $\cdots$ , $a_n$ 有 $x_n$ 个 , 那么有如下方程 :

$a_1{x}_1+a_2{x}_2+\cdots +a_n{x}_n=N$

这种形式可以使用 不定方程非负整数解个数 的生成函数计算 , 是 带系数 , 带限制条件的情况 , 参考 : 组合数学】生成函数 ( 使用生成函数求解不定方程解个数 )

无序拆分的情况下 , 拆分后的正整数 , 允许重复 和 不允许重复 , 是两类组合问题 ;

如果不允许重复 , 那么这些 $x_i$ 的取值 , 只能 取值 $0,1$ ; 相当于 带限制条件 , 带系数 的 不定方程非负整数解 的情况 ;

对应的生成函数是 : $G(x)=(1+y^{a_1})(1+y^{a_2})\cdots (1+y^{a_n})$

如果 允许重复 , 那么这些 $x_i$ 的取值 , 就是 自然数 ; 相当于 带系数 的 不定方程非负整数解 的情况 ;

对应的生成函数是 : $G(x)=(1+y^{a_1}+y^{2a_1}\cdots )(1+y^{a_2}+y^{2a_2}\cdots )\cdots (1+y^{a_n}+y^{2a_n}\cdots )$

或 $G(x)=\frac{1}{(1-y^{a_1})(1-y^{a_2})\cdots (1-y^{a_n})}$

二、有限制条件的无序拆分

将 正整数 $N$ 无序拆分成正整数 , $a_1,a_2,\cdots ,a_n$ 是拆分后的 $n$ 个数 ,

该拆分是无序的 , 上述拆分的 $n$ 个数的个数可能是不一样的 ,

假设 $a_1$ 有 $x_1$ 个 , $a_2$ 有 $x_2$ 个 , $\cdots$ , $a_n$ 有 $x_n$ 个 , 那么有如下方程 :

$a_1{x}_1+a_2{x}_2+\cdots +a_n{x}_n=N$

其中存在限制条件 , $a_i$ 的取值个数 $x_i$ 取值范围 做一下限制 , $l_i\le x_i\le t_i$

这种形式可以使用 不定方程非负整数解个数 的生成函数计算 , 是 带系数 , 带限制条件的情况 , 参考 : 组合数学】生成函数 ( 使用生成函数求解不定方程解个数 )

上述受限制条件下的无序拆分 , 就是完整的 带系数 , 带限制条件 的 不定方程非负整数解 的问题 ;

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

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