离散数学中的组合.pptx

组合 研究组合的主要目的之一是求出根据已知条件所能作出的不同组合的种数 定义1 4设是具有个元素的集合 是非负整数 从这个不同的元素里取个不考虑次序组合起来 称为集合的组合 换句话说 的 组合是的 无序子集 用或表示集合的 组合的个数 另外 为了使用方便 我们定义 定理1 5对于 有 1 7 证明 从个不同的元素里取个元素的组合个数为 而个元素可以组成个 排列 也就是说一个 组合对应个 排列 于是个 组合就对应个 排列 这实际就是从个元素中选取个元素组成的 排列数 因此有 所以有 证毕 推论1 1 8 证明 事实上 从个不同的元素中选取个元素 就有个元素没有被选出 因此选出个元素的方式数等于选出个元素的方式数 即 证毕式 1 8 的证明也可由公式 1 7 得出 事实上推论2 Pascal公式 1 9 证明 证毕 这个公式也可用组合分析的方法论证 在集合的个元素中固定一个元素 不妨设为 于是 从个元素中取个元素的组合就有下面两种情形组成 1 个元素中包含 这可以从除去的个元素中取个元素的组合 然后将加入而得到 其组合个数为 2 个元素中不包含 这可以从除去的个元素中取个元素的组合而得到 其组合个数为 由加法法则即得利用式 1 9 和初始值 对所有非负整数可计算出一张三角形阵列 P8 通常称这个三角阵列为杨辉三角形或Pascal三角形 值得注意的是 如果仔细考察表 可以发现组合中的一些关系式及其一些有趣的性质 推论3 1 10 证明 反复应用Pascal公式容易得到式 1 10 例1 在一个平面上有42个点 且没有任何三个点在同一条直线上 通过这些点可以确定多少条不相同的直线 可以构成多少个位置不相同的三角形 解 由于没有三个点在一条线上 故每两个点可确定唯一的一条直线 故有条不同直线 又由于任意三点可以构成一个三角形 故有个位置不同的三角形 例2 数510510能被多少个不同的奇数整数 解 由于510510 2 3 5 7 11 13 17 其中除2是偶数外都是奇数 于是要整除510510的奇数只能是除2以外的奇素数之积 而且在一个积中一个奇数至多出现一次 奇素数之积分下面几种情况讨论 只包含一个奇素数 一共有个包含两个奇素数 一共个包含三个奇素数 一共个包含四个奇素数 一共个包含五个奇素数 一共个包含六个奇素数 一共个于是 由加法法则知总共有6 15 20 15 6 1 63个 故510510能被63个不同的奇数整除 上面 我们研究了从个不同的元素中选取个不同元素的组合 下面我们考虑从个不同的元素中 允许重复地从中选取个元素的组合 这就是重复组合 定义1 5从重集中选取个元素不考虑次序组合起来 称为从中取个元素的重复组合 用表示从中取个元素的重复组合种数 例如 则都是的2组合 在集合中 若 则由下面的定理 定理1 6的 组合数为 1 11 证明 设个元素和自然数一一对应 于是所考虑的任何组合便可看成是一个个数的组合 由于是组合 不妨认为各是按大小次序排列的 相同的连续地排在一起 如按排列 又令 即 由于最大可取 故最大可取 这样就得到一个集合的 组合 易见有一种的取法便有一种的取法 而这两种取法有一一对应关系 从而这两个组合计数问题时等价的 这样一来 允许重复的从个不同元素中取个元素的组合数和不允许重复的从个不同元素中取 个元素的组合数是相同的 故有证毕 注意 在定理1 6中 如果的不同元素的重复数至少是 则结论仍成立 例3 试问有多少项 解 展开式相当于从每一个右边括号里取一项相乘 可对应于有4个无标志的球 放进3个有标志的盒子 一盒可多于1个球比如可以看作4个球全部放在标为的盒子 又比如可以看作盒有两个球 盒子各一个球 所以问题等价于从3个元素中取4个作允许重复的组合 其组合数为共15项 例4 求个无区别的球放入个有标志的盒子里而无一空盒的方式数 解 由于每个盒子不能为空 故每个盒子中可先放一球 这样还剩个球 再将这个球放入个盒子中去 由于这时每盒的球数不受限制 这相当于从重集中取个元素的组合 由式 1 11 知 其组合数为 例5 在由数0 1 9组成的位整数所组成的集合中 如果将一个整数重新排列而得到另一个整数 则称这两个整数是等价的 那么 1 有多少不等价的整数 2 如果数字0和9最多只能出现一次 又有多少不等价的整数 解 1 由两个整数等价的定义可知 一个位整数只和所取的数字有关 而与这些数字的次序无关 故这时一个组合问题 而且每一整数中的每一位可从数 字0 1 9中任意选取 因此不等价的位整数可以看作是重集的 组合 由式 1 11 知 其个数为注意 这里将个0组成的数看作是0 2 数字0和9最多只能出现一次 由下列三种情形组成 a 数字0和9均不出现 这实际上是重集的 组合 其个数为b 数字0和9出现其一 或者数字0出现一次 或者数字9出现一次 若数字0出现 数字9不出现 这实际上是重集的 组合 然后将数字0加入 其个数为同样 数字9出现 数字0不出现 其个数为c 数字0和9都出现一次 这实际上是重集的 组合 然后将0和9加入 其个数为由加法规则知 符合题意要求的不等价整数个数为 例6 求方程的非负整数解的个数 其中为正整数 解 设为个不同的元素 于是重集的任何一个 组合都具有形式 其中是非负整数且满足方程 反之 对于每个满足方程的非负整数解都对应于重集的一个 组合 于是 方程的非负整数解的个数就等于重集的 组合数 不相邻的组合所谓不相邻的组合是指从取个不相邻的数的组合 即不存在相邻两个数和的组合 例如 有组合 定理1 3从中取个作不相邻的组合 其组合数为证明 设是一组不相邻的组合 假定 令 则有 即为从中取个作不允许重复的组合 假定 反之 从中取个作不允许重复的组合 假定 则 则 而且故是从取个作不相邻的组合 若 则不存在这样的组合 后面我们在讨论容斥原理时会讲到对夫妻问题 会用到这个结论 组合的生成组合的生成比排列要简单些 试从1 2 3 4 5 6 7中取3个作组合得如下一组 从中找出生成的规律 123 124 125 126 127234 235 236 237345 346 347456 457567134 135 136 137245 246 247356 3574671