2023-03-27 16:22:11
浏览数 (1)
文章目录 多重集 r 组合数 生成函数计算方法 多重集 r 组合数题目 不定方程解个数 x 取值范围为 ( 0 ~ n ) 不定方程解个数 x 取值范围为 自然数 ( 0 ~ ∞ ) 符合多重集组合公式计算情况 不定方程解个数 x 取值范围 ( 给定一个范围 ) 不定方程解个数 x 取值范围 ( 给定一个范围 并带系数 ) 不定方程解的题目 带限制的情况 多重集 r 组合数 生成函数计算方法 此处引入 不定方程的解 和 生成函数系数问题 , 帮助解决问题 ;
以下三个值是等价的 :
① 多重集
S = {n_1 cdot a_1 , n_2 cdot a_2 , cdots , n_k cdot a_k } 的
r- 组合数
② 不定方程
x_1 x_2 cdots x_k = r (x_i leq n_i) 的非负整数解个数 ;
③ 生成函数
G(y) = (1 y y^2 cdots y^{n_1}) (1 y y^2 cdots y^{n_2})cdots (1 y y^2 cdots y^{n_k}) 展开后
y^r 的系数 ;
生成函数中
y 的幂从
0 到
n_i ,
1 是
y^0 ;
x_i 对应的是多重集中的 , 指定某元素
a_i 的个数 ;
多重集 r 组合数题目 题目 : 计算
S={3 cdot a , 4 cdot b , 5 cdot c} 的 10-组合数 ;
分析 : 以下 三个 数 是等价的 ;
S={3 cdot a , 4 cdot b , 5 cdot c} 的
10- 组合数 ;
G(y) = (y^0 y^1 y^2 y^3) (y^0 y^1 y^2 y^3 y^4) (y^0 y^1 y^2 y^3 y^4 y^5) 展开式中的
y^{10} 的系数 ;
解 :
① 展开上述生成函数 :
G(y) = (y^0 y^1 y^2 y^3) (y^0 y^1 y^2 y^3 y^4) (y^0 y^1 y^2 y^3 y^4 y^5) ② 其中
y^0 = 1 ,
y^1 =y , 替换 :
= (1 y y^2 y^3) (1 y y^2 y^3 y^4) (1 y y^2 y^3 y^4 y^5) ③ 先将前两项
(1 y y^2 y^3) (1 y y^2 y^3 y^4) 计算出来 :
(1 y y^2 y^3) (1 y y^2 y^3 y^4) =1 y y^2 y^3 y^4 y(1 y y^2 y^3 y^4) y^2(1 y y^2 y^3 y^4) y^3(1 y y^2 y^3 y^4) =1 2y 3y^2 4y^3 4y^4 3y^5 2y^6 y^7 ④ 将 ③ 结果代入到 ② 中 :
G(y) = (1 2y 3y^2 4y^3 4y^4 3y^5 2y^6 y^7) (1 y y^2 y^3 y^4 y^5) ⑤ 上式全部展开没有意义 , 这里我们只统计 y^10 的组合 :
3y^5 与
y^5 可以乘出一个
3y^{10} 2y^6 与
y^4 可以乘出一个
2y^{10} y^7 与
y^4 可以乘出一个
y^{10} ⑥ 最终结果相加 :
y^{10} 前的系数为 6 ;
不定方程解个数 x 取值范围为 ( 0 ~ n ) 该情况下 值 与 多重集 的组
r- 组合数是等价的 ;
此时的多重集中每个元素的个数 是限定在
0 到 某个数
n 之间的 ;
这是是之前的多重集排列公式无法计算的情况 , 此处使用生成函数可以统计 多重集 的
r- 组合数 ;
以下三个值是等价的 :
① 不定方程
x_1 x_2 cdots x_k = r (x_i leq n_i) 的解个数 ;
② 多重集
S = {n_1 cdot a_1 , n_2 cdot a_2 , cdots , n_k cdot a_k } 的
r- 组合数
③ 生成函数
G(y) = (1 y y^2 cdots y^{n_1}) (1 y y^2 cdots y^{n_2})cdots (1 y y^2 cdots y^{n_k}) 展开后
y^r 的系数 ;
生成函数中
y 的幂从
0 到
n_i ,
1 是
y^0 ;
x_i 对应的是多重集中的 , 指定某元素
a_i 的个数 ;
不定方程解个数 x 取值范围为 自然数 ( 0 ~ ∞ ) 符合多重集组合公式计算情况 该情况下 值 与 多重集 的组
r- 组合数是等价的 ;
此时的多重集中每个元素的个数 是无限的 或者 大于 等于
r ;
该情况下的多重集组合问题 , 可以使用组合公式 , 多重集 的
r- 组合 , 其有
k 种元素 每种个数大于等于
r 或 无限 ; 使用公式
C(r k - 1, r) 以下三个值是等价的 :
① 不定方程
x_1 x_2 cdots x_k = r ( 0 leq x_i) 的解个数 ;
② 多重集
S = {infty cdot a_1 , infty cdot a_2 , cdots , infty cdot a_k } 的
r- 组合数
③ 生成函数
G(y) = (1 y y^2 cdots )^k 展开后
y^r 的系数 ;
生成函数中
y 的幂从
0 到
n_i ,
1 是
y^0 ;
x_i 对应的是多重集中的 , 指定某元素
a_i 的个数 ;
不定方程解个数 x 取值范围 ( 给定一个范围 ) 该情况下 多重集的组合 问题就该退出舞台了 , 只剩下 不定方程解 和 生成函数的系数 了 ,
x_i 的取值有可能是负的 ;
以下两个值是等价的 :
① 不定方程
x_1 x_2 cdots x_k = r ( l_i leq x_i leq n_j) 的解个数 ;
② 生成函数
G(y) = (y^{l_1} cdots y^{n_1})(y^{l_2} cdots y^{n_2})cdots(y^{l_k} cdots y^{n_k}) 展开后
y^r 的系数 ;
③ 多重集问题在这里就不太适用了 ,
x 取值有可能是负数 ;
生成函数中
y 的幂从
i 到
j ;
不定方程解个数 x 取值范围 ( 给定一个范围 并带系数 ) 以下两个值是等价的 :
① 不定方程
p_1x_1 p_2x_2 cdots p_kx_k = r ( l_i leq x_i leq n_j) 的解个数 ;
② 生成函数
G(y) = ((y^p_1)^{l_1} cdots (y^p_1)^{n_1})((y^p_2)^{l_2} cdots (y^p_2)^{n_2})cdots((y^p_k)^{l_k} cdots (y^p_k)^{n_k}) 展开后
y^r 的系数 ;
③ 多重集问题在这里就不太适用了 ,
x 取值有可能是负数 ;
注意不定方程带系数的情况下 , 生成函数中需要使用
y^{系数} 替代
y , 生成函数中
y^{系数} 的幂从
i 到
j ;
不定方程解的题目 带限制的情况 题目 : 求方程
x_1 x_2 x_3 x_4 = 15 的整数解个数 , 其中
x_1 geq 1 , x_2 geq 2 , x_3 geq 4 , x_4 geq 4 ;
分析 :
1>不要直接求解 : 直接列出生成函数 , 就将问题复杂化了 ; 2> 换元转化 : 这里可以将其转为 非负整数解的个数来计算 ; 3> 多重集组合数 : 此时就等价于 多重集 S = {infty cdot a_1 , infty cdot a_2 , cdots , infty cdot a_k } 的
r- 组合数 , 使用 多重集组合数公式
C(r k - 1, r) 计算 ;
解 :
① 换元准备 :
y_1 = x_1 - 1 , 此时
y_1 的取值范围是
N ( 自然数 ) ;
y_2 = x_2 - 2 , 此时
y_2 的取值范围是
N ( 自然数 ) ;
y_3 = x_3 - 4 , 此时
y_3 的取值范围是
N ( 自然数 ) ;
y_4 = x_4 - 4 , 此时
y_4 的取值范围是
N ( 自然数 ) ;
② 换元过程 :
y_1 1 替换
x_1 ;
y_2 2 替换
x_2 ;
y_3 4 替换
x_3 ;
y_4 4 替换
x_4 ;
x_1 x_2 x_3 x_4 = 15 (y_1 1) (y_2 2) (y_3 4) (y_4 4) = 15 y_1 y_2 y_3 y_4 11 = 15 y_1 y_2 y_3 y_4 = 4 ③ 求
y_1 y_2 y_3 y_4 = 4 (
y_i 是自然数 ) , 非负整数解个数 ;
相当于求
S = {infty cdot a_1 , infty cdot a_2 , infty cdot a_3, infty cdot a_4 } 的
4- 组合数 , 根据公式
C(r k - 1 , r) 计算 :
C(4 4 - 1 , 4) = C(7,4) = dbinom{7}{4} = cfrac{7!}{(7-4)!4!} = cfrac{7 times 6 times 5 times 4 times 3 times 2 times 1}{4 times 3 times 2 times 1 times 3 times 2 times 1} = 35 解这 整数解 个数的问题 :
① 如果
x_i 的取值范围是 自然数 或 可以转化成 自然数的 , 那就用 多重集 组合公式计算 ;
② 如果
x_i 的取值范围是一个闭区间 , 直接生成函数 展开 , 计算
y^r 的系数是多少 , 该系数就是整数解个数 ;
