离散数学中的组合28.pptxVIP

组合; 证毕. 推论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) 证明：设 个元素 和自然数 一一对应. 于是所考虑的任 何组合便可看成是一个 个数的组合 ，由于是组合，不妨认为各 是 按大小次序排列的. 相同的 连续地排在一起. 如按 排列. 又令 ，即