竞赛数学 排列组合 讲义-北京清北学堂.pdf

《竞赛数学 排列组合 讲义-北京清北学堂.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、排列组合几种特殊的排列、组合圆排列定义1：从几个元素中任取r个不同元素仅按元素之间的相对位置而不分首尾排成一个r圆圈，这种排列称为n个不同元素的r——圆排列。r——圆排列数记为K.nrPrn定理1：K.nr证：对n个不同元素取r个的任一圆排列，均有r种不同的方式展开成r个不同的直线rr排列，且不同的圆排列展开的直线排列也彼此不同，故有r·K=P，得正.nn重复排列定义2：从n个不同元素中允许重复的任取r个元素排成一列，称为n个不同元素的r——可重复排列.r定理2：n个不同元素的r——可重排列数为n.证：在按顺序选取的r个元素中，每个元素都有n种不同的选法，故由乘法原理有，其r排列数为n.

2、不全相异元素的全排列定义3：设n个元素可分为k组，每一组中的元素是相同的，不同组间的元素是不同的，其中第i组的元素个数为n(i=1,2,.....,k),n+n+.....+n=n.则这n个元素的全排列i12k称为不全相异元素的全排列.n!.定理3：n个元素的不全相异元素的全排列个数为.n!n!n!12k证：先把每组中的元素看做是不相同的，则n个不同元素的全排列数为n!，然后分别将每个组的元素还其本来面目看成是相同的，则在这n!个全排列中，每个排列都重复出现n!.了n!n!……n!次，所以不全相异元素的全排列数.12kn!n!n!12k多组组合定义4：将n个不同的元素分成k组的组合称为

3、n个不同元素的k——组合.定理4：对于一个n个不同元素的k——组合，若第i组有n个元素（i=1,2,…，k），in!.则不同的分组方法数为.n!n!n!12k重重组合定义5：从n个不同元素中任取r个允许元素重复出现的组合称为n个不同元素的r——可重组合.枚举法所谓枚举法就是把集合A中的元素一一列举出来，从而计算出集体A的元素个数。它是最基本，也是最简单的计算数方法。应用枚举法计数的关键在于一一列举集合中的元素时必须做到既不重又不漏。分类计数原理与分步计数原理分类计算原理完成一件事，有几种方式，第一种方式有m种方法，第二种方式有n种方法，……最后一种方式有r种方法.不管采取哪一种方法都能完

4、成这件事，则完成这件事的方法总数为m+n+.....+r.分步计数原理完成一件事，有几个步骤，第一步有m种方法，第二步有n种方法，…，最后一步有r种方法，要完成这件事，必须通过每一步，则完成这件事的方法总数为m·n……r.应用分类计数原理的关键在于分划，即把一个所要计数的集合S分划成一些两两不交的小集合，且使每个小集合都便于计数.应用分步计数原理的关键在于分解，即把一个所要计数的集合S分解成若干个集合的乘积.对一个集合S的分划或分解，没有一般方法，应由具体问题而定，而这正是应用两个原理解题的难点与技巧所在.递推方法将与正整数有关的数字问题，通过寻求递推公式，或通过递推公式，而使问题得到解决

5、的方法，叫做递推方法.递推方法几乎对所有数学分支都具有重要的作用，当然对组合计数就更不例外了，它是组合计数的常用方法.组合恒等式rnrCCnnr1r1rCCCn1nnrnr1CCnn1rrmmrmCCCCnnnnm012nnCCCC2nnnn0123nnCCCC(1)C0nnnnn组合恒等式的证明方法有：①恒等变形，变换求和指标；②建立递推关系；③数学归纳法；④考虑组合意义；⑤母函数.组合不等式组合不等式以前我们见的不多，在其他一些书籍中组合不等式的著述也很少，设A是一个有n个元素的集合，A的m个子集A,A,.....,A两两互不包含

6、，试证：12mm1（1）

7、A

8、1;CIi1nm（2）C

9、AI

10、m2ni1其中

11、A

12、表示A所含元素的个数，C

13、AI

14、表示n个不同元素取

15、A

16、的组合数.iini我们有必要研究组合不等式的证明方法.组合不等式的证明方法有：在集合间建立单射，利用集合阶的不等关系定理，设X和Y都是有限集，f为从X到Y的一个映射，（1）若f为单射，则

17、X

18、≤

19、Y

20、；（2）若f为满射，则

21、X

22、≥

23、Y

24、.利用容斥原理n例如：设元素a属于集族{AA12,,,Ak}的k个不同集合Ai1,Ai2,,Aik，则在

25、Ai

26、i12中a被计算了k次，当k≥2时，集合A,A,,A两两的交集共有C个.由于i1i2ik

27、k2k(k1)Ckk1,故a在

28、AiAj

29、中至少少被计算了k－1次，这样我们得到下21ijn面的不等式：nn

30、Ai

31、

32、Ai

33、

34、AiAj

35、i1i11ijn组合不等式（*）可由容斥公式：nnn(n1)

36、Ai

37、

38、Ai

39、

40、AiAj

41、(1)

42、Ai

43、删去右边第三个和式起的所有i1i1i11ijn和式得到.采用这种办法，我们可以从容斥公式得到另外一些组合不等式