排列组合问题

排列组合问题 1有五对夫妇围成一圈，使每一对夫妇的夫妻二人动相邻的排法有（ ） A 768种 B 32种 C 24种 D 2的10次方中 解： 根据乘法原理，分两步： 第一步是把5对夫妻看作5个整体，进行排列有54321120种不同的排法，但是因为是围成一个首尾相接的圈，就会产生5个5个重复，因此实际排法只有120524种。 第二步每一对夫妻之间又可以相互换位置，也就是说每一对夫妻均有2种排法，总共又2222232种 综合两步，就有2432768种。 2 若把英语单词hello的字母写错了,则可能出现的错误共有 ( ) A 119种 B 36种 C 59种 D 48种 解： 5全排列5*4*3*2*1=120 有两个l所以120/2=60 原来有一种正确的所以60-1=593、“IMO”是国际数学奥林匹克的缩写，把这3个字母用3种不同颜色来写，现有5种不同颜色的笔，问共有多少钟 .分析：从5个元素中取3个的排列：P（5、3）=543=604、一个正方体，用6种颜色涂面，面与面之间颜色不同，问有多少种涂法？如果改为相邻面 .第一问：首先要明确什么叫正方体面相同。因为任何一个都有可能为底面，确定底面，确定顶面再确定侧面是解这题的关键先选一个颜色定一个底面，比如用色1，5种颜色选一个在顶面 5中情况 4种颜色排成一圈是（4-1）！ 6种情况5*6 =30第二问6种颜色都用：这个就与第一问相同了，完全是等价的问题，所以是30种。只用5种颜色：先选定5种颜色C（5,6），然后只用5种颜色意味着有两面的颜色相同，那么这两面必然是相对着的，我们优先考虑这两面。那么相同的这两面的颜色共有5种选法。然后剩下4个面，注意此时这4个面不再是6种颜色都用的情况下的3！了，因为前面说了有两面颜色一样，这样种数变成3！/2=3种。所以一共C（5,6）*5*3=90种。只用4种颜色：先选4种颜色：C（4,6）=15种，然后必须有两对面是相同的，C（2,4）=6种，那么剩下两个面就确定了，而且本来剩下两个面应该是有两种情况，但由于对称，导致情况唯一，所以一共15*6=90种。只用3种颜色：先选3种颜色：C（3,6）=20种，然后必然是3对面颜色相同，所以情况唯一。因此是20种。综上：30+90+90+20=230种。从6名志愿者中选出4人分别从事翻译、导游、导购、保洁四项不同的工作，则选派的方案有几种解答：6543=360（种）小升初专题系列之排列组合知识点来源：本站原创 文章作者：匿名 2009-08-17 14:49:02标签：排列组合 小升初奥数精华资讯 免费订阅解排列问题和组合问题时，当问题分成互斥各类时，根据加法原理，可用 分类法；当问题考虑先后次序时，根据乘法原理，可用位置法；这两种方法又称作直接法 当问题的反面简单明了时，可通过求差排除采用间接法求解；另外，排列中相邻问题可 以用捆绑法；分离问题可能用插空法等 解排列问题和组合问题，一定要防止重复与遗漏 互斥分类-分类法 先后有序-位置法 反面明了-排除法 相邻排列-捆绑法 分离排列-插空法 课后习题：1.用0、1、2、3、4、5、6、7、8、9组成数字不重复的九位数，求符合要求的九位数的个数？2. 9个人坐成一圈，问不同坐法有多少种？3. 今欲从 1，2，3，8，9，10，12诸数中选取两数，使其和为偶数，问共有几种选法？4. 小明去商店买球，足球有3种不同的牌子，排球有4种牌子篮球有5种牌子，羽毛球有6种牌子，如果小明买3种球，每种一个，一共有多少 种不同的选择方式？5. 一个四面体的顶点和各棱的中点共10个点，取其中4个点，则 四个点不共面的取法有多少种？1.解：9987654323265920个。2.解：9人围坐成一圈，每个人既是起点，又是终点，所以有 98765432940320种坐法。3.解：在1，3，9中任选两段：1，3；1，9；3，9有3个组合. ?在2，8，10，12中任选两数：2，8；2，10；2，12；8，10；8，12；10，12.有6个组合. ?根据分类计数原理，369. ?所以共有9种选法.4.解：如买足球、排球、篮球共有34*5=60种，如买足球、排球、羽毛球共有346=72种，如买足球、篮球、羽毛球共有356=90种，如买排球、篮球、羽毛球共有456=120种，合起来共有60+72+90+120=342种。5.解：10个点中取4个点的取法为C(10)(4)=210种 ；共面的分三种情况： 1、四个点都在四面体的某一个面上，每个面6个点，有652=15种，四个面共有415=60种情况。 2、其中三点共线，另一个点与此三点不在四面体的某一个面上，而在与此三点所在直线异面的那条直线的中点，显然只有6种情况(因为四面体只有6条边)。 3、其中两点所在直线与另两点所在直线平行，且这四个点也不在四面体的某一个面上，画图可得出只有3种情况。因此，取四个不共面的点的不同取法共有：210-60-6-3=141小升初奥数专题讲解：排列与组合来源：重庆奥数网整理 文章作者：奥数网编辑 2011-08-18 16:12:41标签：小升初 奥数 专题讲解 练习题奥数精华资讯 免费订阅问题：小明所在的班级要选出4名中队长，要求每位同学在选票上写上名字，也可以写自己的名字。 结果全班的每位同学都在自己的选票上写了4个互不相同的名字。当小明把同学们的选票收集后发现一个有趣的现象：就是任意取出2张选票，一定有且只有一个人的名字同时出现在2张选票上。 请问：小明所在的班级共有多少人？总体逻辑思路：首先，假设题目所说的情况存在。然后，得出班级人数。最后，构造出一个例子，说明确实存在这种情况。我们先来证明这个班每个人都恰好都被选了4次。思路简介：我们首先用反证法证明没有人被选了4次以上。由于平均每人被选了4次，既然没有人被选了4次以上，肯定也不存在被选了4次以下的人。所以，可以得到每个人恰好被选了4次。首先证明没有人被选了4次以上，我们用反证法。假设有一个人被选了4次以上（由于很容易证明这个班的人数肯定不少于7人，所以我们可以假设有一个人被选了4次以上），我们设这个人为A同学。接下来我们来证明这种情况不存在。把所有选择A同学的选票集中到一起，有5张或5张以上。方便起见，我们把这些选票编号，记为A1选票，A2选票，A3选票，A4选票，A5选票，。意思就是选择A同学的第1张选票，选择A同学的第2张选票，。这些选票都选择了A同学。由于任意2张选票有且只有1个人相同，所以这些选票上除了A同学外，其他都是不同的人。我们还可以证明，这些并不是全部的选票，不是太难，就不证明了。既然这些（所有选A同学的选票）不是全部的选票，我们再拿一张没有选择A同学的选票。方便起见，称之为B选票。根据任意2张选票有且只有1个人相同，A1选票上必有一个人和B选票上的一个人是相同的，而且这个人不是A同学。同样道理，第A2、A3、A4、A5、上也必有一个人和B选票上的一个人是相同的，而且这个人不是A同学。由于B选票上只有4个不同的人，而A1、A2、，的数量大于4.所以，A1、A2、A3、选票中至少有2张选票，除了A同学外还有一个共同的候选人。根据任意2张选票有且只有1个人相同，我们知道这是不可以的。所以，没有人被选了4次以上。由于平均每人被选4次，既然没有人被选4次以上，当然也就不可能有人被选4次以下。所以，每个人恰好被选了4次！证明了每个人都恰好被选了4次后，下面我们用两种方法来求出班级的人数。方法一：解方程设这一班有n个人，从n张选票里面任选2张有C（n，2）=n（n-1）/2种情况。由于任意2张选票都有且只有1个人相同，所以每一种情况都代表了一种2张选票重复选择了同一个人的情况。（这句话不太好理解，暂时没有想到好的表述）每一个人都被选了4次，则2张选票重复选择了同一个人的情况又等于nC（4，2）=6n所以n（n-1）/2=6n解得n=13.方法二：分析论证，计算我们从所有选票中拿出一张，这张选票上有四个人，方便起见记为甲、乙、丙、丁四个人。除了我们拿出的这张选票外，所有选甲的选票组成集合甲.所有选乙的选票组成集合乙.所有选丙的选票组成集合丙.所有选丁的选票组成集合丁.由于每个人都恰好被选了4次，所以甲、乙、丙、丁四个集合中都有3个元素。而且这四个集合没有交集。每个集合有3张选票，再加上我们拿出的这张选票，一共有43+1=13张选票，即13个人。下面我们证明选票数不能多于13张。还是用反证法。假设选票数多于13张，我们从中取14张。从这14张选票中我们拿出一张称为C选票。除了C选票外还有13张选票，C选票上有4个不同的人，这13张选票中的每一张都有一个人和C选票上的一个人是相同的。这样13张选票中至少有4张选择了C选票上的同一个人，这样再加上C选票，就有5个人选择了同一个人。根据前面的结论，没有人被选了4次以上，所以选票数不能多于13张。而且只能是13张。所以只有13张选票，即只有13个人。下面说明这种情况确实存在。给出一种投票结果即可。（1，2，3，4）（1，5，6，7）（1，8，9，10）（1，11，12，13）（2，5，8，11）（2，6，9，12）（2，7，10，13）（3，5，9，13）（3，6，10，11）（3，7，8，12）（4，5，10，12）（4，6，8，13）（4，7，9，11）方法三：网上搜到得一种方法，设班级有x个人，那么x张票中总共有4x（有重复）个名字，也就是说班级里每个人的名字平均出现4次，（1） 如果有一个人的名字在所有票中都出现，那么x张票应该有不重复的名字3x+1个，这与班级有x个人矛盾，（2）如果一个人的名字在5张票中都出现过，那么假设为（1，2，3，4）（1，5，6，7）（1，8，9，10）（1，11，12，13）（1，14，15，16）那么你无法构造一个不包含1，但与前面5张票都有一个同名的票，所以一个人的名字在所有票中最多出现4次，并且每个人的名字在所有票中平均出现4次，那也就是说每个人的名字在所有票中出现4次假设包含1的票为（1，2，3，4）（1，5，6，7）（1，8，9，10）（1，11，12，13）其中2出现了1次，之后构造其他包含名字2的3张票为（2，5，8，11）（2，6，9，12）（2，7，10，13）之后构造分别包含名字3，4的各3张票。发现符合题意，所以这个班有13人。学而思奥数难题以小学4-6年级的杯赛题为来源，试题挑选、答案详解准确性均经学而思奥数名师鉴证；根据对历年杯赛真题的研究、总结及归纳，结合了赛题中的高频考点、难点、易错点、以及最近几年命题趋势所得；适合志在杯赛中夺取佳绩的学生。用1、2、3、4、5、6、7、8可组成多少个没有重复数字的五位数？老师教你解难题-试题详解解：题目：10位客人住入6个有编号的房间，要求空出2间不住人，而其余4间不能空着（至少住有1名客人）。问有多少种住法？这实际上是第二斯特林数。定义S(n,k)为n个有编号的元素分到k个无区别的非空房间里的方法数（注意，和本题目稍有不同，这里房间是不编号的）。S(n,k)就是第二斯特林数，有递推公式S(n,k) = S(n-1,k-1)+k*S(n-1,k) ；作为递推的基础，显然S(n,1)=1（n1），S(n,n)=1。上面的递推式可以用组合证明：假设将元素1单独拿出来住1个房间，那么方法数是S(n-1,k-1)；或者，如果元素1所在的房间不止一个元素，那么可以先将剩下的n-1个元素分配好了房间后，再任选一个房间把元素1放进去，方法数是k*S(n-1,k)；以上两种可能，根据加法原理得证递推公式。（注意，这和爬楼梯的那道题在递推方面有相似之处，那道题是：爬楼梯可以一步跨1级台阶，也可以一步跨2级台阶，求跨一个9级台阶的楼梯有几种走法。） A=10人进1房间方法数；B=10人进2个房间（每个房间不能空着）方法数；C=10人进3房间（每个房间不能空着）方法数；D=10人进4房间（每个房间不能空着）方法数。 c（n，m）代表m个中选n个的组合数。A=1B=10人进2个房间方法数（房间可空着）-1个房间空着方法数=210-c（1，2）*A=1022；C=10人进3个房间方法数（房间可空着）-1个房间空着方法数-2个房间空着方法数=310-c(1，3）*B-c(2，3）*A=55980；D=10人进4个房间方法数（房间可空着）-1个房间空着方法数-2个房间空着方法数-3个房间空着方法数=410-c(1，4）*C-c(2，4）*B-c(3，4）*A=818520；所以10位客人住入6个有编号的房间，要求空出2间的总方法数=c（2，6）*D=12277800。排列组合应用题解题技巧 文章来源：4221学习网 发布日期：2010-03-23 已被977人浏览 关键词： 数学 排列组合排列组合问题在实际应用中是非常广泛的，并且在实际中的解题方法也是比较复杂的，下面就通过一些实例来总结实际应用中的解题技巧。1.排列的定义：从n个不同元素中，任取m个元素，按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列。2.组合的定义：从n个不同元素中，任取m个元素，并成一组，叫做从n个不同元素中取出m个元素的一个组合。3.排列数公式：4.组合数公式：5.排列与组合的区别与联系：与顺序有关的为排列问题，与顺序无关的为组合问题。例1 学校组织老师学生一起看电影，同一排电影票12张。8个学生，4个老师，要求老师在学生中间，且老师互不相邻，共有多少种不同的坐法？分析：此题涉及到的是不相邻问题，并且是对老师有特殊的要求，因此老师是特殊元素，在解决时就要特殊对待。所涉及问题是排列问题。解：先排学生共有种排法，然后把老师插入学生之间的空档，共有7个空档可插，选其中的4个空档，共有种选法。根据乘法原理，共有的不同坐法为种。结论1 插入法：对于某两个元素或者几个元素要求不相邻的问题，可以用插入法。即先排好没有限制条件的元素，然后将有限制条件的元素按要求插入排好元素的空档之中即可。例2 5个男生3个女生排成一排，3个女生要排在一起，有多少种不同的排法？分析：此题涉及到的是排队问题，对于女生有特殊的限制，因此，女生是特殊元素，并且要求她们要相邻，因此可以将她们看成是一个元素来解决问题。解：因为女生要排在一起，所以可以将3个女生看成是一个人，与5个男生作全排列，有种排法，其中女生内部也有种排法，根据乘法原理，共有种不同的排法。结论2 捆绑法：要求某几个元素必须排在一起的问题，可以用捆绑法来解决问题。即将需要相邻的元素合并为一个元素，再与其它元素一起作排列，同时要注意合并元素内部也可以作排列。例3 高二年级8个班，组织一个12个人的年级学生分会，每班要求至少1人，名额分配方案有多少种？分析：此题若直接去考虑的话，就会比较复杂。但如果我们将其转换为等价的其他问题，就会显得比较清楚，方法简单，结果容易理解。解：此题可以转化为：将12个相同的白球分成8份，有多少种不同的分法问题，因此须把这12个白球排成一排，在11个空档中放上7个相同的黑球，每个空档最多放一个，即可将白球分成8份，显然有种不同的放法，所以名额分配方案有种。结论3 转化法：对于某些较复杂的、或较抽象的排列组合问题，可以利用转化思想，将其化归为简单的、具体的问题来求解。例4 袋中有5分硬币23个，1角硬币10个，如果从袋中取出2元钱，有多少种取法？分析：此题是一个组合问题，若是直接考虑取钱的问题的话，情况比较多，也显得比较凌乱，难以理出头绪来。但是如果根据组合数性质考虑剩余问题的话，就会很容易解决问题。解：把所有的硬币全部取出来，将得到0.0523+0.1010=2.15元，所以比2元多0.15元，所以剩下0.15元即剩下3个5分或1个5分与1个1角，所以共有种取法。结论4 剩余法：在组合问题中，有多少取法，就有多少种剩法，他们是一一对应的，因此，当求取法困难时，可转化为求剩法。例5 期中安排考试科目9门，语文要在数学之前考，有多少种不同的安排顺序？分析：对于任何一个排列问题，就其中的两个元素来讲的话，他们的排列顺序只有两种情况，并且在整个排列中，他们出现的机会是均等的，因此要求其中的某一种情况，能够得到全体，那么问题就可以解决了。并且也避免了问题的复杂性。解：不加任何限制条件，整个排法有种，“语文安排在数学之前考”，与“数学安排在语文之前考”的排法是相等的，所以语文安排在数学之前考的排法共有种。结论5 对等法：在有些题目中，它的限制条件的肯定与否定是对等的，各占全体的二分之一。在求解中只要求出全体，就可以得到所求。例6 我们班里有43位同学，从中任抽5人，正、副班长、团支部书记至少有一人在内的抽法有多少种？分析：此题若是直接去考虑的话，就要将问题分成好几种情况，这样解题的话，容易造成各种情况遗漏或者重复的情况。而如果从此问题相反的方面去考虑的话，不但容易理解，而且在计算中也是非常的简便。这样就可以简化计算过程。解：43人中任抽5人的方法有种，正副班长，团支部书记都不在内的抽法有种，所以正副班长，团支部书记至少有1人在内的抽法有种。结论6 排异法：有些问题，正面直接考虑比较复杂，而它的反面往往比较简捷，可以先求出它的反面，再从整体中排除。练习1 某人射击8枪，命中4枪，那么命中的4枪中恰有3枪是连中的情形有几种？练习2 一排8个座位，3人去坐，每人两边至少有一个空座的坐法有多少种？练习3 马路上有编号为1，2，3，10的十只路灯，为节约电而不影响照明，可以把其中的三只路灯关掉，但不能同时关掉相邻的两只或三只，也不能关掉马路两端的灯，问满足条件的关灯方法有多少种？练习4 A、B、C、D、E五人站成一排，如果B必须站在A的右边，那么不同的站法有多少种？练习5 某电路有5个串联的电子元件，求发生故障的不同情形数目？小结：解决排列组合应用题的一些解题技巧，具体有插入法，捆绑法，转化法，剩余法，对等法，排异法；对于不同的题目，根据它们的条件，我们就可以选取不同的技巧来解决问题。对于一些比较复杂的问题，我们可以将几种技巧结合起来应用，便于我们迅速准确地解题。在这些技巧中所涉及到的数学思想方法，例如：分类讨论思想，变换思想，特殊化思想等等，要在应用中注意掌握。