离散数学中的组合

1、 组合 研究组合的主要目的之一是求出根据已知条件所能作出的不同组合的种数. 定义1.4 设 是具有 个元素的集合， 是非负整数. 从这 个不同的元素里取 个不考虑次序组合起来 ，称为集合 的 组合.换句话说， 的 -组合是 的 -无序子集. 用 或 表示集合 的 -组合的个数. 另外，为了使用方便，我们定义： 定理1.5 对于 ，有 (1.7) 证明：从 个不同的元素里取 个元素的组合个数为 . 而 个元素可以组成 个 -排列，也就是说一个 -组合对应 个 -排列. 个 -组合就对应 个 排列，这实际就是从 个元素中选取 个元素组成的 排列数 ，因此有 . 所以有1 证毕. 推论1 (1.8)

2、 证明：事实上，从 个不同的元素中选取 个元素，就有 个元素没有被选出. 因此选出 个元素的方式数等于选出 个元素的方式数，即 . 证毕 式(1.8)的证明也可由公式(1.7)得出，事实上 推论2 （Pascal公式） (1.9) 证明： 证毕. 2 这个公式也可用组合分析的方法论证： 在集合 的 个元素中固定一个元素，不妨设为 ，于是，从 个元素中取 个元素的组合就有下面两种情形组成： 1) 个元素中包含 ，这可以从除去 的 个元素中取 个元素的组合，然后将 加入而得到，其组合个数为 . 2) 个元素中不包含 ，这可以从除去 的 个元素中取 个元素的组合而得到，其组合个数为 . 由加法法则即

3、得 利用式(1.9)和初始值 ，对所有非负整数可计算出一张三角形阵列(P8)，通常称这个三角阵列为杨辉三角形或Pascal三角形. 值得注意的是，如果仔细考察表，可以发现组合中的一些关系式及其一些有趣的性质. 推论3 (1.10) 证明：反复应用Pascal公式容易得到式(1.10).3 例1 在一个平面上有42个点，且没有任何三个点在同一条直线上. 通过这些点可以确定多少条不相同的直线？可以构成多少个位置不相同的三角形？ 解：由于没有三个点在一条线上，故每两个点可确定唯一的一条直线. 故有条不同直线. 又由于任意三点可以构成一个三角形，故有个位置不同的三角形. 例2 数510510能被多少个

4、不同的奇数整数？ 解：由于510510=2357111317，其中除2是偶数外都是奇数. 于是要整除510510的奇数只能是除2以外的奇素数之积，而且在一个积中一个奇数至多出现一次. 奇素数之积分下面几种情况讨论： 只包含一个奇素数，一共有 个 包含两个奇素数，一共 个 包含三个奇素数，一共 个 包含四个奇素数，一共 个 包含五个奇素数，一共 个 包含六个奇素数，一共 个 于是，由加法法则知总共有6+15+20+15+6+1=63个. 故510510能被63个不同的奇数整除.4 上面，我们研究了从 个不同的元素中选取 个不同元素的组合. 下面我们考虑从 个不同的元素中，允许重复地从中选取 个元

5、素的组合，这就是重复组合. 定义1.5 从重集 中选取 个元素不考虑次序组合起来，称为从 中取 个元素的重复组合. 用 表示从 中取 个元素的重复组合种数. 例如 ，则 都是 的2组合. 在集合 中，若 ，则由下面的定理. 定理1.6 的 -组合数为 (1.11) 证明：设 个元素 和自然数 一一对应. 于是所考虑的任何组合便可看成是一个 个数的组合 ，由于是组合，不妨认为各 是按大小次序排列的. 相同的 连续地排在一起. 如按 排列. 又令 ，即 . 由于 最大可取 ，故 最大可取 . 这样就得到一个集合 的 -组合 .易见有一种 的取法便有一种 的取法. 而这两种取法有一一对应关系，从而这

6、两个组合计数问题时等价的. 这样一来，允许重复的从 个不同元素中取 个元素的组合数和不允许重复的从 个不同元素中取5个元素的组合数是相同的. 故有 证毕. 注意，在定理1.6中，如果 的不同元素的重复数至少是 ，则结论仍成立. 例3 试问 有多少项？ 解：展开式相当于从每一个右边括号里取一项相乘，可对应于有4个无标志的球，放进3个有标志 的盒子，一盒可多于1个球比如 可以看作4个球全部放在标 为 的盒子. 又比如 可以看作 盒有两个球， 盒子各一个球. 所以问题等价于从3个元素中取4个作允许重复的组合，其组合数为 共15项. 6 例4 求 个无区别的球放入 个有标志的盒子里 而无一空盒的方式数

7、. 解：由于每个盒子不能为空，故每个盒子中可先放一球，这样还剩 个球，再将这 个球放入 个盒子中去，由于这时每盒的球数不受限制，这相当于从重集 中取 个元素的组合，由式(1.11)知，其组合数为 例5 在由数0,1,9组成的 位整数所组成的集合中，如果将一个整数重新排列而得到另一个整数，则称这两个整数是等价的. 那么， 1)有多少不等价的整数？ 2)如果数字0和9最多只能出现一次，又有多少不等价的整数. 解：1)由两个整数等价的定义可知，一个 位整数只和所取的数字有关，而与这些数字的次序无关，故这时一个组合问题. 而且每一整数中的每一位可从数7字0,1,9中任意选取，因此不等价的 位整数可以看

8、作是重集 的 -组合. 由式(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加入，其个数为由加法规则知，符合题意要求的不等价整数个数为 8 例6 求方程 的非负整数解的个数，其中 为正整数. 解：设 为 个不同

9、的元素，于是重集 的任何一个 -组合都具有形式 ，其中 是非负整数且满足方程 .反之，对于每个满足方程 的非负整数解 都对应于重集 的一个 -组合. 于是，方程 的非负整数解的个数就等于重集 的 -组合数 .不相邻的组合 所谓不相邻的组合是指从 取 个不相邻的数的组合，即不存在相邻两个数 和 的组合. 例如 ，有组合 . 定理1-3 从 中取 个作不相邻的组合，其组合数为 证明：设 是一组不相邻的组合，假定 ， 令 ，则 有 ，即为从 中取 个作不允许重复的组合，假定 . 反之， ，从 中取 个作不允许重复的组合 ，假定 ，则9则 ，而且 故 是从 取 个 作不相邻的组合. 若 ，则不存在这样的组合. 后面我们在讨论容斥原理时会讲到 对夫妻问题，会用到这个结论.组合的生成 组合的生成比排列要简单些，试从1,2,3,4,5,6,7中取3个作组合得如下一组，从中找出生成的规律.123,124,125,126,127 234,235,236,237 345,346,347 456,457 567134,135,136,137 245,246,247 356,357 467145,146,147