排列组合的算法公式

排列组合公式

复习排列与组合

考试内容：两个原理；排列、排列数公式；组合、组合数公式。

考试要求：1）掌握加法原理及乘法原理，并能用这两个原理分析和解决一些简单的问题。

2）理解排列、组合的意义。掌握排列数、组合数的计算公式，并能用它们解决一些简单的问题。

重点：两个原理尤其是乘法原理的应用。

难点：不重不漏。

知识要点及典型例题分析：

1．加法原理和乘法原理

两个原理是理解排列与组合的概念，推导排列数及组合数公式，分析和解决排列与组合的应用问题的基本原则和依据；完成一件事共有多少种不同方法，这是两个原理所要回答的共同问题。而两者的区别在于完成一件事可分几类办法和需要分几个步骤。

例1．书架上放有3本不同的数学书，5本不同的语文书，6本不同的英语书。

（1）若从这些书中任取一本，有多少种不同的取法？

（2）若从这些书中取数学书、语文书、英语书各一本，有多少种不同的取法？

（3）若从这些书中取不同的科目的书两本，有多少种不同的取法。

解：（1）由于从书架上任取一本书，就可以完成这件事，故应分类，由于有3种书，则分为3类然后依据加法原理，得到的取法种数是：3+5+6=14种。

（2）由于从书架上任取数学书、语文书、英语书各1本，需要分成3个步骤完成，据乘法原理，得到不同的取法种数是：3×5×6=90（种）。

（3）由于从书架上任取不同科目的书两本，可以有3类情况（数语各1本，数英各1本，语英各1本）而在每一类情况中又需分2个步骤才能完成。故应依据加法与乘法两个原理计算出共得到的不同的取法种数是：3×5+3×6+5×6=63（种）。

例2．已知两个集合A={1，2，3}，B={a,b,c,d，e}，从A到B建立映射，问可建立多少个不同的映射？

分析：首先应明确本题中的“这件事是指映射，何谓映射？即对A中的每一个元素，在B中都有唯一的元素与之对应。”

公式P是指排列，从N个元素取R个进行排列。

公式C是指组合，从N个元素取R个，不进行排列。

N-元素的总个数

R参与选择的元素个数

！-阶乘 ，如 9！＝9*8*7*6*5*4*3*2*1

从N倒数r个，表达式应该为n*（n-1)*(n-2)..(n-r+1);

因为从n到（n-r+1)个数为n－（n-r+1)＝r

举例：

Q1: 有从1到9共计9个号码球，请问，可以组成多少个三位数？

A1: 123和213是两个不同的排列数。即对排列顺序有要求的，既属于“排列P”计算范畴。

上问题中，任何一个号码只能用一次，显然不会出现988,997之类的组合， 我们可以这么看，百位数有9种可能，十位数则应该有9-1种可能，个位数则应该只有9-1-1种可能，最终共有9*8*7个三位数。计算公式＝P（3，9)＝9*8*7,(从9倒数3个的乘积）

Q2: 有从1到9共计9个号码球，请问，如果三个一组，代表“三国联盟”，可以组合成多少个“三国联盟”？

A2: 213组合和312组合，代表同一个组合，只要有三个号码球在一起即可。即不要求顺序的，属于“组合C”计算范畴。

上问题中，将所有的包括排列数的个数去除掉属于重复的个数即为最终组合数C(3,9)=9*8*7/3*2*1

排列、组合的概念和公式典型例题分析

例1 设有3名学生和4个课外小组．（1）每名学生都只参加一个课外小组；（2）每名学生都只参加一个课外小组，而且每个小组至多有一名学生参加．各有多少种不同方法？

解（1）由于每名学生都可以参加4个课外小组中的任何一个，而不限制每个课外小组的人数，因此共有 种不同方法．

（2）由于每名学生都只参加一个课外小组，而且每个小组至多有一名学生参加，因此共有 种不同方法．

点评 由于要让3名学生逐个选择课外小组，故两问都用乘法原理进行计算．

排列组合公式

排列与组合都是计算“从n个元素中任取r个元素”的取法总数公式，其主要区别在于：如果不讲究取出元素间的次序，则用组合公式，否则用排列公式。而所谓讲究元素间的次序，可以从实际问题中得以辨别，例如两个人相互握手是不讲次序的；而两个人排队是讲次序的。

排列与组合公式的推导都基于如下两条计数原理：

（1）乘法原理（分步）

如果某件事需经k个步骤才能完成，做第一步有1m种方法，做第二步有2m种方法„„做第k步有km种方法，那么完成这件事共有kmmm21种方法。

譬如，甲城到乙城有3条旅游线路，由乙城到丙城有2条旅游线路，那么从甲城经乙城去丙城共有623条旅游线路。

（2）加法原理（分类）

如果某件事可由k类不同途径之一去完成，在第一类途径中有1m种完成方法，在第二类途径中有2m种完成方法„„在第k类途径中有km种完成方法，那么完成这件事共有kmmm21种方法。

譬如，由甲城到乙城去旅游有3类交通工具：汽车、火车和飞机。而汽车有5个班次，火车有3个班次，飞机有2个班次，那么从甲到乙共有10235个班次供旅游者选择。

计算公式：

（1）排列

从n个不同元素中任取r（nr）个元素排成一列（考虑元素先后出现次序），称此为一个排列，此种排列的总数记为rnP。

按乘法原理，取出的第一个元素有n种取法，取出的第二个元素有1n种取法„„取出的第r个元素有1rn种取法，所以有

！rnn！rnnnPrn)()1()1( （rnA）

若nr，责称为全排列，记为nP，全排列n！Pn （rnA n！Ann） 例如：121234)124(424A

123444A

例：把4个不同的球放入4个不同的盒子中，每个盒子放一个球，有多少种放法？

答：123444A

（2）重复排列

从n个不同元素中每次取出一个，放回后再取下一个，如此连续取r次所得的排列称为重复排列，此种重复排列数共有rn个。

排列组合是组合学最基本的概念。所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。 排列组合公式/排列组合计算公式2008-07-08 13:30

公式P是指排列，从N个元素取R个进行排列。

公式C是指组合，从N个元素取R个，不进行排列。

N-元素的总个数

R参与选择的元素个数

！-阶乘 ，如 9！＝9*8*7*6*5*4*3*2*1

从N倒数r个，表达式应该为n*（n-1)*(n-2)..(n-r+1);

因为从n到（n-r+1)个数为n－（n-r+1)＝r

举例：

Q1: 有从1到9共计9个号码球，请问，可以组成多少个三位数？

A1: 123和213是两个不同的排列数。即对排列顺序有要求的，既

属于“排列P”计算范畴。

上问题中，任何一个号码只能用一次，显然不会出现988,997

之类的组合， 我们可以这么看，百位数有9种可能，十位数则应该有

9-1种可能，个位数则应该只有9-1-1种可能，最终共有9*8*7个三位

数。计算公式＝P（3，9)＝9*8*7,(从9倒数3个的乘积）

Q2: 有从1到9共计9个号码球，请问，如果三个一组，代表“三国

联盟”，可以组合成多少个“三国联盟”？

A2: 213组合和312组合，代表同一个组合，只要有三个号码球在

一起即可。即不要求顺序的，属于“组合C”计算范畴。

上问题中，将所有的包括排列数的个数去除掉属于重复的个

数即为最终组合数C(3,9)=9*8*7/3*2*1

排列、组合的概念和公式典型例题分析

例1 设有3名学生和4个课外小组．（1）每名学生都只参加一个课外小组；（2）每名学生都只参加一个课外小组，而且每个小组至多有一名学生参加．各有多少种不同方法？ 解（1）由于每名学生都可以参加4个课外小组中的任何一个，而不限制每个课外小组的人数，因此共有 种不同方法． （2）由于每名学生都只参加一个课外小组，而且每个小组至多有一名学生参加，因此共有 种不同方法． 点评 由于要让3名学生逐个选择课外小组，故两问都用乘法原理进行计算． 例2 排成一行，其中 不排第一， 不排第二， 不排第三， 不排第四的不同排法共有多少种？ 解 依题意，符合要求的排法可分为第一个排 、 、 中的某一个，共3类，每一类中不同排法可采用画“树图”的方式逐一排出： ∴ 符合题意的不同排法共有9种． 点评 按照分“类”的思路，本题应用了加法原理．为把握不同排法的规律，“树图”是一种具有直观形象的有效做法，也是解决计数问题的一种数学模型． 例３　判断下列问题是排列问题还是组合问题？并计算出结果． （1）高三年级学生会有11人：①每两人互通一封信，共通了多少封信？②每两人互握了一次手，共握了多少次手？ （2）高二年级数学课外小组共10人：①从中选一名正组长和一名副组长，共有多少种不同的选法？②从中选2名参加省数学竞赛，有多少种不同的选法？ （3）有2，3，5，7，11，13，17，19八个质数：①从中任取两个数求它们的商可以有多少种不同的商？②从中任取两个求它的积，可以得到多少个不同的积？ （4）有8盆花：①从中选出2盆分别给甲乙两人每人一盆，有多少种不同的选法？②从中选出2盆放在教室有多少种不同的选法？ 分析　（1）①由于每人互通一封信，甲给乙的信与乙给甲的信是不同的两封信，所以与顺序有关是排列；②由于每两人互握一次手，甲与乙握手，乙与甲握手是同一次握手，与顺序无关，所以是组合问题．其他类似分析． （1）①是排列问题，共用了 封信；②是组合问题，共需握手 （次）． （2）①是排列问题，共有 （种）不同的选法；②是组合问题，共有 种不同的选法． （3）①是排列问题，共有 种不同的商；②是组合问题，共有 种不同的积． （4）①是排列问题，共有 种不同的选法；②是组合问题，共有 种不同的选法． 例４　证明 ． 证明 左式 右式． ∴ 等式成立． 点评　这是一个排列数等式的证明问题，选用阶乘之商的形式，并利用阶乘的性质 ，可使变形过程得以简化． 例5　化简 ． 解法一　原式 解法二　原式 点评 解法一选用了组合数公式的阶乘形式，并利用阶乘的性质；解法二选用了组合数的两个性质，都使变形过程得以简化． 例6　解方程：（1） ；（2） ． 解 （1）原方程 解得 ． （2）原方程可变为 ∵ ， ， ∴ 原方程可化为 ． 即 ，解得第六章 排列组合、二项式定理