【组合数学】生成函数 ( 正整数拆分 | 无序 | 有序 | 允许重复 | 不允许重复 | 无序不重复拆分 | 无序重复拆分 )

参考博客 :

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

一、正整数拆分

正整数拆分 涉及内容 :

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

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

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

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

按照是否重复进行分类 :

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

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

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

二、无序拆分

无序拆分基本模型 :

将 正整数 N N N 无序拆分成正整数 , a 1 , a 2 , ⋯   , a n a_1, a_2, \cdots , a_n a1​,a2​,⋯,an​ 是拆分后的 n n n 个数 ,

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

假设 a 1 a_1 a1​ 有 x 1 x_1 x1​ 个 , a 2 a_2 a2​ 有 x 2 x_2 x2​ 个 , ⋯ \cdots ⋯ , a n a_n an​ 有 x n x_n xn​ 个 , 那么有如下方程 :

a 1 x 1 + a 2 x 2 + ⋯ + a n x n = N a_1x_1 + a_2x_2 + \cdots + a_nx_n = N a1​x1​+a2​x2​+⋯+an​xn​=N

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

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

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

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

1、无序拆分 不允许重复

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

a 1 a_1 a1​ 项对应的生成函数项 , x 1 x_1 x1​ 取值 0 , 1 0,1 0,1 , 则对应的生成函数项是 ( y a 1 ) 0 + ( y a 1 ) 1 = 1 + y a 1 (y^{a_1})^{0} + (y^{a_1})^{1}= 1+ y^{a_1} (ya1​)0+(ya1​)1=1+ya1​

a 2 a_2 a2​ 项对应的生成函数项 , x 2 x_2 x2​ 取值 0 , 1 0,1 0,1 , 则对应的生成函数项是 ( y a 2 ) 0 + ( y a 2 ) 1 = 1 + y a 2 (y^{a_2})^{0} + (y^{a_2})^{1}= 1+ y^{a_2} (ya2​)0+(ya2​)1=1+ya2​

⋮ \vdots ⋮

a n a_n an​ 项对应的生成函数项 , x n x_n xn​ 取值 0 , 1 0,1 0,1 , 则对应的生成函数项是 ( y a n ) 0 + ( y a n ) 1 = 1 + y a n (y^{a_n})^{0} + (y^{a_n})^{1}= 1+ y^{a_n} (yan​)0+(yan​)1=1+yan​

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

G ( x ) = ( 1 + y a 1 ) ( 1 + y a 2 ) ⋯ ( 1 + y a n ) G(x) = (1+ y^{a_1}) (1+ y^{a_2}) \cdots (1+ y^{a_n}) G(x)=(1+ya1​)(1+ya2​)⋯(1+yan​)

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

2、无序拆分 允许重复

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

a 1 a_1 a1​ 项对应的生成函数项 , x 1 x_1 x1​ 取值 0 , 1 , ⋯ 0,1, \cdots 0,1,⋯ , 则对应的生成函数项是 ( y a 1 ) 0 + ( y a 1 ) 1 + ( y a 1 ) 2 = 1 + y a 1 + y 2 a 1 ⋯ (y^{a_1})^{0} + (y^{a_1})^{1} + (y^{a_1})^{2}= 1+ y^{a_1} + y^{2a_1}\cdots (ya1​)0+(ya1​)1+(ya1​)2=1+ya1​+y2a1​⋯

a 2 a_2 a2​ 项对应的生成函数项 , x 2 x_2 x2​ 取值 0 , 1 , ⋯ 0,1, \cdots 0,1,⋯ , 则对应的生成函数项是 ( y a 2 ) 0 + ( y a 2 ) 1 + ( y a 2 ) 2 = 1 + y a 2 + y 2 a 2 ⋯ (y^{a_2})^{0} + (y^{a_2})^{1} + (y^{a_2})^{2}= 1+ y^{a_2} + y^{2a_2}\cdots (ya2​)0+(ya2​)1+(ya2​)2=1+ya2​+y2a2​⋯

⋮ \vdots ⋮

a n a_n an​ 项对应的生成函数项 , x n x_n xn​ 取值 0 , 1 , ⋯ 0,1, \cdots 0,1,⋯ , 则对应的生成函数项是 ( y a n ) 0 + ( y a n ) 1 + ( y a n ) 2 = 1 + y a n + y 2 a n ⋯ (y^{a_n})^{0} + (y^{a_n})^{1} + (y^{a_n})^{2}= 1+ y^{a_n} + y^{2a_n}\cdots (yan​)0+(yan​)1+(yan​)2=1+yan​+y2an​⋯

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

G ( x ) = ( 1 + y a 1 + y 2 a 1 ⋯   ) ( 1 + y a 2 + y 2 a 2 ⋯   ) ⋯ ( 1 + y a n + y 2 a n ⋯   ) 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)=(1+ya1​+y2a1​⋯)(1+ya2​+y2a2​⋯)⋯(1+yan​+y2an​⋯)

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

{ a n } \{a_n\} {an​} , a n = 1 n a_n = 1^n an​=1n ; A ( x ) = ∑ n = 0 ∞ x n = 1 1 − x \begin{aligned} A(x) & = \sum_{n=0}^{\infty} x^n = \frac{1}{1-x} \end{aligned} A(x)​=n=0∑∞​xn=1−x1​​

将 1 + y a 1 + y 2 a 1 ⋯ 1+ y^{a_1}+ y^{2a_1}\cdots 1+ya1​+y2a1​⋯ 中的 y a 1 y^{a_1} ya1​ 换元成 x x x , 则可得到

1 + x + x 2 + x 3 + ⋯ 1 + x + x^2 + x^3 + \cdots 1+x+x2+x3+⋯

对应的数列是 1 n 1^n 1n

则上述 1 + y a 1 + y 2 a 1 ⋯ = 1 1 − y a 1 1+ y^{a_1}+ y^{2a_1}\cdots =\cfrac{1}{1-y^{a_1}} 1+ya1​+y2a1​⋯=1−ya1​1​

最终化简结果 :

G ( x ) = ( 1 + y a 1 + y 2 a 1 ⋯   ) ( 1 + y a 2 + y 2 a 2 ⋯   ) ⋯ ( 1 + y a n + y 2 a n ⋯   ) 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)=(1+ya1​+y2a1​⋯)(1+ya2​+y2a2​⋯)⋯(1+yan​+y2an​⋯)

           = 1 ( 1 − y a 1 ) ( 1 − y a 2 ) ⋯ ( 1 − y a n ) \ \ \ \ \ \ \ \ \ \ =\cfrac{1}{ (1-y^{a_1}) (1-y^{a_2}) \cdots (1-y^{a_n}) }           =(1−ya1​)(1−ya2​)⋯(1−yan​)1​

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