参考博客 :

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

一、正整数拆分

正整数拆分 涉及内容 :

• 拆分定义与分类
• 无序拆分
• 有序拆分

一个正整数可以 拆分成若干正整数 的和 , 每种不同的拆分方法 , 就可以 看做一个方案 ;

按照拆分顺序进行分类 : $4$ 拆分成 $1$ 和 $3$ , $4$ 拆分成 $3$ 和 $1$ ;

• 有序拆分 : 上述 $2$ 个 正整数拆分 , 是 两种不同的拆分方法 ;
• 无序拆分 : 上述 $2$ 个 正整数拆分 , 是 同一种拆分方法 ;

按照是否重复进行分类 :

• 允许重复 : 拆分时 , 允许拆分成若干个重复的正整数 , 如 $3$ 拆分成 $3$ 个 $1$ ;
• 不允许重复 : 拆分时 , 拆分的正整数 不允许重复 , 如 $3$ 拆分成 $3$ 个 $1$ 是错误的 , 只能拆分成 $1,2$ ;

正整数拆分可以按照性质 , 分为 $4$ 类 ;

• 有序重复
• 有序不重复
• 无序重复
• 无序不重复

二、无序拆分

无序拆分基本模型 :

将 正整数 $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$ ; 相当于 带限制条件 , 带系数 的 不定方程非负整数解 的情况 ;

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

1、无序拆分 不允许重复

讨论 无序拆分 , 不允许重复的情况 , 该方式 等价于 带限制条件 , 带系数 的 不定方程非负整数解 的情况 ;

$a_1$ 项对应的生成函数项 , $x_1$ 取值 $0,1$ , 则对应的生成函数项是 $(y^{a_1}{)}^0+(y^{a_1}{)}^1=1+y^{a_1}$

$a_2$ 项对应的生成函数项 , $x_2$ 取值 $0,1$ , 则对应的生成函数项是 $(y^{a_2}{)}^0+(y^{a_2}{)}^1=1+y^{a_2}$

$⋮$

$a_n$ 项对应的生成函数项 , $x_n$ 取值 $0,1$ , 则对应的生成函数项是 $(y^{a_n}{)}^0+(y^{a_n}{)}^1=1+y^{a_n}$

将上述生成函数项相乘 , 则可得到完整生成函数 :

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

将上述生成函数写好之后 , 计算 展开 , $y$ 的 $N$ 次幂的系数 , 就是 正整数 $N$ 的拆分方案数 ;

2、无序拆分 允许重复

讨论 无序拆分 , 允许重复的情况 , 该方式 等价于 不带限制条件 , 带系数 的 不定方程非负整数解 的情况 ;

$a_1$ 项对应的生成函数项 , $x_1$ 取值 $0,1,\cdots$ , 则对应的生成函数项是 $(y^{a_1}{)}^0+(y^{a_1}{)}^1+(y^{a_1}{)}^2=1+y^{a_1}+y^{2a_1}\cdots$

$a_2$ 项对应的生成函数项 , $x_2$ 取值 $0,1,\cdots$ , 则对应的生成函数项是 $(y^{a_2}{)}^0+(y^{a_2}{)}^1+(y^{a_2}{)}^2=1+y^{a_2}+y^{2a_2}\cdots$

$⋮$

$a_n$ 项对应的生成函数项 , $x_n$ 取值 $0,1,\cdots$ , 则对应的生成函数项是 $(y^{a_n}{)}^0+(y^{a_n}{)}^1+(y^{a_n}{)}^2=1+y^{a_n}+y^{2a_n}\cdots$

将上述生成函数项相乘 , 则可得到完整生成函数 :

$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 )$

上述生成函数可以根据 如下生成函数的常用取值 :

$\{a_n\}$ , $a_n=1^n$ ; A ( x ) = ∑ n = 0 ∞ x n = 1 1 − x

将 $1+y^{a_1}+y^{2a_1}\cdots$ 中的 $y^{a_1}$ 换元成 $x$ , 则可得到

$1+x+x^2+x^3+\cdots$

对应的数列是 $1^n$

则上述 $1+y^{a_1}+y^{2a_1}\cdots =\frac{1}{1-y^{a_1}}$

最终化简结果 :

$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 )$

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

将上述生成函数写好之后 , 计算 展开 , $y$ 的 $N$ 次幂的系数 , 就是 正整数 $N$ 的拆分方案数 ;

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

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