排列组合介绍及例题

1、排列组合排列组合是组合学最基本的概念。所谓排列，就是指从给定个数的元素中取出指定个 数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排 序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。排列组合与 古典概率论关系密切。1历史及发展虽然数数始于以结计数的远古时代，由于那时人的智力的发展尚处于低级阶段，谈不 上有什么技巧。随着人们对于数的了解和研究，在形成与数密切相关的数学分支的过程 中，如数论、代数、函数论以至泛函的形成与发展，逐步地从数的多样性发现数数的多样 性，产生了各种数数的技巧。同时，在人们对于形有了深入的了解和研究的基础上，在形成与形密切相

2、关的各种数 学分支的过程中，如几何学、拓扑学以至X畴论的形成与发展，逐步地从形的多样性也发现了数形的多样性，产生了各种数形的技巧。近代的集合论、数理逻辑等反映了潜在的数 与形之间的结合。而现代的代数拓扑和代数几何等则将数与形密切地联系在一起了。这 些，对于以数的技巧为中心课题的近代组合学的形成与发展都产生了而且还将会继续产生 深刻的影响。由此观之，组合学与其他数学分支有着必然的密切联系。它的一些研究内容与方法来 自各个分支也应用于各个分支。当然，组合学与其他数学分支一样也有其独特的研究问题 与方法，它源于人们对于客观世界中存在的数与形及其关系的发现和认识。例如，中国古 代的易经中用十个天干和十

3、二个地支以六十为周期来记载月和年，以及在洛书河图中 关于幻方的记载，是人们至今所了解的最早发现的组合问题。于11和12世纪间，贾宪就发现了二项式系数，杨辉将它整理记载在他的续古抉奇 法一书中。这就是中国通常称的杨辉三角。事实上，于12世纪印度的婆什迦罗第二也发现了这种组合数。13世纪波斯的哲学家曾讲授过此类三角。而在西方，布莱兹帕斯卡发现这个三角形是在 17世纪中期。这个三角形在其他数学分支的应用也是屡见不鲜的。同时，帕斯卡和费马均发现了许多与概率论有关的经典组合学的结果。因此，西方人认为 组合学开始于17世纪。组合学一词是德国数学家莱布尼茨在数学的意义下首次应用。也 许，在那时他已经预感到了

4、其将来的蓬勃发展。然而只有到了18世纪欧拉所处时代，组合学才可以说开始了作为一门科学的发展，因为那时，他解决了柯尼斯堡七桥问题问题， 发现了多面体（首先是凸多面体，即平面图的情形）的顶点数、边数和面数之间的简单关系。现在已被人们称为欧拉公式。甚至，当今人们所称的哈密顿圈的首创者也应该是欧 拉。这些不但使欧拉成为组合学的一个重要组成部分一一图论而且也成为占据现代数学舞台中心的拓扑学发展的先驱。同时，他对导致当今组合学中的另一个重要组成部分一一组合设计中的拉丁方的研究所提出的猜想，人们称为欧拉猜想，直到 1959年才得到完全的 解决。于19世纪初，高斯提出的组合系数，今称高斯系数，在经典组合学中也

5、占有重要地 位。同时，他还研究过平面上的闭曲线的相交问题，由此所提出的猜想称为高斯猜想，它 直到20世纪才得到解决。这个问题不仅贡献于拓扑学，而且也贡献于组合学中图论的发 展。同在19世纪，由乔治布尔发现且被当今人们称为布尔代数的分支已经成为组合学中 序理论的基石。当然，在这一时期，人们还研究其他许多组合问题，它们中的大多数是娱 乐性的。20世纪初期，庞加莱联系多面体问题发展了组合学的概念与方法，导致了近代拓扑 学从组合拓扑学到代数拓扑学的发展。于20世纪的中、后期，组合学发展之迅速也许是人们意想不到的。首先，于 1920年费希尔(Fisher , R.A.)和耶茨(Yates , F.)发展

6、了 实验设计的统计理论，其结果导致后来的信息论，特别是编码理论的形成与发展.于1939年，坎托罗维奇(K a h t o p p用及.发现了线性规划问题并提出解乘数法。于 1947年 丹齐克(Dantzig , G.B.)给出了一般的线性规划模型和理论，他所创立的单纯形方法奠定 了这一理论的基础，阐明了其解集的组合结构。直到今天它仍然是应用得最广泛的数学方 法之一。这些又导致以网络流为代表的运筹学中的一系列问题的形成与发展。开拓了人们 目前称为组合最优化的一个组合学的新分支。在20世纪50年代，中国也发现并解决了一类称为运输问题的线性规划的图上作业法，它与一般的网络流理论确有异曲同工之妙。在

7、此基础上又出现了国际上通称的中国邮递员问题。另一方面，自1940年以来，生于英国的塔特(Tutte, W.T.)在解决拼方问题中取得 了一系列有关图论的结果，这些不仅开辟了现今图论发展的许多新研究领域，而且对于20世纪30年代，惠特尼(Whitney , H.)提出的拟阵论以及人们称之为组合几何的发展都起 到了核心的推动作用。应该特别提到的是在这一时期，随着电子技术和计算机科学的发展 愈来愈显示出组合学的潜在力量。同时，也为组合学的发展提出了许多新的研究课题。例 如，以大规模和超大规模集成电路设计为中心的计算机辅助设计提出了层出不穷的问题。其中一些问题的研究与发展正在形成一种新的几何，目前人们

8、称之为组合计算几何。关于 算法复杂性的研究，自 1961年库克(Cook, S.A.)提出NP完全性理论以来，已经将这 一思想渗透到组合学的各个分支以至数学和计算机科学中的一些分支。近20年来，用组合学中的方法已经解决了一些即使在整个数学领域也是具有挑战性 的难题。例如，X 德瓦尔登(Van der Waerden , B.L.)于1926年提出的关于双随机矩 阵积和式猜想的证明；希伍德( Heawood , P.J.)于1890年提出的曲面地图着色猜想的 解决;著名的四色定理的计算机验证和扭结问题的新组合不变量发现等。在数学中已经或正 在形成着诸如组合拓扑、组合几何、组合数论、组合矩阵论、组

9、合群论等与组合学密切相关的交叉学科。此外，组合学也正在渗透到其他自然科学以及社会科学的各个方面，例 如，物理学、力学、化学、生物学、遗传学、心理学以及经济学、管理学甚至政治学等。2定义及相关定义及公式排列计算公式=乃(一i)(一 2)5切+ 1)= (w -/?)!.排列数公式排列的定义及其11算公式：从n个不同元素中，任取 m(mcn,m与n均为自然数，下同)个元素按照一定的顺序排成一列，叫做从 n个不同元素中取出 m个元素的一个排列； 从n个不同元素中取出 m(mCn )个元素的所有排列的个数，叫做从 n个不同元素中取出 m 个元素的排列数，用符号 A(n,m )表示。A(n,m)=n(n

10、-1)(n- 2)(n-m+1)=n!/(n-m)! 此外规定 0!=1(n!表示 n(n-1)(n-2).1,也就是 6! =6x5x4x3x2x1)组合的定义及其方t算公式：从n个不同元素中，任取 m(mcn )个元素并成一组，叫做从n个不同元素中取出 m个元素的一个组合；从 n个不同元素中取出 m(mCn )个元素 的所有组合的个数，叫做从 n个不同元素中取出 m个元素的组合数。用符号 C(n,m)表 示。C(n,m)=A(n,m)/m ! ; C(n,m)=C(n,n-m )。( nm)其他排列与组合公式从n个元素中取出 m个元素的循环排列数 =A(n,m)/m!=n!/m!(n-m)

11、!. n个元素被分成k类，每类的个数分别是n1,n2,.nk这n个元素的全排列数为n!/(n1 !沏2 ! X.冰!). k类元素，每类的个数无限，从中取出m个元素的组合数为C(m+k-1,m )。符号例题：求4*1!十2*2!+3*3! +十六*占！ = ?解：因为! *!-(Jt+l)-l*jt! = (fr+l)Ujl!所以原式=(2!-1!) + (3!-2!) + (4-3!. + 网-佐一1川 + 伏+1)一眉= (A +1)-1常见的一道题目C-bination 组合数A-Arrangement 排列数（在旧教材为P-Permutation ）N-元素的总个数M-参与选择的元素个

12、数些公式:。：十。；+。；+ ；=2Cr+Cr+1=C：!n n十 I!-阶乘（月+1）23 H r-=（7n m n nG m =cm cm-ln +1n r?ync1 y = nG-刍门 2n-lft- VC7c C门一？ =C：ya-iatn cl = cn1g -n霭-yjc1 =*（凡+3僻一， 刍门9：）:口与：二；4”（也一）。或二：*气。；）2 5 个 1r口r* q1J. E -V Cml 二 C m 5廿m）工刍 h m置1 +咒组合恒等式V C f /T 4-Cn，谷2十2F -U71分产：= s +1)!-1七i ，产m+1 =pm + n，pm - 1r? +1 n

13、n 排列组合常见公式基本计数原理加法原理和分类计数法L加法原理：做一件事，完成它可以有n类办法，在第一类办法中有 ml种不同的方法，在第二类办法中有 m2种不同的方法， ，在第n类办法中有mn种不同的方法， 那么完成这件事共有 N=m1+m2+m 3+mn种不同方法。2 .第一类办法的方法属于集合 A1 ,第二类办法的方法属于集合 A2,，第n类办 法的方法属于集合 An,那么完成这件事的方法属于集合A1UA2U UAn 。3 .分类的要求：每一类中的每一种方法都可以独立地完成此任务；两类不同办法中的 具体方法，互不相同（即分类不重）；完成此任务的任何一种方法，都属于某一类（即分 类不漏）。乘

14、法原理和分步计数法1 .乘法原理：做一件事，完成它需要分成n个步骤，做第一步有 ml种不同的方法,做第二步有m2种不同的方法，做第n步有mn种不同的方法，那么完成这件事共 W N=m1 m2X m3XXmn种不同的方法。2 .合理分步的要求任何一步的一种方法都不能完成此任务，必须且只须连续完成这n步才能完成此任务；各步计数相互独立；只要有一步中所采取的方法不同，则对应的完成此事的方法也不 同。3.与后来的离散型随机变量也有密切相关。二项式定理(a+b)An= . ( 0-n)C(in)aA(n-i)bAi1通项公式：a_(i+1 ) =C(in)aA(n-i)bAi二项式系数：C(in)杨辉三

15、角：右图。两端是 1,除1外的每个数是肩上两数之和。系数性质：和首末两端等距离的系数相等；当二项式指数n是奇数时，中间两项最大且相等;111121133114641i5ID10511B152015611721353521T11a2S5C70552BS11q3664恢126343fi51当二项式指数n是偶数时，中间一项最大。二项式展开式中奇数项和偈城项总和相同，都是 2A(n-1 );二项式展开式中所有系数总和是2An历史1772年，法国数学家 X德蒙德(Vandermonde , A. - T.)以np表示由n个不同的 元素中每次取p个的排列数。瑞士数学家欧拉(Euler, L.)则于1771

16、年以及于1778年以表示由n个不同元素中 每次取出p个元素的组合数。1830年，英国数学家皮科克(Peacock , G)引入符号Cr表示n个元素中每次取r 个的组合数。1869年或稍早些，剑桥的古德文以符号nPr表示由n个元素中每次取r个元素的排列数，这用法亦延用至今。按此法，nPn便相当于n!。1872年，德国数学家埃汀肖森(Ettingshausen , B. A. von )引入了符号(np)来表 示同样的意义，这组合符号( Signs of binations ) 一直沿用至今。1880年，鲍茨(Potts , R.)以nCr及nPr分别表示由n个元素取出r个的组合数 与排列数。18

17、86年，惠特渥斯(Whit-worth , A. W.)用r和Pnr表示同样的意义，他还用 Rnr 表示可重复的组合数。1899年，英国数学家、物理学家克里斯托尔( Chrystal , G.)以nPr, nCr分别表示 由n个不同元素中每次取出 r个不重复之元素的排列数与组合数，并以 nHr表示相同意义 下之可重复的排列数，这三种符号也通用至今。1904年，德国数学家内托(Netto , E.)为一本百科辞典所写的辞条中，以 Arn表 示上述nPr之意，以Crn表示上述nCr之意，后者亦也用符号(n r)表示。这些符号也一 直用到现代。此外，在八卦中，亦运用到了排列组合。组合数的奇偶奇偶定义

18、：X崔&合数 C(n,k)(n=k ):将n,k分别化为二进制，若某二进制位对应的n为0,而k为1，则C(n,k )为偶数；否则为奇数。下面是判定方法：结论：对于C(n,k ),若n&k = k则c(n,k)为奇数，否则为偶数。证明：对于C(n,k ),若n&k = k则c(n,k)为奇数，否则为偶数。证明：利用数学归纳法：由 C(n,k) = C(n-1,k) + C(n-1,k-1);对应于杨辉三角：1可以验证前面几层及k = 0时满足结论，下面证明在C(n-1,k )和C(n-1,k-1) (k 0)满足结论的情况下，C(n,k)满足结论。1) .假设 C(n-1,k)和 C(n-1,k

19、-1 )为奇数：则有：(n-1) &k = k;(n-1 ) &(k-1 ) = k-1;由于k和k-1的最后一位(在这里的位指的是二进制的位，下同)必然是不同的，所 以n-1的最后一位必然是1O现假设n&k = k。则同样因为n-1和n的最后一位不同推出k的最后一位是1。因为n-1的最后一位是1,则n的最后一位是0,所以n&k != k ,与假设矛盾。所以得n&k != k。2) .假设 C(n-1,k)和 C(n-1,k-1 )为偶数：则有:(n-1) &k != k;(n-1 ) &(k-1 ) != k-1;现假设n&k = k.则对于k最后一位为1的情况：此日n n最后一位也为1,所

20、以有(n-1 ) &(k-1 ) = k-1 ,与假设矛盾。而对于k最后一位为0的情况：则k的末尾必有一部分形如：10;代表任意个0。相应的，n对应的部分为：1*; *代表0或1。而若n对应的*中只要有一个为1,则(n-1 ) &k = k成立，所以n对应部分也应该是10 O则相应的，k-1和n-1的末尾部分均为 01,所以(n-1 ) &(k-1 ) = k-1成立，与假 设矛盾。所以得n&k != k。由1)和2)得出当C(n,k)是偶数时，n&k != k。3) .假设C(n-1,k)为奇数而C(n-1,k-1 )为偶数：则有：(n-1) &k = k;(n-1 ) &(k-1 ) !=

21、 k-1;显然，k的最后一位只能是 0,否则由(n-1 ) &k = k即可推出(n-1) &(k-1 ) = k- 1。所以k的末尾必有一部分形如：10;相应的，n-1的对应部分为：1*;相应的，k-1的对应部分为：01;则若要使得(n-1) &(k-1 ) != k-1则要求n-1对应的号*中至少有一个是 0.所以n的对应部分也就为：1*;(不会因为进位变1为0)所以n&k = k 。4) .假设C(n-1,k)为偶数而C(n-1,k-1 )为奇数：则有:(n-1) &k != k;(n-1 ) &(k-1 ) = k-1;分两种情况：当k-1的最后一位为0时：则k-1的末尾必有一部分形如

22、：10;相应的，k的对应部分为:11;相应的，n-1的对应部分为:1*0;(若为1*1 ,则(n-1) &k = k)相应的，n的对应部分为：1*1;所以n&k = k。当k-1的最后一位为1时：则k-1的末尾必有一部分形如：01;(前面的0可以是附加上去的)相应的，k的对应部分为:10;相应的，n-1的对应部分为：01;(若为11 ,则(n-1) &k = k)相应的，n的对应部分为:10;所以n&k = k。由3) , 4)得出当C(n,k)为奇数时，n&k = k。综上，结论得证。3组合数学中的著名问题?计算一些物品在特定条件下分组的方法数目。这些是关于排列、组合和整数分拆 的。?地图着

23、色问题：对世界地图着色，每一个国家使用一种颜色。如果要求相邻国家的 颜色相异，是否总共只需四种颜色？这是图论的问题。?船夫过河问题：船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊 就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样把所有东西都运过 河？这是线性规划的问题。?中国邮差问题：由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是一个 NP完全问题，存在多项式复杂度算法：先求出度为奇数的点，用匹配算法算出这些点间的连接方式，然后再用欧拉路 径算法求解。这也是图论的问题。?任务分配问题（也称婚配问题）：有一些员工要完成一些

24、任务。各个员工完成不同 任务所花费的时间都不同。每个员工只分配一项任务。每项任务只被分配给一个员 工。怎样分配员工与任务以使所花费的时间最少？这是线性规划的问题。?如何构作幻方。?大乐透4例题分析难点从千差万别的实际问题中抽象出几种特定的数学模型，需要较强的抽象思维能力；限制条件有时比较隐晦，需要我们对问题中的关键性词（特别是逻辑关联词和量词）准确理解；计算手段简单，与旧知识联系少，但选择正确合理的计算方案时需要的思维量较大；计算方案是否正确，往往不可用直观方法来检验，要求我们搞清概念、原理，并具有较强的分析能力。例题【例1】从1、2、3、20这二十个数中任取三个不同的数组成等差数列，这 样的

25、不同等差数列有多少个？分析：首先要把复杂的生活背景或其它数学背景转化为一个明确的排列组合问题。设a,b,c成等差，2b=a+c ,可知b由a,c决定，又 2b是偶数，a,c同奇或同偶，即：分别从 1, 3, 5,，19或2, 4, 6,8,，20这十个数中选出两个数进行排列，由此就可确定等差数列，A （10,2）*2=90*2 ,因而本题为 180。【例2】某城市有4条东西街道和6条南北的街道，街道之间的间距相同，若规定只 能向东或向北两个方向沿图中路线前进，则从M到N有多少种不同的走法 ？分析：对实际背景的分析可以逐层深入：(一)从M到N必须向上走三步，向右走五步，共走八步；(二)每一步是向

26、上还是向右，决定了不同的走法；(三)事实上，当把向上的步骤决定后，剩下的步骤只能向右；从而，任务可叙述为：从八个步骤中选出哪三步是向上走，就可以确定走法数。，本题答案为：C (8,3) =56。分析分析是分类还是分步，是排列还是组合注意加法原理与乘法原理的特点，分析是分类还是分步，是排列还是组合。【例3】在一块并排的10垄田地中，选择二垄分别种植 A, B两种作物，每种种植一 垄，为有利于作物生长，要求 A, B两种作物的间隔不少于 6垄，不同的选法共有多少 种？分析：条件中 要求A、B两种作物的间隔不少于 6垄”这个条件不容易用一个包含排 列数，组合数的式子表示，因而采取分类的方法。第一类：

27、A在第一垄，B有3种选择；第二类：A在第二垄，B有2种选择；第三类：A在第三垄，B有1种选择，同理A、B位置互换，共12种。【例4】从6双不同颜色的手套中任取 4只，其中恰好有一双同色的取法有多少种？ (A)240 (B)180 (C)120 (D)60分析：显然本题应分步解决。(一)从6双中选出一双同色的手套，有6种方法；(二)从剩下的十只手套中任选一只，有10种方法。(三)从除前所涉及的两双手套之外的八只手套中任选一只，有8种方法；(四)由于选取与顺序无关，因(二)(三)中的选法重复一次，因而共 240种。或分步从6双中选出一双同色的手套，有 C (6,1) =6种方法从剩下的5双手套中任

28、选两双，有 C (5,2) =10种方法从两双中手套中分别拿两只手套，有 C (2,1 ) XC (2,1 ) =4种方法。【例5】.身高互不相同的 6个人排成2横彳T 3纵列，在第一行的每一个人都比他同 列的身后的人个子矮，则所有不同的排法种数为 。分析：每一纵列中的两人只要选定，则他们只有一种站位方法，因而每一纵列的排队 方法只与人的选法有关系，共有三纵列，从而有 C (6,2) XC (4,2) C (2,2) =90种。【例6】在11名工人中，有5人只能当钳工，4人只能当车工，另外 2人能当钳工 也能当车工。现从 11人中选出4人当钳工，4人当车工，问共有多少种不同的选法？分析：采用加

29、法原理首先要做到分类不重不漏，如何做到这一点？分类的标准必须前后统一。以两个全能的工人为分类的对象，考虑以他们当中有几个去当钳工为分类标准。第一类：这两个人都去当钳工，C(2,2)XC(5,2)XC (4,4)=10种；第二类：这两个人都去当车工，C(5,4)XC(2,2)XC (4,2)=30种；第三类：这两人都不去当钳工，C(5,4)XC(4,4)=5种。第四类：这两个人一个去当钳工、一个去当车工，C (2,1) XC (5,3) XC (4,3) =80种；第五类：这两个人一个去当钳工、另一个不去当车工，C (2,1) C (5,3) XC(4,(4) =20 种；第六类：这两个人一个去

30、当车工、另一个不去当钳工，C (5,4) C (2,1) 0(4,(5) =40 种；因而共有185种。【例7】现有印着0,1,3, 5, 7 , 9的六X卡片，如果允许9可以作6用，那么从 中任意抽出三X可以组成多少个不同的三位数？分析：有同学认为只要把 0, 1, 3 ,5 ,7 , 9的排法数乘以2即为所求，但实际上抽 出的三个数中有9的话才可能用6替换，因而必须分类。抽出的三数含0,含9,有32种方法；抽出的三数含0不含9,有24种方法；抽出的三数含9不含0,有72种方法；抽出的三数不含9也不含0,有24种方法。因此共有32+24+72+24=152 种方法。【例8】停车场划一排12个

31、停车位置，今有 8辆车需要停放，要求空车位连在一起，不同的停车方法有多少种 ？分析：把空车位看成一个元素，和8辆车共九个元素排列，因而共有A (9,9)=362880种停车方法。特殊优先特殊元素，优先处理；特殊位置，优先考虑。【例9】六人站成一排，求甲、乙既不在排头也不在排尾的排法数甲不在排头，乙不在排尾，且甲乙不相邻的排法数分析：按照先排出首位和末尾再排中间四位分步计数第一步：排出首位和末尾、因为甲乙不在首位和末尾，那么首位和末尾实在其它四位 数选出两位进行排列、一共有A (4,2) =12种；第二步：由于六个元素中已经有两位排在首位和末尾，因此中间四位是把剩下的四位 元素进行顺序排列，共

32、A (4,4) =24 种；根据乘法原理得即不再排头也不在排尾数共12 X24=288种。第一类：甲在排尾，乙在排头，有 A (4,4)种方法。第二类：甲在排尾，乙不在排头，有 33 (4,4)种方法。第三类：乙在排头，甲不在排尾，有 33 (4,4)种方法。第四类：甲不在排尾也不在排头，乙不在排头也不在排尾，有 63 (4,4)种方法 (排除相邻)。共 A (4,4) +3XA (4,4) +3XA (4,4) +6XA (4,4) =312 种。【例10】对某件产品的6件不同正品和4件不同次品进行一一测试，至区分出所有 次品为止。若所有次品恰好在第五次测试时被全部发现，则这样的测试方法有多

33、少种可 能？分析：本题意指第五次测试的产品一定是次品，并且是最后一个次品，因而第五次测 试应算是特殊位置了，分步完成。第一步：第五次测试的有 C (4,1)种可能；第二步：前四次有一件正品有C (6,1)中可能。第三步：前四次有 A (4,4)种可能。共有576种可能。捆绑与插空【例11】8人排成一队甲乙必须相邻甲乙不相邻甲乙必须相邻且与丙不相邻甲乙必须相邻，丙丁必须相邻甲乙不相邻，丙丁不相邻分析：甲乙必须相邻，就是把甲乙捆绑(甲乙可交换)和 7人排列A (7,7) XA(2, 2)甲乙不相邻， A (8,8) -A (7,7) X2。或 A (6,6) 3(7,2)甲乙必须相邻且与丙不相邻，

34、先求甲乙必须相邻且与丙相邻A (6,6) 2X2甲乙必须相邻且与丙不相邻 A (7,7) X2-A (6,6) X2X2甲乙必须相邻，丙丁必须相邻A (6,6) X2X2甲乙不相邻，丙丁不相邻，A (8,8) -A (7,7) X2X2+A (6,6) X2 X2【例12】某人射击8枪，命中4枪，恰好有三枪连续命中，有多少种不同的情况,分析：二.连续命中的三枪与单独命中的一枪不能相邻，因而这是一个插空问题。另外没有命中的之间没有区别，不必计数。即在四发空枪之间形成的5个空中选出2个的排列，即 A (5,2)。【例13】马路上有编号为1, 2, 3,10十个路灯，为节约用电又看清路面， 可以把其

35、中的三只灯关掉，但不能同时关掉相邻的两只或三只，在两端的灯也不能关掉的 情况下，求满足条件的关灯方法共有多少种？分析：即关掉的灯不能相邻，也不能在两端。又因为灯与灯之间没有区别，因而问题 为在7盏亮着的灯形成的不包含两端的6个空中选出3个空放置熄灭的灯。.共C (6,3) =20种方法。间接计数法排除法【例14】三行三列共九个点，以这些点为顶点可组成多少个三角形？分析：有些问题正面求解有一定困难，可以采用间接法。所求问题白方法数=任意三个点的组合数-共线三点的方法数，共76种。【例15 正方体8个顶点中取出4个，可组成多少个四面体 ？分析：所求问题的方法数 =任意选四点的组合数-共面四点的方法

36、数，:共 C (8,4) -12=70-12=58 个。【例16】1, 2, 3,，9中取出两个分别作为 对数的底数和真数，可组成多少个 不同数值的对数？分析：由于底数不能为1。当1选上时，1必为真数，.有一种情况。当不选1时，从2-9中任取两个分别作为底数，真数，共 A (8,2) =56,其中log2为底4=log3为底9, log4为底2=log9为底3,log2为底3=log4为底9,log3为底 2=log9 为底 4.因而一共有 56-4+1=53 个。【例17】六人排成一排，要求甲在乙的前面，(不一定相邻)，共有多少种不同的方法？如果要求甲乙丙按从左到右依次排列呢？分析：(一)实

37、际上，甲在乙的前面和甲在乙的后面两种情况对称，具有相同的排法 数。因而有=360种。(二)先考虑六人全排列；其次甲乙丙三人实际上只能按照一种顺序站位，因而前面的排法数重复了种，.共=120种。【例18】5男4女排成一排，要求男生必须按从高到矮的顺序，共有多少种不同的方法？分析：首先不考虑男生的站位要求，共 A (9,9)种；男生从左至右按从高到矮的顺 序，只有一种站法，因而上述站法重复了次。因而有=9X8X7X6=3024种。若男生从右至左按从高到矮的顺序，只有一种站法，同理也有 3024种，综上，有6048 种。【例19 三个相同的红球和两个不同的白球排成一行，共有多少种不同的方法？分析：先认为三个红土互不相同，共 A (5,5) =120种方法。而由于三个红球所占位置相同的情况下，共A (3,3) =6变化，因而共 A (5,5) /A(3,3) =20 种。公式P是指排列，从N个元素