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

韩曙亮

发布于 2023-03-28 18:41:33

1.6K0

发布于 2023-03-28 18:41:33

文章被收录于专栏：韩曙亮的移动开发专栏

文章目录

参考博客 :

一、正整数拆分

正整数拆分涉及内容 :

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

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

按照拆分顺序进行分类 :

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_1x_1 + a_2x_2 + \cdots + a_nx_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}

\vdots

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

\vdots

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

;

\begin{aligned} A(x) & = \sum_{n=0}^{\infty} x^n = \frac{1}{1-x} \end{aligned}

将

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 =\cfrac{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 )

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

将上述生成函数写好之后 , 计算展开 ,

y

的

N

次幂的系数 , 就是正整数

N

的拆分方案数 ;

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-10-29，如有侵权请联系 cloudcommunity@tencent.com 删除

博客

函数

模型

数学

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度