离散数学中的组合x

《离散数学中的组合x》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、出个元素的方式数，即.证毕式(1.8)的证明也可由公式(1.7)得出，事实上推论2（Pascal公式）(1.9)证明：证毕.这个公式也可用组合分析的方法论证：在集合的个元素中固定一个元素，不妨设为，于是，从个元素中取个元素的组合就有下面两种情形组成：1)个元素中包含，这可以从除去的个元素中取个元素的组合，然后将加入而得到，其组合个数为.2)个元素中不包含，这可以从除去的个元素中取个元素的组合而得到，其组合个数为.由加法法则即得利用式(1.9)和初始值，对所有非负整数可计算出一张三角形阵列(P8)，通常称这个三角阵列为杨辉三角形或Pascal三角形.值得注意的是，如果仔细考察表，可以发现组合

3、中的一些关系式及其一些有趣的性质.推论3(1.10)证明：反复应用Pascal公式容易得到式(1.10).[例1]在一个平面上有42个点，且没有任何三个点在同一条直线上.通过这些点可以确定多少条不相同的直线？可以构成多少个位置不相同的三角形？解：由于没有三个点在一条线上，故每两个点可确定唯一的一条直线.故有条不同直线.又由于任意三点可以构成一个三角形，故有个位置不同的三角形.[例2]数510510能被多少个不同的奇数整数？解：由于510510=2·3·5·7·11·13·17，其中除2是偶数外都是奇数.于是要整除510510的奇数只能是除2以外的奇素数之积，而且在一个积中一个奇数至多出现一

4、次.奇素数之积分下面几种情况讨论：只包含一个奇素数，一共有个包含两个奇素数，一共个包含三个奇素数，一共个包含四个奇素数，一共个包含五个奇素数，一共个包含六个奇素数，一共个于是，由加法法则知总共有6+15+20+15+6+1=63个.故510510能被63个不同的奇数整除.上面，我们研究了从个不同的元素中选取个不同元素的组合.下面我们考虑从个不同的元素中，允许重复地从中选取个元素的组合，这就是重复组合.定义1.5从重集中选取个元素不考虑次序组合起来，称为从中取个元素的重复组合.用表示从中取个元素的重复组合种数.例如，则都是的2组合.在集合中，若，则由下面的定理.定理1.6的-组合数为(1.1

5、1)证明：设个元素和自然数一一对应.于是所考虑的任何组合便可看成是一个个数的组合，由于是组合，不妨认为各是按大小次序排列的.相同的连续地排在一起.如按排列.又令，即.由于最大可取，故最大可取.这样就得到一个集合的-组合.易见有一种的取法便有一种的取法.而这两种取法有一一对应关系，从而这两个组合计数问题时等价的.这样一来，允许重复的从个不同元素中取个元素的组合数和不允许重复的从个不同元素中取个元素的组合数是相同的.故有证毕.注意，在定理1.6中，如果的不同元素的重复数至少是，则结论仍成立.[例3]试问有多少项？解：展开式相当于从每一个右边括号里取一项相乘，可对应于有4个无标志的球，放进3个有

6、标志的盒子，一盒可多于1个球比如可以看作4个球全部放在标为的盒子.又比如可以看作盒有两个球，盒子各一个球.所以问题等价于从3个元素中取4个作允许重复的组合，其组合数为共15项.[例4]求个无区别的球放入个有标志的盒子里而无一空盒的方式数.解：由于每个盒子不能为空，故每个盒子中可先放一球，这样还剩个球，再将这个球放入个盒子中去，由于这时每盒的球数不受限制，这相当于从重集中取个元素的组合，由式(1.11)知，其组合数为[例5]在由数0,1,…,9组成的位整数所组成的集合中，如果将一个整数重新排列而得到另一个整数，则称这两个整数是等价的.那么，1)有多少不等价的整数？2)如果数字0和9最多只能出

7、现一次，又有多少不等价的整数.解：1)由两个整数等价的定义可知，一个位整数只和所取的数字有关，而与这些数字的次序无关，故这时一个组合问题.而且每一整数中的每一位可从数字0,1,…,9中任意选取，因此不等价的位整数可以看作是重集的-组合.由式(1.11)知，其个数为注意：这里将个0组成的数看作是0.2)数字0和9最多只能出现一次，由下列三种情形组成：a.数字0和9均不出现，这实际上是重集的-组合，其个数为b.数字0和9出现