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

《竞赛数学 排列组合 讲义-北京清北学堂》由会员分享，可在线阅读，更多相关《竞赛数学 排列组合 讲义-北京清北学堂（9页珍藏版）》请在金锄头文库上搜索。

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

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

3、素的全排列数.!.21knnnn 多组组合多组组合 定义定义 4：将n个不同的元素分成 k 组的组合称为n个不同元素的 k组合. 定理定理 4：对于一个n个不同元素的 k组合，若第i组有in个元素（i=1, 2, ，k） ，则不同的分组方法数为.!.21knnnn 重重组合重重组合 定义定义 5：从n个不同元素中任取r个允许元素重复出现的组合称为n个不同元素的 r可重组合. 枚举法枚举法 所谓枚举法就是把集合 A 中的元素一一列举出来，从而计算出集体 A 的元素个数。它是最基本， 也是最简单的计算数方法。 应用枚举法计数的关键在于一一列举集合中的元素时必须做到既不重又不漏。 分类计数原理与分步

4、计数原理分类计数原理与分步计数原理 分类计算原理 完成一件事， 有几种方式， 第一种方式有m种方法， 第二种方式有n种方法， 最后一种方式有r种方法.不管采取哪一种方法都能完成这件事， 则完成这件事的方法总数为m+n+.+r . 分步计数原理 完成一件事， 有几个步骤， 第一步有m种方法， 第二步有n种方法， ，最后一步有r种方法，要完成这件事，必须通过每一步，则完成这件事的方法总数为 mnr. 应用分类计数原理的关键在于分划， 即把一个所要计数的集合S分划成一些两两不交的小集合，且使每个小集合都便于计数. 应用分步计数原理的关键在于分解， 即把一个所要计数的集合S分解成若干个集合的乘积. 对

5、一个集合S 的分划或分解，没有一般方法，应由具体问题而定，而这正是应用两个原理解题的难点与技巧所在. 递推方法递推方法 将与正整数有关的数字问题，通过寻求递推公式，或通过递推公式，而使问题得到解决的方法，叫做递推方法. 递推方法几乎对所有数学分支都具有重要的作用，当然对组合计数就更不例外了，它是组合计数的常用方法. 组合恒等式组合恒等式 0) 1(232102101 111 1 n nn nnnnnn nnnnmr mnm nm nr nr nr nr nr nr nrn nr nCCCCCCCCCCCCCCrnCCCCCC组合恒等式的证明方法有： 恒等变形，变换求和指标； 建立递推关系； 数

6、学归纳法； 考虑组合意义； 母函数. 组合不等式组合不等式 组合不等式以前我们见的不多，在其他一些书籍中组合不等式的著述也很少， 设 A 是一个有n个元素的集合，A 的m个子集12mA ,A ,.,A两两互不包含，试证： （1）miA nIC1|; 11（2）miA nmCI12|其中|Ai|表示 Ai所含元素的个数，|IA nC表示 n 个不同元素取|Ai|的组合数. 我们有必要研究组合不等式的证明方法.组合不等式的证明方法有： 在集合间建立单射，利用集合阶的不等关系在集合间建立单射，利用集合阶的不等关系 定理，设X和Y都是有限集，f为从 X 到 Y 的一个映射， （1）若f为单射，则|X|

7、Y|； （2）若f为满射，则|X|Y|. 利用容斥原理利用容斥原理 例如： 设元素 a 属于集族12,kA AA的k个不同集合 kiiiAAA, 21， 则在niiA1|中 a 被计算了k次，当k2 时，集合 kiiiAAA, 21两两的交集共有2 kC个.由于 |, 12) 1(12 j njiikAAakkkC 在故中至少少被计算了k1 次，这样我们得到下面的不等式： |111j njiiiniiniAAAA 组合不等式（*）可由容斥公式： |) 1(| 1)1(111inin j njiiiniiniAAAAA 删去右边第三个和式起的所有和式得到. 采用这种办法， 我们可以从容斥公式得到

8、另外一些组合不等式， 只是要注意这些不等式的方向的变化. 利用抽屉原则利用抽屉原则 由于抽屉原则的结论本身就是组合不等式关系， 所以我们利用抽屉原则， 巧妙构造抽屉的方法证明组合不等式. 利用组合分析利用组合分析 在复杂的组合计数问题、离散极值问题等问题中，会出现一些组合不等式，这时可运用组合分析方法证明之. 经典例题 1.数 1447，1005 和 1231 有某些共同点，即每个数都是首位为 1 的四位数，且每个四位 数中恰有两个数字相同，这样的四位数共有多少个？ 【解】符合条件的四位数必含有一个 1 或者两个 1. （1）含有两个 1 的情形 从除 1 之外的其余 9 个数字中任取两个，有

9、2 9C种取法，再与其中的一个 1 组成任意排列的三位数，有3 3P种，这样构成的首位为 1 的四位数共有2 19NC3 3P（个）. （2）只含有一个 1 的情形 从其余的 9 个数字中任取两个，有2 9C 种取法，其中一个数字被重复选出，有1 2C种，这样的三 个数字组 成的三位 数共有23 3P，这样构成 的首位为 1 的 四 位 数 共 有23 31 22 9 2PCCN（个）. 因此，符合题意的四位数共有12432NNN（个）. 2. 证明： nknk nnnnC012 2!2)!2(2 【分析】 把 nnkk nnnkk nnkk nnkk nCCCC212212202 02,而对

10、于变形为，变换求和指标. 【证明】knjCCCCCnnkk nnnkk nnnnkk nnkk nnkk n 2,22122122212202 02令对于和式，则.2 02 022102212n nnkk nnjn nj nnjj nnnkk nCCCCCC 所以.22 02202n nnkk nnnkk nCCC 即 n nnnkk nCC220222 ，从而有 nknk nnnnC012 2!2)!2(2. 3. （2003 年上海交大冬令营）求证：.,) 1(1 11) 1(31 21 11210NnCnmCnmCmCmCmn nmn nn nnn其中证明证明 设n nn nnnnCnm

11、CmCmCma11) 1(31 21 11210 ，则由基本恒等式r nr nr nr nr nCnrCCCC 11 11及得 .1) 1()() 1()(31)(21 111 11 2 21 11 1 12 10 11 10 n nn n nn nnnnnnnnCnmCCnmCCmCCmCma.) 1(1 ) 1)(2()(1(!,) 1)(2(1 21 11,)3()(1(!)(1() 1( 1.1,1112111n nmnnnnnnnnnnCnmmmnmnmnammmmaamnmnmnanmnmnnanmnaaanmaanmaa从而有而所以即故【说明】注意到 an中各项的系数均与 n 无

12、关，且符号正负相同，由此想到 an与 an1 之间必定存在着某些联系，且是递推关系. 4. 设,212211nnBBBDAAAD是集合 M 的两个划分，又对任何两个不变的子集),1 (,njiBAji有,|nBAji求证：2 21|nM 并说明等号能否成立？ 【证明】令,1|,| |,min|njiBAkji，不妨设,|kAi因nBBB,21两两不交，故nBBB,21中至多有k个,jB使1jAB 1jAB., 2 , 1,knmj 由k的选取知), 2 , 1(|mjkBj从而.|1mkBmjj又因 1jAB ., 1,nmi 故 ,|11nBABAii 即 .|knBi 所以 )(|111k

13、nmnmkBBBMnmjjmjjnjj).2()(knmknn 若,2nk 因, km 故 .2)2(2)2(2)2()()2()(|2 22nknnknkknnknmknnM 若,2nk 则), 2 , 1(2|ninAi 从而 .2|211nAAMniinii 下面说明 2|2nM 是可以取到的.显然这时n为偶数，取, 4n则8|M， 令,8 , 7 , 6 , 5 , 4 , 3 , 2 , 1M易验证 M 的两个划分. 11,23,45,67,8, 21,23,54,67,8,DD 满足题目条件. 5. 某市有n所中学，第 I 所中学派出iC名学生（niCi1 ,391）来到体育馆观看

14、球赛，全部学生总数为niiC11990，看台上每一横排有199个座位，要求同一学校的学生必须坐在同一横排. 问体育馆最少要安排多少横排才能保证全部学生都能坐 下？ 【解】让学生按学校顺次入坐，每排坐满后再转入下一排，共用10排. 这时有的学校学生 已坐在同一排，有的学校学生坐在两排. 后一种学校至多9个. 再增加两排座位，每 排可容纳5个学校. 将上述（至多）9个学校移到这两排，则每个学校的学生都坐在 同一排，因此，12排足够. 另一方面，1990=34 58+18. 如果58个学校各有34名学生，1个学校18名学生， 那么每排至多安排34名学生的学校5所（34 6199） ，11排至多安排34名学生的 学校55所，所以11排是不够的. 6. 对n nnCn42:, 22 2求证. 【证明】 构造集合2 22121,nnnnCaaaaaA则表示从A中取n个元素的组合数，即由n个元素组成的 A 的真子集有n nC2个，而 A 的所有子集数是 nnn nnnnCCCC4222 22 21 20 2个， 故有nn nC42 又设集合,211naaa