【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 2 | 扩展到整数解 )

韩曙亮

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

4920

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

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

文章目录

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

参考博客 :

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

1

克砝码

2

个 ,

2

克砝码

1

个 ,

4

克砝码

2

个 ,

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

砝码可以放在左右两侧

将生成函数的概念 , 推广到可以放负数次幂 , 放在左边是正数 , 不放是

0

, 放在右边是负数 ,

1

克的砝码个数是

x_1

个 , 取值范围是

-2 \leq x_1 \leq 2

, 可取值

-2, -1, 0 , 1, 2

2

克的砝码个数是

x_2

个 , 取值范围是

-1 \leq x_2 \leq 1

, 可取值

-1, 0,1

4

克的砝码个数是

x_3

个 , 取值范围是

-2 \leq x_3 \leq 2

, 可取值

-2, -1, 0,1,2

x_1 + 2x_2 + 4x_3 = r

, 其中

r

代表可以称出的重量 ,

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

x_1

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

y

, 幂取值

0 , 1, 2

, 对应的生成函数项是

(y^{-2} + y^{-1} + 1 + y + y^2 )

x_2

项 , 带限制条件 , 带系数

2

, 其底是

y^2

, 幂取值

0,1

, 对应生成函数项是

(y^2)^{-1} + (y^2)^0 + (y^2)^1 = y^{-2} + 1+ y^2

x_3

项 , 带限制条件 , 带系数

4

, 其底是

y^4

, 幂取值

0,1, 2

, 对应生成函数项是

(y^4)^{-2} + (y^4)^{-1} + (y^4)^0 + (y^4)^1 + (y^4)^2 = y^{-8} + y^{-4} + 1+ y^4 + y^8

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

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

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

上述展开后的

y

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

4y^2

项表示 , 称出

2

克重量 , 有

4

个方案 ;

总体描述 :

1

项 : 表示

y^0

, 称出

0

克 , 有

0

种方案 ;

3y

项 : 表示

3y^1

, 称出

1

克 , 有

3

种方案 ;

4y^2

项 : 表示

4y^2

, 称出

2

克 , 有

4

种方案 ;

3y^3

项 : 表示

3y^3

, 称出

3

克 , 有

3

种方案 ;

5y^4

项 : 表示

5y^4

, 称出

4

克 , 有

5

种方案 ;

3y^5

项 : 表示

3y^5

, 称出

5

克 , 有

3

种方案 ;

4y^6

项 : 表示

4y^6

, 称出

6

克 , 有

4

种方案 ;

3y^7

项 : 表示

3y^7

, 称出

7

克 , 有

3

种方案 ;

4y^8

项 : 表示

4y^8

, 称出

8

克 , 有

4

种方案 ;

2y^9

项 : 表示

2y^9

, 称出

9

克 , 有

2

种方案 ;

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 条评论

热度