【组合数学】生成函数 ( 正整数拆分 | 正整数拆分基本模型 | 有限制条件的无序拆分 )

韩曙亮

发布于 2023-03-28 10:42:03

2.2K0

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

文章目录

参考博客 :

一、正整数拆分基本模型

无序拆分基本模型 :

将正整数

N

$N$

无序拆分成正整数 ,

a_{1}, a_{2}, \dots, a_{n}

$a_1, a_2, \cdots , a_n$

是拆分后的

n

$n$

个数 ,

该拆分是无序的 , 上述拆分的

n

$n$

个数的个数可能是不一样的 ,

假设

a_{1}

$a_1$

有

x_{1}

$x_1$

个 ,

a_{2}

$a_2$

有

x_{2}

$x_2$

个 ,

\dots

$\cdots$

a_{n}

$a_n$

有

x_{n}

$x_n$

个 , 那么有如下方程 :

a_{1} x_{1} + a_{2} x_{2} + \dots + a_{n} x_{n} = N

$a_1x_1 + a_2x_2 + \cdots + a_nx_n = N$

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

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

如果不允许重复 , 那么这些

x_{i}

$x_i$

的取值 , 只能取值

0, 1

$0, 1$

; 相当于带限制条件 , 带系数的不定方程非负整数解的情况 ;

对应的生成函数是 :

G (x) = (1 + y^{a_{1}}) (1 + y^{a_{2}}) \dots (1 + y^{a_{n}})

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

如果允许重复 , 那么这些

x_{i}

$x_i$

的取值 , 就是自然数 ; 相当于带系数的不定方程非负整数解的情况 ;

对应的生成函数是 :

G (x) = (1 + y^{a_{1}} + y^{2 a_{1}} \dots) (1 + y^{a_{2}} + y^{2 a_{2}} \dots) \dots (1 + y^{a_{n}} + y^{2 a_{n}} \dots)

$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}}) \dots (1 - y^{a_{n}})}

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

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

将正整数

N

$N$

无序拆分成正整数 ,

a_{1}, a_{2}, \dots, a_{n}

$a_1, a_2, \cdots , a_n$

是拆分后的

n

$n$

个数 ,

该拆分是无序的 , 上述拆分的

n

$n$

个数的个数可能是不一样的 ,

假设

a_{1}

$a_1$

有

x_{1}

$x_1$

个 ,

a_{2}

$a_2$

有

x_{2}

$x_2$

个 ,

\dots

$\cdots$

a_{n}

$a_n$

有

x_{n}

$x_n$

个 , 那么有如下方程 :

a_{1} x_{1} + a_{2} x_{2} + \dots + a_{n} x_{n} = N

$a_1x_1 + a_2x_2 + \cdots + a_nx_n = N$

其中存在限制条件 ,

a_{i}

$a_i$

的取值个数

x_{i}

$x_i$

取值范围做一下限制 ,

l_{i} \leq x_{i} \leq t_{i}

$l_i \leq x_i \leq t_i$

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

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

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

博客

函数

模型

数学

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

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

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

登录后参与评论

暂无评论