计数原理与排列组合

1、整理ppt1计数原理与排列组合整理ppt2基本原理组合排列排列数公式组合数公式应用问题1、知识结构一。复习回顾整理ppt3 2。分类记数原理，分步记数原理分类记数原理分步记数原理原理 完成一件事可以有完成一件事可以有n n类类办法，在第一类中有办法，在第一类中有m m1 1种不种不同的方法，在第二类中有同的方法，在第二类中有m m2 2种不同的方法，种不同的方法，在第，在第n n类办法中有类办法中有m mn n种不同的方种不同的方法，那么完成这件事共法，那么完成这件事共N= N= m m1 1+m+m2 2+m+mn n有种不同的方有种不同的方法。法。 完成一件事需要分成完成一件事需要分成n个

2、个步骤，第一步有步骤，第一步有m1种不同的种不同的方法，第二步有方法，第二步有m2种不同的种不同的方法，方法，第，第n步有步有mn种种不同的方法，那么完成这件不同的方法，那么完成这件事共事共N=m1m2mn有种不同的方法有种不同的方法。 区别 分类记数原理针对的是分类记数原理针对的是“分类分类”问题，其中各种方问题，其中各种方法相互独立，用其中任何一法相互独立，用其中任何一种方法都可完成这件事。种方法都可完成这件事。 分步记数原理针对的是分步记数原理针对的是“分步分步”问题，各步方法相问题，各步方法相互依存，只有各步都完成才互依存，只有各步都完成才能完成这件事。能完成这件事。 整理ppt4排列

3、组合定义从从n个个不同不同元素中，任取元素中，任取m(mn)个个不同不同元素按照元素按照一定顺序排成一列，叫一定顺序排成一列，叫做从做从n个不同元素中取出个不同元素中取出m个不同元素的一个个不同元素的一个排列排列。从从n个个不同不同的元素中，的元素中，任取任取m（mn）个）个不不同同的元素并成一组，的元素并成一组，叫做从叫做从n个不同的元素个不同的元素中取出中取出m个不同的元个不同的元素的一个素的一个组合组合。区别与顺序有关与顺序无关判定 看取出的两个元素互换位置是否为同一种方法，看取出的两个元素互换位置是否为同一种方法，若不是，则是排列问题；若是，则是组合。若不是，则是排列问题；若是，则是组

4、合。公式) 1() 2)(1(mnnnnAmn)!(!mnn!) 1()2)(1(mmnnnnmnC!mmnn3。排列与组合整理ppt5 4。解排列组合问题基本思路排列组合问题有序无序排列组合分类或分步分类或分步直接法直接法间接法不易解不易解整理ppt6题型2 可重复元素排列问题【例【例2】五名学生报名参加四项体育比赛，每人限报一】五名学生报名参加四项体育比赛，每人限报一项，报名方法的种数为多项，报名方法的种数为多 少？五名学生争夺四项比少？五名学生争夺四项比赛的冠军赛的冠军(冠军不并列冠军不并列)，获得冠军的可能性有多少种？，获得冠军的可能性有多少种？ 解答：报名的方法种数为解答：报名的方法

5、种数为4444445(种种)获得冠获得冠军的可能情况有军的可能情况有555554(种种). 方法小节：方法小节： 解决解决“允许重复排列问题允许重复排列问题”常用常用“住店法住店法”，要注，要注意区分两类元素：意区分两类元素：一类元素可以重复，另一类不能重一类元素可以重复，另一类不能重复，把不能重复的元素看作复，把不能重复的元素看作“客客”，能重复的元素看，能重复的元素看作作“店店”，再利用乘法原理直接求解。，再利用乘法原理直接求解。整理ppt7基础知识梳理基础知识梳理二、题型与方法【例【例3】如图，用】如图，用5种不同的颜色给图中种不同的颜色给图中A、B、C、D四个区域涂色，规定每个区四个区

6、域涂色，规定每个区域只涂一种颜色，相邻区域颜色不同，域只涂一种颜色，相邻区域颜色不同，求有多少种不同的涂色方法？求有多少种不同的涂色方法？题型3 涂色问题 解法一解法一（分步法）如题图分四个步骤来完成涂色这件事（分步法）如题图分四个步骤来完成涂色这件事需分为四步，第一步涂需分为四步，第一步涂A区有区有5种涂法；第二步涂种涂法；第二步涂B有有4种种方法；第三步涂方法；第三步涂C有有3种方法；第四步涂种方法；第四步涂D有有3种方法种方法(还可还可以使用涂以使用涂A的颜色的颜色)，根据分步计数原理共有，根据分步计数原理共有5433180种涂色方法种涂色方法 整理ppt82011高考导航高考导航解法二

7、（分类法）：完成涂色的方法分为两类，第一类：解法二（分类法）：完成涂色的方法分为两类，第一类：四个区域涂四种不同的颜色共有四个区域涂四种不同的颜色共有 120种涂法；种涂法； 第二类：四个区域涂三种不同的颜色，由于第二类：四个区域涂三种不同的颜色，由于A、D不不相邻只能是相邻只能是A、D两区域颜色一样，将两区域颜色一样，将A、D看做一个区看做一个区域，共域，共 60种涂法种涂法 由分类计数原理知共有涂法由分类计数原理知共有涂法12060180(种种)方法总结：方法总结： 对涂色问题，有两种解法，法对涂色问题，有两种解法，法1是逐区图示法，注意不是逐区图示法，注意不相邻可同色相邻可同色. 法法2

8、根据用色多少分类法根据用色多少分类法.整理ppt9 题型4 排列中的“相邻”、“不相邻问题” 【例【例4】 a1，a2，a8共八个元素，分别计算满足下列共八个元素，分别计算满足下列条件的排列数条件的排列数(1)八个元素排成一排，且八个元素排成一排，且a1，a2，a3，a4四个元素排在一四个元素排在一起；起；(2)八个元素排成一排，且八个元素排成一排，且a1，a2，a3，a4四个元素互不相四个元素互不相邻；邻；(3)八个元素排成一排，且八个元素排成一排，且a1，a2，a3，a4四个元素互不相四个元素互不相邻，并且邻，并且a5，a6，a7，a8也互不相邻；也互不相邻；(4)排成前后两排每排四个元素

9、排成前后两排每排四个元素整理ppt10解答：解答：(1)（捆绑法捆绑法）先将a1，a2，a3，a4四个元素看成一四个元素看成一个元素与个元素与a5，a6，a7，a8排列一排，有排列一排，有 种排法，再排种排法，再排a1，a2，a3，a4有 不同排法，根据分步计数原理知满足条件的分步计数原理知满足条件的排列数为排列数为 2 880.55A44A55A44A (2)(插空法插空法）先排）先排a5，a6，a7，a8四个元素排成一排，有四个元素排成一排，有 种排法；再将元素种排法；再将元素a1，a2，a3，a4插入由插入由a5，a6，a7，a8间间隔及两端的五个位置中的四个，有隔及两端的五个位置中的四

10、个，有 种排法，根据分步计种排法，根据分步计数原理知：满足条件的排列数为数原理知：满足条件的排列数为 2 880.44A45A44A45A (3)先排先排a5，a6，a7，a8，；共有；共有 种排种排法；然后排法；然后排a1，a2，a3，a4排在排在或或中的中的共有共有2 种排法；根据分步计种排法；根据分步计数原理共有数原理共有 2 1 152种排法种排法(4)前排有前排有 种排法，后排有种排法，后排有 种排法，由分步计数原种排法，由分步计数原理知共有理知共有 8！种排法！种排法44A44A44A44A48A44A44A48A整理ppt11方法总结 （1）若某些元素必须相邻，常用捆绑法，即先把

11、这几个相邻元素捆在一起看成一个元素，再与其他元素全排列，最后再考虑这几个相邻元素的顺序。 （2）若某些元素不相邻，常用插空法，即先将普通元素全排列，然后再从排就的每两个元素之间及两端选出若干个空挡插入这些特殊元素。 (3)前后排问题，直排法.整理ppt12变式变式4 4个男同学，个男同学，3个女同学站成一排个女同学站成一排(1)3个女同学必须排在一起，有多少种不同的排法？个女同学必须排在一起，有多少种不同的排法？(2)任何两个女同学彼此不相邻，有多少种不同的排任何两个女同学彼此不相邻，有多少种不同的排法？法？(3)其中甲、乙两同学之间必须恰有其中甲、乙两同学之间必须恰有3人，有多少种不人，有多

12、少种不同的排法？同的排法？(4)甲、乙两人相邻，但都不与丙相邻，有多少种不甲、乙两人相邻，但都不与丙相邻，有多少种不同的排法？同的排法？ (5)女同学从左到右按高矮顺序排，有多少种不同的排女同学从左到右按高矮顺序排，有多少种不同的排法？法？(3个女生身高互不相等个女生身高互不相等)整理ppt13解答：解答：(1)3个女同学是特殊元素，我们先把她们排好，共个女同学是特殊元素，我们先把她们排好，共有有 种排法；由于种排法；由于3个女同学必须排在一起，我们可视排个女同学必须排在一起，我们可视排好的女同学为一整体，再与男同学排队，这时是好的女同学为一整体，再与男同学排队，这时是5个元素个元素的全排列，

13、应有的全排列，应有 种排法，由分步计数的原理种排法，由分步计数的原理,有有 720种不同排法种不同排法(2)先将男生排好，共有先将男生排好，共有 种排法，再在这种排法，再在这4个男生的中间个男生的中间及两头的及两头的5个空档中插入个空档中插入3个女生有个女生有 种方案，故符合条种方案，故符合条件的排法共有件的排法共有 1 440种不同排法种不同排法55A(3)甲、乙甲、乙2人先排好，有人先排好，有 种排法，再从余下种排法，再从余下5人中选人中选3人排人排在甲、乙在甲、乙2人中间，有人中间，有 种排法，这时把已排好的种排法，这时把已排好的5人视为人视为一整体，与最后剩下的一整体，与最后剩下的2人再排，又有人再排，又有 种排法，这样总种排法，这样总共有共有 720种不同排法种不同排法整理ppt14(4)先排甲、乙和丙先排甲、乙和丙3人以外的其他人以外的其他4人，有人，有 种排法；由种排法；由于甲、乙要相邻，故再把甲、乙排好，有于甲、乙要相邻，故再把甲、乙排好，有 种排法；最后种排法；最后把甲、乙排好的这个整体与丙分别插入原先排好的