【组合数学】生成函数 ( 使用生成函数求解不定方程解个数 )

韩曙亮

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

6800

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

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

文章目录

参考博客 :

一、使用生成函数求解不定方程解个数

不定方程的解个数 :

x_1 + x_2 + \cdots + x_k = r

x_i

为自然数 ;

之前通过组合对应的方法 , 已经解决 , 其解个数是

C(k + r - 1 , r)

不定方程解的个数 , 推导过程参考 : 【组合数学】排列组合 ( 多重集组合数 | 所有元素重复度大于组合数 | 多重集组合数推导 1 分割线推导 | 多重集组合数推导 2 不定方程非负整数解个数推导 ) 二、多重集组合所有元素重复度大于组合数推导 2 ( 不定方程非负整数解个数推导 )

上述情况下 ,

x_i

的取值都是没有上限的 , 如果

x_i

取值受限 , 如

x_1

取值必须满足

2 \leq x_1 \leq 5

条件时 , 就不能使用上述公式进行计算 , 这里需要使用到生成函数求解 ;

1、带限制条件

x_1 + x_2 + \cdots + x_k = r

如果

x_i

取值受到约束 ,

l_i \leq x_i \leq n_i

, 则对应的生成函数项的

y

次幂值从

l_i

到

n_i

;

对应的生成函数项是

y^{l_i} + y^{l_i + 1} + \cdots + y^{n_i}

完整的生成函数是 :

G(y) = ( y^{l_1} + y^{l_1+1} + \cdots + y^{n_1} )( y^{l_2} + y^{l_2+1} + \cdots + y^{n_2} ) \cdots ( y^{l_k} + y^{l_k+1} + \cdots + y^{n_k} )

将上述生成函数结果乘出来 ,

y^r

前的系数 , 就是不定方程的解的个数 ;

2、带系数

p_1x_1 + p_2x_2 + \cdots + p_kx_k = r

x_i \in N

, 非负整数解 , 对

x_i

不设置上限 ;

带系数的函数非负整数解 , 生成函数的项的基本的底是

y^{p_i}

, 幂的取值范围是

0 , 1, 2, \cdots

,

每个生成函数项是

(y^{p_i})^0 + (y^{p_i})^1 + (y^{p_i})^2 + (y^{p_i})^3 + \cdots

,

化简后的项是

1 +y^{p_i} + y^{2p_i} + y^{3p_i} + \cdots

将所有的

k

项相乘 , 就是对应的生成函数 :

G(y)=(1+y^{p_1} + y^{2p_1} + y^{3p_1 + \cdots})(1+y^{p_2} + y^{2p_2} + y^{3p_2 + \cdots}) \cdots (1+y^{p_k} + y^{2p_k} + y^{3p_k + \cdots})

该方程的非负整数解个数是

y^r

前的系数 ;

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

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

博客

函数

数学

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

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

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

博客

函数

数学

登录后参与评论

0 条评论

热度