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

韩曙亮

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

4250

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

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

文章目录

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

参考博客 :

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

1

克砝码

2

个 ,

2

克砝码

1

个 ,

4

克砝码

2

个 ,

可以称出哪些重量 , 有多少方案个数 ;

1

克的砝码个数是

x_1

个 , 取值范围是

0 \leq x_1 \leq 2

, 可取值

0 , 1, 2

2

克的砝码个数是

x_2

个 , 取值范围是

0 \leq x_2 \leq 1

, 可取值

0,1

4

克的砝码个数是

x_3

个 , 取值范围是

0 \leq x_3 \leq 2

, 可取值

0,1,2

x_1 + 2x_2 + 4x_3 = r

, 其中

r

代表可以称出的重量 ,

写出上述 , 带限制条件 , 并且带系数的不定方程非负整数解的生成函数 :

x_1

项 , 带限制条件 , 没有系数 , 其底是

y

, 幂取值

0 , 1, 2

, 对应的生成函数项是

( 1 + y + y^2 )

x_2

项 , 带限制条件 , 带系数

2

, 其底是

y^2

, 幂取值

0,1

, 对应生成函数项是

(y^2)^0 + (y^2)^1 = 1+ y^2

x_3

项 , 带限制条件 , 带系数

4

, 其底是

y^4

, 幂取值

0,1, 2

, 对应生成函数项是

(y^4)^0 + (y^4)^1 + (y^4)^2 = 1+ y^4 + y^8

将上述三项乘起来 , 并展开 :

G(x) = ( 1 + y + y^2 ) (1+ y^2) (1+ y^4 + y^8)

\ \ \ \ \ \ \ \ \ \ =1 + y + 2y^2 + y^3 + 2y^4 + y^5 + 2y^6 + y^7 + 2y^8 + y^9 + 2y^{10} + y^{11} + y^{12}

上述展开后的

y

的次幂数是重量 , 系数是方案个数 , 如

2y^8

项表示 , 称出

8

克重量 , 有

2

个方案 ;

总体描述 :

1

项 : 表示

y^0

, 称出

0

克 , 有

0

种方案 ;

y

项 : 表示

y^1

, 称出

1

克 , 有

1

种方案 ;

2y^2

项 : 表示

2y^2

, 称出

2

克 , 有

2

种方案 ;

y^3

项 : 表示

y^3

, 称出

3

克 , 有

1

种方案 ;

2y^4

项 : 表示

2y^4

, 称出

4

克 , 有

2

种方案 ;

y^5

项 : 表示

y^5

, 称出

5

克 , 有

1

种方案 ;

2y^6

项 : 表示

2y^6

, 称出

6

克 , 有

2

种方案 ;

y^7

项 : 表示

y^7

, 称出

7

克 , 有

1

种方案 ;

2y^8

项 : 表示

2y^8

, 称出

8

克 , 有

2

种方案 ;

y^9

项 : 表示

y^9

, 称出

9

克 , 有

1

种方案 ;

2y^{10}

项 : 表示

2y^{10}

, 称出

10

克 , 有

2

种方案 ;

y^{11}

项 : 表示

y^{11}

, 称出

11

克 , 有

1

种方案 ;

y^{12}

项 : 表示

y^{12}

, 称出

12

克 , 有

1

种方案 ;

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

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

博客

函数

数学

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

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

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

博客

函数

数学

登录后参与评论

0 条评论

热度