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

2023-03-28 18:41:02 浏览数 (1)

文章目录

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

参考博客 :

  • 【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
  • 【组合数学】生成函数 ( 线性性质 | 乘积性质 )
  • 【组合数学】生成函数 ( 移位性质 )
  • 【组合数学】生成函数 ( 求和性质 )
  • 【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )
  • 【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★
  • 【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 )
  • 【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )
  • 【组合数学】生成函数 ( 使用生成函数求解多重集 r 组合数 )
  • 【组合数学】生成函数 ( 使用生成函数求解不定方程解个数 )

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

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

种方案 ;

博客 函数 数学

0 人点赞