作业帮关于组合数学里多重集合的问题.以下是例题和解答,我搞不懂的是,引入的新变量y到底代表的是什么,为什么会这么引入?怎么就引入了 y1 = x1 - 3呢? 例 令 S 是具有四种元素 a, b, c, d 的多重集 {10
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/09 04:24:36
关于组合数学里多重集合的问题.以下是例题和解答,我搞不懂的是,引入的新变量y到底代表的是什么,为什么会这么引入?怎么就引入了 y1 = x1 - 3呢? 例 令 S 是具有四种元素 a, b, c, d 的多重集 {10
关于组合数学里多重集合的问题.
以下是例题和解答,我搞不懂的是,引入的新变量y到底代表的是什么,为什么会这么引入?怎么就引入了 y1 = x1 - 3呢?
例 令 S 是具有四种元素 a, b, c, d 的多重集 {10*a, 10*b, 10*c, 10*d},S 使得 4 种元素的每一种都至少出现一次的 10-组合 的数目是多少?
设 x1 为 a 出现的次数,x2 为 b 出现的次数,...,x4 为 d 出现的次数,得到方程
x1 + x2 + x3 + x4 = 10
因为所有元素的重复数都等于 10,且要求的组合数也是 10,所以可以当做所有元素都有无限个,进行变量代换 y1 = x1 - 1, y2 = x2 - 1, ..., y4 = x4 - 1,得到新方程
y1 + y2 + y3 + y4 = 6
则得到的解为 C(6 + 4 - 1, 6) = C(9, 6) = 9! / (3! * 6!)
例 方程 x1 + x2 + x3 + x4 = 20,其中 x1 >= 3, x2 >= 1, x3 >= 0, x4 >= 5,则方程的整数解有多少个?
引入新变量 y1 = x1 - 3, y2 = x2 - 1, y3 = x3, y4 = x4 - 5
y1 + y2 + y3 + y4 = 11
则得到解的个数为 C(11 + 4 - 1, 11) = 14! / (3! * 11!) 种
关于组合数学里多重集合的问题.以下是例题和解答,我搞不懂的是,引入的新变量y到底代表的是什么,为什么会这么引入?怎么就引入了 y1 = x1 - 3呢? 例 令 S 是具有四种元素 a, b, c, d 的多重集 {10
关键之处在于：公式C(k+n-1,k)是方程
x1+x2+x3+.+xn=k
的非负整数解,即诸xi>=0,注意,有等号
设 x1 为 a 出现的次数,x2 为 b 出现的次数,...,x4 为 d 出现的次数,得到方程
x1 + x2 + x3 + x4 = 10
4 种元素的每一种都至少出现一次的 ,xi>0
而公式里要求xi>=0,
有xi>0,得xi-1>=0,
所以令 :yi=xi-1
同样可以解释“ 引入新变量 y1 = x1 - 3,y2 = x2 - 1,y3 = x3,y4 = x4 - 5
y1 + y2 + y3 + y4 = 11 ”