竞赛中的排列组合问题 程乐根.pptVIP

竞赛中的排列组合问题安庆一中程乐根 一、出题情况 排列组合出题，主要在第一试中出题，大多以客观题形式呈现，但这一内容是抽象数学的基础，渗透性很强，在其它分支里用得很多，特别是在组合数学和数论中应用更为广泛。 二、常见定义公式： 1、排列 从n个不同元素中，任取m个不同元素的排列数是: 2、组合 从n个不同元素中，任取m个不同元素的 组合数是： 3、重复排列 从n个不同元素中，取m个元素（可以重复）的排列数是　（ｍ个位置按顺序依次来占即可得结论） 4、圆排列 从n个不同的元素中任取m个不同的元素，仅按元素之间的相对位置而不分首尾排成一个圆圈，这种排列称为n个不同元素m的圆排列。其排列数是 当m=n时，排列数为（n-1）! 5、不全相异元素的全排列 如果n个元素中，有p个元素相同，又有q个元素相同，???，又有r个元素相(p+q+??? + r=n), 这n个元素全取的排列叫做不全相异元素的全排列。它的排列数是 6、重复组合 从n个不同元素中任取r个元素允许重复出现的组合称为n个不同元素的r的可重复组合。其组合数是 7、错位排列 若｛1，2，? ? ?n ｝的一个排列为｛ ｝ 满足 则称 ｛ ｝为｛ 1，2，? ? ? n｝的一个错位排列 其所有的错位排列数为： n!（ ） 三、例题讲解 例1、数1447，1005和1231有某些共同点，即每个数都是首位为1的四位数，且每个四位数中恰有两个数字相同，这样的四位数共有多少个？ 解：符合条件的四位数必有两个1或一个1 。 （1）两个1的情形：从除1之外的其余9个数字中任取两个有 种取法再与其中一个1组成任意排列的三位数有 种，这样构成的首位是1的四位数共有 =216个。 （２）只有一个１的情形：从其余的９个数字中任取两个有　　种，其中一个数字被重复选出　种，这样的三个数字组成的三位数有　　种（另一个不重复的数字可放在3个位置上），于是构成的首位为１的四位数有： 　　　　　个。 　　因此符合题意的共有４３２个。　　　　　　　　　　　 点评：占位有序，不易混淆 例２、从１，２，３，４，? ? ? ４９中取出六个不同的数字，其中至少有两个是相邻的取法种数是多少？ 解：设　　 是取自1，2，﹒ ﹒ ﹒，49个不同中的六的数。不妨设 ，显然 ， 且 互不相同的充要条件是 不含相邻的数。 作六元数组（ ）对应于 （ ），则在取自1至49之间的六个不同且没有相邻的数构成的六元数组集合与所有取自1至44之间的六个不同的数构成的六元数组集合之间建立了一一对应。因此这两个集合中六元数组的个数都等于 ，而1至49之间六个不同的数构成的六元数组的个数为 ，于是，其中有相邻数的六元数组的个数为 。 点评：间接作差，化烦为易 例3、集合A,B的并集A∪B={ },当A≠B时，（A,B）和（B,A）视为不同的对，则这样的（A,B）对的个数有多少？ 解：若A= { }时,则满足题意的B有 个，即A的任何子集都可以为B,此时的配对个数是8. 若A= { }时,则满足题意的B可以由{ }的子集再加上元素 构成，此时 的配对个数是 =4；同理，当A= { }或{ }时，则相应的配对个数也为4个。故当A中有两个 元素时配对个数是3×4=12. 若A中有一个元素时，另两个元素必须在B中，故B只有2种可能（A中元素属于B或不属于B