2012江苏省数学竞赛《提优教程》教案：第57讲排列与组合.doc

第 讲 排列与组合本节主要有：排列组合公式及应用；处理排列组合问题的常用方法：如插空法、捆绑法等；可重复排列及圆排列公式等基本内容A类例题例1四个不同的小球放入编号1、2、3、4、的四个盒中，则恰有一个空盒的放法有_种。分析 排列组合中诸如把教师医生分到各所学校；把不同的小球放入盒中等问题都可以归类为分组问题，分组问题解题的原则是：“分组先分堆”解 把4个球分成“2、1、1”三堆，有种分法，把三堆球分别放入四个盒子的任三个中，有种放法，由乘法原理，恰有一个空盒的放法共有=144种说明：本题也可以分类讨论求解，若1号盒空，2号盒放二个球，3、4号盒各放一个球有=12种放法；同理，若1号盒空，3号盒放2个球，2、4号盒各放一个球也是12种放法；1号盒空，4号盒放2个球，2、3号盒各放一个球同样是12种放法。所以，1号盒空共有123 = 36种放法。故满足题设的总放法种数为436 = 144种。例2 6名同学排成一排。（1）其中甲、乙两个必须排在一起的不同排法有_种.(1997年全国高考题)（2）甲乙两人不能相邻的排法有_种分析 排列组合中，处理“在与不在”、“邻与不邻”、“接与不接”等问题时，常常利用捆绑法或插空法解把甲、乙两人看作1人，这样6个人可看成5个人，共有种排法，甲、乙两人有2种顺序，故共有种 先排其他4名同学，有种，再把甲乙两人插入到4名同学的5个空挡中有种，所以共有=480种情景再现13名医生和6名护士被分配到3所学校为学生体检，每校分配1名医生和2名护士，不同的分配方式共有 （ ）A90种 B180种 C270种 D540种 (1998年全国高考题)2某校从5名优秀学生干部中选出4人分别参加“资源”、“生态”和“环保”三个夏令营，要求每一个夏令营活动至少有选出的一人参加，且每人只参加一个夏令营活动，则不同的参加方案有（ ）种A90 B180C270 D540 B类例题例3 在正方体的8个顶点，12条棱的中点，6个面的中心及正方体的中心共27个点中，共线的三点组的个数是 A 57 B 49C 43 D 37(1998年全国数学联赛)分析 正方体中，共线三点组的两个端点可能有三种情形：两端点都是顶点；两端点都是面的中心；两端点都是棱的中点，除此之外没有别的情形解 两端点都是顶点的共线组有个，两端点都是面的中心的共线组有3个，两端点都是棱的中点的共线组有个。所以满足条件的共线组共有49个说明：分类讨论是解决较复杂的排列组合问题的常用思想，分类讨论的关键是找到合适的分类标准，做到不重不漏。例4 某城市在中心广场建造一个花圃，花圃分为6个部分（如右图所示），现要栽种4种不同颜色的花，每部分栽种一种且相邻部分不能栽种同样颜色的花，不同的栽种方法有_种. （2003年江苏高考题）分析 本题是近几年出现的排列组合问题中难度最大的问题之一。基本思想是运用分步记数原理。解 如图所示，把花坛视为一个圆环，先排区域1，有种.由于1与其余5个位置均相邻，故其余5个位置共有3种颜色可选由任两个相邻位置不能同色，故必有2种颜色各种两块地，第一种颜色只有一块地，有种方法，另两种颜色种4个位置，只有两种选择，故共有种.例5在某次乒乓球单打比赛中，原计划每两名选手恰比赛一场，但有3名选手各比赛了2场之后就退出了，这样，全部比赛只进行了50场。那么，上述3名选手之间的比赛场数是A0 B1 C2 D3 （1999全国联赛）分析 3名选手共比赛了6场，设他们之间比赛了x场，故只有这3名选手参加的比赛共6x场解 设三名选手之间的比赛为x场，共有n名选手参赛，由题得50 = ,即 ，由于0x3，经检验知，仅当 x= 1时，n = 13为正整数，故选B说明 求解简单的二元一次不定方程时，可逐个代入检验是否满足题设.例6 四面体的顶点和棱的中点共10个点，取4个不共面的点，不同的取法有 （ ）A150种 B147种 C144种 D141种分析 从所有的取法中减去共面的取法。其中4点共面的情形有三类：第一类，取出的4个点位于四面体的同一个面内有种；第二类，取任一条棱上的3个点及该棱对棱中点，共6种；第三类，由中位线构成的平行四边形，两组对边分别平行于四面体相对的两条棱，有3种解 由上述分析知共有种说明 “排除法”是常用方法之一，其难点在于排除那些不合条件的组合。情景再现3如图，点p1，p2，p10分别是四面体顶点或棱的中点。那么，在同一平面上的四点组(p1，pi，pj，pk)(1 i 1，且由于增加了n个同学而又多写了74封信，则原有同学的人数m = _.C类例题例7 8个女孩和25个男孩围成一圈，任何两个女孩之间至少站两个男孩，问共有多少种不同的排列方法（只要把圈旋转一下就重合的排法认为是相同的）.（1990年全国联赛）分析 以1个女孩和2个男孩为一组，且使女孩恰好站在两个男孩中间，余下的9个男孩和这8个组被看成是17个元素，显然这17个元素任意的圆排列是满足题意的解 先从25个男孩中选出9个男孩共有种可能。其次，上述17个元素的圆排列数为种. 再次，分在8个组内的16个男孩在16个位置上的排列是，所以总的排列方法数为：链接 1在A=a1，a2，an的n个元素中，每次取出r个元素排在一个圆环上，叫做一个圆排列，圆排列有三个特点：第一，无头无尾；第二，按同一方向旋转后仍是同一圆排列；第三，两个圆排列只有在元素不同或者元素相同，但元素之间的顺序不同，才是不同的圆排列.2圆排列计数公式：从n个元素中取r个不同的元素进行圆排列，圆排列数为特别地，当r = n时，圆排列数为(n-1)！3项链问题：从n个相异的珠子中，每次取出r颗穿成一个项链，因其正反相对的两个圆排列在穿成一个项链的完全相同，故项链数为例8 试求从集合A=1，2，n到集合B=1，2，m的映射的个数.分析 在两个集合之间建立映射本质上是给集合A中的元素分步找象解 给A中元素分别找象，元素1有m种找法，元素2有m种找法，元素n有m种找法，故从A到B的映射的个数为mn链接：允许元素重复出现的排列，叫做可重复排列，在m个不同的元素里，每次取出n个元素，元素可重复出现，按一定的次序排成一排的排列数为mn. 例9 整数1，2，n的排列满足：每个数或者大于它之前的所有数，或者小于它之前的所有数. 试问有多少个这样的排列？（第21届加拿大中学生数学竞赛）分析 由特殊到一般，找出递推关系式解 记所求的排列的个数是an.显然，a1 = 1.对于n2，考虑最大的数n，如果n排在第i位，则它之后的（n i）个数排序完全确定，即只能是n i，n i 1，1；而它之前的(i-1)个数有ai-1种排法，考虑到n的所有不同的位置，由加法原理知an = 1 + a1 + a2 + + an-1，于是，an-1 = 1 + a1 + a2 + + an-2.有an = 2an-1，又a1 = 1故an = 2n-1情景再现7某城市有7条南北向的街，5条东西向的街，如果从城市的O点走向A点，最短的走法有多少种？8用6个白珠、8个黑珠、一个红珠串成一串，问共有多少种不同的串法？9有数学、物理、文学3个课外活动小组，6个同学报名，每人限报一组，一共有多少种报名的方法？ 习题17 A18次射击，命中3次，其中恰有2次连续命中的情形共有_种。（1998年湖南联赛）22名医生和4名护士被分配到2所学校为学生体检，每校分配10名医生和2名护士，不同的分配方法共有 （ ） A6种 B12种 C18种 D24种 （1998年全国高考题）3如图，一个地区分为5个行政区域，现给地图着色，要求相邻区域不得使用同一颜色，现有4种颜色可供选择，则不同的着色方法共有_种。4正六边形的中心和顶点共7个点，以其中3个点为顶点的三角形有_个。5n个后乒乓球运动员(n4)，每两个人都可以组成一对双打选手，从中选出两对的选法有 （ ） A3种 B6种C3种 D(6+3)种6已知两个实数集合A=a1，a2，a100与B=b1，b2，b50，若从A到B的映射f使得B中每个元素都有原像，且f(a1) f(a2) f(a100)，则这样的映射共有（ ）个A B C D B7在一个正六边形的六个区域种观赏植物，如图，要求同一块中种同一植物，相邻的两块种不同的植物，现有4种不同的植物可供选择，则有_种栽种方案.8在1，2，3，4，5的排列a1，a2，a3，a4，a5中，满足条件a1 a3，a3 a5的排列个数是 （ ） A8 B10 C14 D169“渐升数”是指每个数字比其左边的数字大的正整数，如34689，已知有个五位“渐升数”，若把这些数按从小到大的顺序排列，则第100个数是_。10把1996个不加区别的小球放在10个不同的盒子里，使得第i个盒子中至少有i个球（i1，2，10），问不同放法的总数是多少？C11用六种不同颜色中的几种染一个正方体各面，要求相邻两面不同色，问有多少种不同染色法？（两个染色正方形，如能通过转动、翻身使二者各面颜色对应相等，则认为是相同染色法）（1996年全国联赛）124对夫妇去看电影，8人生成一排，若每位女性的邻座只能是丈夫或另外的女性，共有多少种坐法？本节“情景再现”解答：1ACC540种 2先选出4人有C种选法，把4人分成“2，1，1”三堆，有种分法，共有CA180种。3首先，在每个侧面上除P1点外尚有五个点，其中任意三点添加P1后组成的4点组都在同一平面，这样的三点组有C个，三个侧面共有3 C个。其次，含P1的每条棱上的三点组添加底面与它异面的那条棱上的中点组成的四点也在一个平面上，这样的四点组有3个，故共有3 C333个。4分别以S1、S2、S3、S4依次记OAB、OBC、OCD、ODA，显然，若不考虑相邻三角形不同色的要求，则共有44256种涂法。下面先对S1和S3涂色i）S1和S3同色，它们共有4种选择，对每一对选择，S2和S4各有3种选择，所以此时共有43336种不同涂法。ii）S1和S3不同色，它们共有C12种选择，对每一种选择，S2和S4各有3种选择，所以此时共有122248种不同涂法。所以相邻三角形均不同色的四边形出现的概率为5设胜x场，平y场，则负（15xy）场，得3xy33，又y333x0 x11，且xy15，共有；三种情形。6由题得CC74 即74，即n(2mn1)1482237，由于n与2mn1有不同的奇偶性，故只能解得n4，2m337有m17整数解。7每条东西向的街被分成6段，每段不妨都用相同的a表示，共有6个a。每条南北向的街被分成4段，用4个b表示，含有6个a和4个b的一种全排列，对应于从0到A的一种走法。例如排列aaabaabab，对应于上图中箭头所示的走法，故走法有210种。8这是一个圆排列问题，如固定红珠，则为线排列，故除红珠外其余的14个珠子共有N13003种串法，14个珠子关于红珠对称或不对称有两种情形：对称共有N235种；不对称有N3N1N22968种，又同色珠子换位后的相同的串法是重复的串法，因此关于红球不对称的串法有N4N31484种，所以共有NN2N41519种不同串法。9可重复排列，共有36729种报名方法。习题解答1把两次连续命中与一次命中的情形看成2个元素插入可知共有30种。或用穷举法把满足条件的情形一一列举出来2B分组先分堆3先排1区，有4种方法，再排2区，有3种方法，如果3、5两区同色，则4区有2种方法，否则4区只有一种方法。另外3、5两区本身还有两种选择，故共有43(12)272种。4用“排除法”，从7个点中任取三点有C种取法，其中3个点在一直线上的有3个，故共有C332个。5n个运动员两两配对有对，从中选出两对共有C3C。6不防设b1b2b50，把A中元素a1，a2，a100按顺序分为非零的50组，定义映射f：AB，使第i组的元素在f之下的像都是bi（i1，2，50），易知这样的f满足题设，每个这样的分组都一一对应满足条件的映射。于是，满足条件的映射f的个数与A按下标顺序分为50组的分法数相等，而A的分法数为C，则这样的映射共有C个。7考虑A、C、E种同一种植物，此时共有4333108种，考虑A、C、E种二种植物，此时共有343322432种方法，考虑A、C、E种三种植物，共有P222192种方法。故总计有108432192732种方法。8由a1a3，a3a4，a4a5可知，要么a25，要么a45（a1、a3、a5不可能是最大者），且a23，a43，a33。若a25，则a44或3。当a44时，有3！6种，当a43时，有2！2种，这时共有628种；同理当a45时，也有8种，故共有16种。9前3位数是123的五位“渐升数”共有5432115个数。同理，前3位数分别是124，125，126，127的五位“渐升数”分别有10，6，3，1个。即前两位数是12的五位渐升数有35个，类似可得前两位数是13，14，15，16的五位“渐升数”分别有20个，10个，4个，1个。从而首位是1的五位“渐升数”共有3520104170个。同理，前两位数是23的五位“渐升数”共有1063120个。前2位是24的五位“渐升数”共有63110个。所以第100个“渐升数”是24789。10先在第i盒里放入i个球（i1，2，10）这时共放了1231055个球，还余下1941个球，转化为把1941个球放入10个盒子中（有的盒中不放球），有C种放法。11分四种情形讨论：1有3 6种颜色，将一种颜色染下底，则上底有5种染法，按圆排列，其余4个侧面有3！种染法，共有53！30种