文章目录
多重集 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) = 15y_1 + y_2 + y_3+y_4 + 11 = 15y_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 的系数是多少 , 该系数就是整数解个数 ;
