排列组合问题(一)   枚举法 

导言：

   当计算的总数量不多时，我们通常把要计数的所有对象一一列举出来，从而求出其总数，这种最简单、最基本的计数方法叫做枚举法，或穷举法、列举法、分组法

   使用枚举法计数时，要注意以下几点：①初步估计，总的数目不太多，又没有更简捷的办法②为了使枚举的结果不重复又不遗漏，我们要抓住对象的特征，选择适当的标准分类，有次序、有规律地列举

 例1．现有1克、2克、4克、10克的砝码各一个，那么在天平上能称出多少不同重量的物体（只允许砝码放在天平的右边的盘子里）

   解析：按使用砝码的个数进行分类列举

   （1）、若使用一个砝码能称：1克、2克、4克、10克，共4种重量物体

   （2）、若使用二个砝码能称：1+2；1+4；1+10；2+4；2+10；4+10克，共6种重量

   （3）、若使用三个砝码能称：1+2+4；1+2+10；1+4+10；2+4+10克，共4种重量

   （4）若使用四个砝码能称：1+2+4+10=17克，共1种重量物体

    所以，总共能称：4+6+4+1=15种不同重量的物体

   思考：如果把题目中括号里的条件去掉，又能称多少种不同重量的物体？

   例2、有一张五元、4张贰元和8张一元人民币，从中取出9元，共有多少种不同的取法？

   解析：按从大到小，从少到多的次序，先取五元，再取贰元，后取一元的顺序，把所有情况通常列表的形式一一列举出来

5     元	2     元	1    元
1	0	4
1	1	2
0	2	0
0	1	7
0	2	5
0	3	3
0	4	1

 从上面的列举中可以看出:取9元钱共有7种不同的取法

   例3、从1—10的10个数中，每次取2个数，要使它们的和大于10，一共有多少种取法？

    解析：可从小到大依次思考

          ①   1+10

          ②   2+9，2+10

          ③   3+8，3+9，3+10

          ④   4+7，4+8，4+9，4+10

          ⑤   5+6，5+7，5+8，5+9，5+10

          ⑥   6+7，6+8，6+9，6+10

          ⑦   7+8，7+9，7+10

          ⑧   8+9，8+10

          ⑨   9+10

   所以，共有1+2+3+4+5+4+3+2+1=25种不同的取法

   例4、在1—400的自然数中，数字“2”出现了多少次？

   解析：在1—400这400个数中，“2”可能出现在个位、十位、百位上，我们就按这个来分类列举

 在个位上：2、12、、、92；102、112、、、192；202、212、、、292；302、312、、、392，共10×4=40次

 在十位上：20、21、、、29；120、121、、、129；220、221、、、229；320、321、、、329；共10×4=40次

 在百位上：200—299，共100次

  所以，“2”总共出现了40+40+100=180次

 思考：仔细思考下题，看看与例4有何区别：在1—400的自然数中，含有数字“2”的数字有多少个？

   例5、下图中有6个点，9条线段，一只蚂蚁从A点出发，沿差某条线段爬到C点，行进中，同一点或同一线段只能经过一次，这只蚂蚁最多有多少种不同的爬法

    解析：从A点出发有三种路可以走，我们就按这个进行分类列举

A                   E                    D     

 B                      F                      C

(注示:上图中,AF间有一连线,EC间也有一连线)

 ①A—E—D—C；A—E—C；A—E—F—C，有三种爬法

 ②A—F—E—D—C；A—F—E—C；A—F—C，有三种爬法

 ③A—B—F—E—D—C；A—B—F—E—C；A—B—F—C，有三种爬法

  所以，共有9种不同的爬法

 例6、从学校到少年宫有4条东西向的马路和3条南北向的马路，小明从学校步行到少年宫（只许向东或向南行步），最多有多少种走法？

学校 A                           B            

C	D
E	F

                                                                   少年宫 解析：在图形ABCD中，到B只有一种走法，到C也只有一种走法，到D有两种走法

在图形CDEF中，到E只有一种走法，到D有两种走法，到F有三种走法

  我们可以发现规律：通过任何一个交叉点的路线总数等于该点左、上方的两邻交叉点的路线的总和，例如，通过点F的路线总和，会等于F点左方的点E、上方的点D通过路线的总和，1+2=3种，按这个规律，我们依次计数下去，到少年宫应有6+4=10种不同的走法

  小结：在计数时，不遵循数序规律，东举一个，西举一个，不按顺序列举，往往会出现遗漏或重复，有序的思考、合理的分类，才是解决这类问题最关键的思维。

排列组合问题(二)   加法原理和乘法原理

导言：

   加法原理和乘法原理，是排列组合中的二个基本原理，在解决计数问题中经常运用。把握这两个原理，并能正确区分这两个原理，至关重要。

一、概念

   （一）加法原理

   如果完成某件事共有几类不同的方法，而每类方法中，又有几种不同的方法，任选一种方法都可以完成此事，那么完成这件事的方法总数就等于各种方法的总和，这一原理称为加法原理。

  例：从甲地到乙地，一天中火车有4班，汽车有2班，轮船有3班，那么，一天中乘坐这些交通工具从甲地到乙地，共有多少种不同的走法？

   解析：把乘坐不同班次的车、船称为不同的走法。要完成从甲地到乙地这件事，可以乘火车，也可以乘汽车，还可以乘轮船，一天中，乘火车有4种走法，乘汽车有2种走法，乘轮船有3种走法。而乘坐火车、汽车、轮船中的任何一班次，都可以从甲地到乙地，符合加法原理。所以从甲地到乙地的总的走法=乘火车的4种走法+乘汽车的2种走法+乘轮船的3种走法=9种不同的走法

 （二）乘法原理

   如果做某件事，需要分几个步骤才能完成，而每个步骤又有几种不同的方法，任选一种方法都不能完成这件事，那么完成这件事的方法总数，就等于完成各步骤方法的乘积。

   例：用1、2、3、4这四个数字可以组成多少个不同的三位数？

   解析：要完成组成一个三位数这件事，要分三个步骤做，首先选百位上的数，再选十位上的数，最后选个位上的数。

   选百位上的数这一步骤中，可选1、2、3、4任何一个，共4种方法

   选十位上的数这一步骤中，可选除百位上已选好那个数字之外的三个数字，共3种方法

   选个位上的数这一步骤中，可选除百、十位上已选好的两个数字之外的另两个数字，共2种方法

   单独挑上面的任何一步中的任何一种方法，都不能组成一个三位数，符合乘法原理

   所以，可以组成：4×3×2=24（个）不同的三位数

二、加法原理和乘法原理的区别

   什么时候使用加法原理，什么时候使用乘法原理，最关键是要把握住加法原理与乘法原理的区别。从上面两个例子我们容易发现，加法原理与乘法原理最大的区别就是：如果完成一件事有几类方法，不论哪一类方法，都能完成这件事时，运用加法原理，简称为“分类-----加法”；如果完成一件事要分几个步骤，而无论哪一个步骤，都只是完成这件事的一部分，只有每一步都完成了，这件事才得以完成，这里运用乘法原理，简称为“分步----乘法”。

 三、加乘法原理的综合应用

   有时候，做某件事有几类方法，而每一类方法又要分几个步骤完成。在计算做这件事的方法时，既要用到加法原理，也要用到乘法原理，这就是加乘法原理的综合应用。

   例：从甲地到乙地有4条路可走，从乙地到丙地有2条路可走，从甲地到丙地有3条路可走，那么，从甲地到丙地共有多少种走法？

   解析：从甲地到丙地共有两大类不同的走法：可以直接从甲地到丙地，也可以从甲地先到乙地再到丙地，选择任何一类方法，都可以从甲地到丙地，符合加法原理；而在第二类方法中（即从甲地先到乙地再到丙地），又分两步完成：第一步从甲地先到乙地，有4种走法，第二步再从乙地到丙地，有2种走法，这里的任何一种方法都不能完成从甲地到丙地这件事，符合乘法原理，这时共有4×2=8种走法。

 所以从甲地到丙地总的走法=第一类方法+第二类方法

                       =3+4×2=11（种）

  四、加法原理和乘法原理的应用

   例1．（数字排列问题）用数字1、2、3、4、5可以组成多少个没有重复数字的三位数？

   解析：组成一个三位数，要分三个步骤，先选百位数，再选十位数，最后选个位数，使用乘法原理

      5×4×3=60（个）

    例2．（数字排列问题）一种电子表6点24分30秒时，显示数字是：6:2430，那么从8点到9点这段时间里，此表5个数字都不相同的情况一共有多少种？

    解析：在8点到9点间，电子表的第一位数字肯定8，在这段时间内是固定不变的，可以不考虑；第2位和第4位的取值范围只能是0、1、2、3、4、5，第3位和第5位只能从0、1、2、3、4、5、6、7、9。题中要求5个数字各不相同。所以我们要分开来考虑：

①第2位到第5位只取0----5中的数，有6×5×4×3=360种情况

②第2位和第4位只取0---5中的数，而第3位和第5位只取6、7、9中的数，有6×5×3×2=180种情况

③第2位、第3位和第4位只取0---5中的数，第5位只取6、7、9中的数，有6×5×4×3=360种情况

④第2位、第4位和第5位只取0---5中的数，第3位只取6、7、9中的数，有6×5×4×3=360种情况

所以，此表在8到9点间5个数字不同的情况共有：360+180+360+360=1260种

   例3．（数字排列问题）从1到400的所有自然数中，不含数字3的自然数有多少个？

   解析：在一位数前面添两个零，如把2写成002；在两位数前面添一个零，如把12写成012，这样，1—400中的数全成了“三位数”了，除去数字400外，考虑不含数字“3”的这样的“三位数”的个数，分三步考虑：百位、十位、个位上不含数字“3”，符合乘法原理。百位上可取0、1、2，有三种取法；十位上都可取0、1、2、4、5、6、7、8、9，有9种取法；个位与十位情况一样，也有9种取法。根据乘法原理，这样的数有：3×9×9=243（个）。数“000”不合要求，另外还需要补上符合要求的数“400”，所以不含数字“3”的自然数有：243-1+1=243（个）；（提示：这243个数中，有首位是“0”的，把“0”删掉，就成了一位数和两位数，不影响最后的个数。）

   例4．（站队排列问题）有6个同学排成一排照相，共有多少种不同的站法？

   解析：6人中任何一位的位置换了，就是一种站法。把这6个位置用字母表示为：A、B、C、D、E、F。要排成一排，要分六步，依次排A、B、C、D、E、F这六个位置，使用乘法原理；A位置中有6种站法，B位置中就只剩5种站法、、、、、如此下去，F位置上就只剩1种站法，根据乘法原理，总的站法是：6×5×4×3×2×1=720种不同的站法

  思考：看看下题与例4有何区别，又如何解答

   A、B、C、D、E 5人排成一排，如果C不站在中间，一共有多少有种不同的排法？

   例5．（取物排列问题）有5件不同的上衣，3条不同的裤子，4顶不同的帽子，从中取出一顶帽子、一件上衣和一条裤子配成一套装束，最多有多少种不同的装束？

   解析：要完成一套装束要分三步完成，先取帽子，再取上衣，最后取裤子，而每一步分别有4、5、3种不同的方法，根据乘法原理，共有4×5×3=60种不同的装束

   例6．（信号排列问题）有5面颜色不同的小旗，任意取3面排成一行表示一种信号，问：一共可以表示多少种不同的信号？

   解析：一种信号上有三个位置，要完成一种信号要分三步选好这三个位置上的小旗。而每个位置上依次有5、4、3种不同的选小旗的选法，根据乘法原理，一共可以表示：5×4×3=60种不同的信号。

  例7．（涂色问题）如图，用红、绿、蓝、黄四色去涂编号为1、2、3、4号的长方形，要求任何相邻的两个长方形的颜色都不相同，一共有多少种不同的涂法？

1	2
3	4

  解析：要分4种情况考虑：

  ① 1、2、3、4号长方形颜色都不相同，根据乘法原理，有4×3×2×1=24种涂法

  ②只有1、4号长方形同色，有4×3×2=24种

  ③只有2、3号长方形同色，有4×3×2=24种

  ④2、4和1、3号长方形分别同色，有4×3=12种

  最后用加法原理

  共有24+24+24+12=84种不同的涂法

 

   例8．深圳市的电话号码全是8位数，若前3位只能用1----9这9个数字，则深圳市可以安装多少台不同的电话号码的电话？

 解析：要确定一个电话号码，就必须确定8位数上各个位置的数字，要分八个步骤完成。使用乘法原理。根据题目要求，先确定电话号码前3位数字的取法，由于数字可以重复，前3位上的每一位置上都可以取1、2、3、4、5、6、7、8、9中的一个数，各有9种取法。电话号码中的后5位的每一位置上都可以取0、1、2、3、4、5、6、7、8、9，各有10种取法。

 根据乘法原理，共有不同的电话号码的电话：9×9×9×10×10×10×10×10=72900000台

   例9．（棋子排列问题）如图，现在要把A、B、C、D、E 5个棋子放在方格里，每行和每列只能出现一个棋子，一共有多少种放法？

解析：要将5个棋子放入格子中，要分5步完成。第一步先放A，有5×5=25个方格就有25种不同的放法；第二步放B，对应A的放法，由于不能在同一行与同一列，B放的行数和列数都会减少1，所以只能放在4×4=16个格子里，有16种放法；同理可推出，第三步放C，有3×3=9种放法；第四步放D，有2×2=4种放法；第五步放E，有1×1=1种放法。根据乘法原理。总的放法有：25×16×9×4×1=14400种