离散数学中的组合

组合研究组合主要目标之一是求出依据已知条件所能作出不一样组合种数.

定义1.4设是含有个元素集合，是非负整数.从这个不一样元素里取个不考虑次序组合起来，称为集合组合.换句话说，-组合是-无序子集.用或表示集合-组合个数.

另外，为了使用方便，我们定义：

定理1.5对于，有(1.7)

证实：从个不一样元素里取个元素组合个数为.而个元素能够组成个-排列，也就是说一个-组合对应个-排列.于是个-组合就对应个–排列，这实际就是从个元素中选取个元素组成–排列数，所以有.所以有第1页

证毕.

推论1(1.8)

证实：实际上，从个不一样元素中选取个元素，就有个元素没有被选出.所以选出个元素方式数等于选出个元素方式数，即.证毕式(1.8)证实也可由公式(1.7)得出，实际上

推论2

（Pascal公式）(1.9)

证实：

证毕.

第2页这个公式也可用组合分析方法论证：

在集合个元素中固定一个元素，不妨设为，于是，从个元素中取个元素组合就有下面两种情形组成：1)个元素中包含，这能够从除去个元素中取个元素组合，然后将加入而得到，其组合个数为.2)个元素中不包含，这能够从除去个元素中取个元素组合而得到，其组合个数为.

由加法法则即得

利用式(1.9)和初始值，对全部非负整数可计算出一张三角形阵列(P8)，通常称这个三角阵列为杨辉三角形或Pascal三角形.

值得注意是，假如仔细考查表，能够发觉组合中一些关系式及其一些有趣性质.

推论3(1.10)

证实：重复应用Pascal公式轻易得到式(1.10).第3页[例1]在一个平面上有42个点，且没有任何三个点在同一条直线上.经过这些点能够确定多少条不相同直线？能够组成多少个位置不相同三角形？

解：因为没有三个点在一条线上，故每两个点可确定唯一一条直线.故有条不一样直线.

又因为任意三点能够组成一个三角形，故有个位置不一样三角形.[例2]数510510能被多少个不一样奇数整数？

解：因为510510=2·3·5·7·11·13·17，其中除2是偶数外都是奇数.于是要整除510510奇数只能是除2以外奇素数之积，而且在一个积中一个奇数至多出现一次.奇素数之积分下面几个情况讨论：

只包含一个奇素数，一共有个

包含两个奇素数，一共个

包含三个奇素数，一共个

包含四个奇素数，一共个

包含五个奇素数，一共个

包含六个奇素数，一共个

于是，由加法法则知总共有6+15+20+15+6+1=63个.

故510510能被63个不一样奇数整除.第4页上面，我们研究了从个不一样元素中选取个不一样元素组合.下面我们考虑从个不一样元素中，允许重复地从中选取个元素组合，这就是重复组合.

定义1.5从重集中选取个元素不考虑次序组合起来，称为从中取个元素重复组合.用表示从中取个元素重复组合种数.

比如，则都是2组合.

在集合中，若，则由下面定理.

定理1.6

-组合数为(1.11)证实：设个元素和自然数一一对应.于是所考虑任何组合便可看成是一个个数组合，因为是组合，不妨认为各是按大小次序排列.相同连续地排在一起.如按排列.

又令，即.

因为最大可取，故最大可取.这么就得到一个集合

-组合.易见有一个取法便有一个取法.而这两种取法有一一对应关系，从而这两个组累计数问题时等价.这么一来，允许重复从个不一样元素中取个元素组合数和不允许重复从个不一样元素中取第5页个元素组合数是相同.故有

证毕.注意，在定理1.6中，假如不一样元素重复数最少是，则结论仍成立.[例3]试问有多少项？

解：展开式相当于从每一个右边括号里取一项相乘，可对应于有4个无标志球，放进3个有标志盒子，一盒可多于1个球比如能够看作4个球全部放在标为盒子.又比如能够看作盒有两个球，盒子各一个球.

所以问题等价于从3个元素中取4个作允许重复组合，其组合数为

共15项.第6页[例4]求个无区分球放入个有标志盒子里而无一空盒方式数.

解：因为每个盒子不能为空，故每个盒子中可先放一球，这么还剩个球，再将这个球放入个盒子中去，因为这时每盒球数不受限制，这相当于从重集中取个元素组合，由式(1.11)知，其组合数为[例5]在由数0,1,…,9组成位整数所组成集合中，假如将一个整数重新排列而得到另一个整数，则称这两个整数是等价.那么，1)有多少不等价整数？2)假如数字0和9最多只能出现一次，又有多少不等价整数.

解：1)由两个整数等价定义可知，一个位整数只和所取数字相关，而与这些数字次序无关，故这时一个组合问题.而且每一整数中每一位可从数第7页字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加入，其个数为由加法规则知，符合题意要求不等价整数个数为

第8页[例6]求方程非负整数解个数，其中为正整数.

解：设为个不一样元素，于是重集任何一个-组合都含有形式，其中是非负整数且满足方程.反之，对于每个满足方程非负整数解都对应于重集一个-组合.于是，方程非负整数解个数就等于重集-组合数.不相邻组合

所谓不相邻组合是指从取个不相邻数组合，即不存在相邻两个数和组合.比如，有组合.

定理1-3从中取个作不相邻组合，其组合数为

证实：设是一组不相邻组合，假定，令，则有

，即为从中取个作不允许重复组合，假定.反之，，从中取个作不允许重复组合，假定，则第9页则，而且故是从取个作不相邻组合.若，则不存在这么组合.

后面我们在讨论容斥原理时会讲到对夫妻问题，会用到这个结论.组合生成

组合生成比排列要简单些，试从1,2,3,4,5,6,7中取3个作组合得以下一组，从中找出生成规律.123,124,125,126,127234,235,236,237345,346,347456,457567134,135,136,137245,246,247356,357467145,146,147256,257367156,157267167

已知为一组不允许重复组合，不妨假定，.而且存在

使，不然已到最终一组，不存在后续组合.

下面