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

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

文章目录

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

1、带限制条件

2、带系数



参考博客 :


【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )

【组合数学】生成函数 ( 线性性质 | 乘积性质 )

【组合数学】生成函数 ( 移位性质 )

【组合数学】生成函数 ( 求和性质 )

【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )

【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★

【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 )

【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )

【组合数学】生成函数 ( 使用生成函数求解多重集 r 组合数 )





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


不定方程的解个数 :


x 1 + x 2 + ⋯ + x k = r x_1 + x_2 + \cdots + x_k = rx

1


+x

2


+⋯+x

k


=r


x i x_ix

i


 为自然数 ;


之前通过组合对应的方法 , 已经解决 , 其解个数是 C ( k + r − 1 , r ) C(k + r - 1 , r)C(k+r−1,r)



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



上述情况下 , x i x_ix

i


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

i


 取值受限 , 如 x 1 x_1x

1


 取值必须满足 2 ≤ x 1 ≤ 5 2 \leq x_1 \leq 52≤x

1


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





1、带限制条件


x 1 + x 2 + ⋯ + x k = r x_1 + x_2 + \cdots + x_k = rx

1


+x

2


+⋯+x

k


=r


如果 x i x_ix

i


 取值受到约束 , l i ≤ x i ≤ n i l_i \leq x_i \leq n_il

i


≤x

i


≤n

i


 , 则对应的 生成函数项的 y yy 次幂值从 l i l_il

i


 到 n i n_in

i


 ;


对应的生成函数项是 y l i + y l i + 1 + ⋯ + y n i y^{l_i} + y^{l_i + 1} + \cdots + y^{n_i}y

l

i


+y

l

i


+1

+⋯+y

n

i




完整的生成函数是 :


G ( y ) = ( y l 1 + y l 1 + 1 + ⋯ + y n 1 ) ( y l 2 + y l 2 + 1 + ⋯ + y n 2 ) ⋯ ( y l k + y l k + 1 + ⋯ + y n k ) 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} )G(y)=(y

l

1


+y

l

1


+1

+⋯+y

n

1


)(y

l

2


+y

l

2


+1

+⋯+y

n

2


)⋯(y

l

k


+y

l

k


+1

+⋯+y

n

k


)



将上述生成函数结果乘出来 , y r y^ry

r

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




2、带系数


p 1 x 1 + p 2 x 2 + ⋯ + p k x k = r p_1x_1 + p_2x_2 + \cdots + p_kx_k = rp

1


x

1


+p

2


x

2


+⋯+p

k


x

k


=r


x i ∈ N x_i \in Nx

i


∈N , 非负整数解 , 对 x i x_ix

i


 不设置上限 ;



带系数的函数非负整数解 , 生成函数的项的基本的 底是 y p i y^{p_i}y

p

i


 , 幂的取值范围是 0 , 1 , 2 , ⋯ 0 , 1, 2, \cdots0,1,2,⋯ ,


每个生成函数项是 ( y p i ) 0 + ( y p i ) 1 + ( y p i ) 2 + ( y p i ) 3 + ⋯ (y^{p_i})^0 + (y^{p_i})^1 + (y^{p_i})^2 + (y^{p_i})^3 + \cdots(y

p

i


)

0

+(y

p

i


)

1

+(y

p

i


)

2

+(y

p

i


)

3

+⋯ ,


化简后的项是 1 + y p i + y 2 p i + y 3 p i + ⋯ 1 +y^{p_i} + y^{2p_i} + y^{3p_i} + \cdots1+y

p

i


+y

2p

i


+y

3p

i


+⋯



将所有的 k kk 项相乘 , 就是对应的生成函数 :


G ( y ) = ( 1 + y p 1 + y 2 p 1 + y 3 p 1 + ⋯ ) ( 1 + y p 2 + y 2 p 2 + y 3 p 2 + ⋯ ) ⋯ ( 1 + y p k + y 2 p k + y 3 p 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})G(y)=(1+y

p

1


+y

2p

1


+y

3p

1


+⋯

)(1+y

p

2


+y

2p

2


+y

3p

2


+⋯

)⋯(1+y

p

k


+y

2p

k


+y

3p

k


+⋯

)



该方程的非负整数解个数是 y r y^ry

r

 前的系数 ;


目录
相关文章
|
7月前
【每日一题Day146】给定行和列的和求可行矩阵 | 贪心
【每日一题Day146】给定行和列的和求可行矩阵 | 贪心
55 0
|
6月前
高等数学II-知识点(1)——原函数的概念、不定积分、求原函数的两种常用方法 (凑微分法、第二换元法)、分部积分法、有理函数原函数求法、典型三角函数原函数求法
高等数学II-知识点(1)——原函数的概念、不定积分、求原函数的两种常用方法 (凑微分法、第二换元法)、分部积分法、有理函数原函数求法、典型三角函数原函数求法
184 1
|
7月前
|
算法 测试技术 C++
【分解质因数 差分数组】2584. 分割数组使乘积互质
【分解质因数 差分数组】2584. 分割数组使乘积互质
【分解质因数 差分数组】2584. 分割数组使乘积互质
|
7月前
|
C语言
【汇编语言实战】求两组给定数组最大值
【汇编语言实战】求两组给定数组最大值
21 0
|
C语言
二维数组实验题:按如下公式递归计算矩阵行列式的值:(C语言)
二维数组实验题:按如下公式递归计算矩阵行列式的值:(C语言)
241 1
二维数组实验题:按如下公式递归计算矩阵行列式的值:(C语言)
第7章 符号计算——7.8 符号代数方程求解
第7章 符号计算——7.8 符号代数方程求解
第7章 符号计算——7.9 符号微分方程求解
第7章 符号计算——7.9 符号微分方程求解
|
算法
一元多项式相加问题(两种方法)
一元多项式的相加问题,主要运用了线性结构的合并,在合并线性结构的基础上,增加判断,所以我们可以将这个问题理解为一个复杂的线性表合并问题
258 0
一元多项式相加问题(两种方法)
|
机器学习/深度学习 移动开发
【组合数学】指数生成函数 ( 指数生成函数概念 | 排列数指数生成函数 = 组合数普通生成函数 | 指数生成函数示例 )
【组合数学】指数生成函数 ( 指数生成函数概念 | 排列数指数生成函数 = 组合数普通生成函数 | 指数生成函数示例 )
345 0