从头学习排列组合-适合公务员复习

4排列组合课本从古到今，人们在社会生活的各个方面都常需要进行计数，如电话号码的编排、密码的设定、彩票设计、集成电路的布线安排，以及电子计算机的程序编制……，等等．本章中，我们将研究●怎样用数学模型刻画计数问题？●如何利用计数模型解决实际问题？序言两个基本原理调查某市职工和农民家庭中按人均月收入划分的户数如下户数500以下500元以上合计城市职工8221229农民413358771合计4215791000根据这组数据分别估计在该市任取一家庭，其人均月收入在500以下元的概率和在该市任取两个家庭，其中一个家庭人均月收入在500以下，另一家庭人均月收入在500元以上的概率。●上述两个问题有怎样的区别？他们都是计数问题，但在问题（1）中，任选一种方法都能达到完成事件的目的，而在问题（2）中，必须分为两个步骤，依次连续完成全部的步骤，才能达到完成该事件的目的．首先考察问题（1）．乘坐汽车有3班，每一班汽车都可以完成从甲地到乙地这件事，而乘火车有2班，每一班火车也都能完成从甲地到乙地这件事，所以共有3+2=5种不同的走法．再考察问题（2）．必须经过先从甲地走到乙地，再从乙地到丙地两个步骤，才能完成从甲地经乙地到丙地这件事．从甲地走到乙地有3走法，从乙地到丙地有2种走法．所以，从甲地经乙地到丙地共有2×5=10种不同的走法．5一般地，我们有分类加法计数原理完成一件事，有n类方式，在第1类方式中有m1种不同的方法，在第2类方式中有m2种不同的方法……在第n类方式中有mn种不同的方法．那么完成这件事共有N=m1+m2+…+mn种不同的方法．和分步乘法计数原理完成一件事，需要分成n个步骤，做第1步有m1种不同的方法，做第2步有m2种不同的方法……做第n步有mn种不同的方法．那么完成这件事共有N=m1m2…mn种不同的方法．例1某班共有男生28名、女生20名，欲从该班选出学生代表参加校学代会．（1）若学校分配给该班1名代表，有多少种不同的选法？（2）若学校分配给该班男、女生代表各1名，有多少种不同的选法？解（1）选出1名代表有2类办法：第1类办法是从男生中选出1名代表，有28种方法；第2类办法是从女生中选出1名代表，有20种方法．根据分类加法计数原理，不同的选法种数是N=m1+m2=28+20=48．（2）选出男、女生代表各1名，可以分成2个步骤完成：第1步，选1名男生代表，有28种方法；第2步，选1名女生代表，有20种方法．根据分步乘法计数原理，选出男、女生代表各1名，不同的选法种数是N=m1×m2=28×20=560．答选出1名代表有48种不同的选法；选出男、女生代表各1名，有560种不同的选法．例2要从甲、乙、丙3名工人中选出2名分别上日班和晚班，有多少种不同的选法？分析我们可以从甲、乙、丙3名工人中任选1人上日班，再从余下的两人中任选1人上晚班．为了便于分析，可画出如下的树图：分步乘法计数原理又称为乘法原理．分类加法计数原理又称为加法原理．画树形图可清楚地显示选法的情况．甲乙丙乙甲丙丙甲乙6解从3名工人中选出2名分别上日班和晚班，可以分两个步骤来完成：第1步，先从甲、乙、丙3名工人中任选1名上日班，共有3种选法；第2步，从余下的2名工人中任选1名工人上晚班，有2种选法．根据分步乘法计数原理，所求的不同的选法数是N=32=6．答从3名工人中选出2名分别上日班和晚班，有6种不同的选法．例3（1）在图1.1.3的电路中，只合上一只开关以接通灯泡，有多少种不同的方法？（2）在图7.1.2中，分别在A、B中各合上一只开关以使电路接通，有多少种不同的通电线路？解（1）在图7.1.3按要求接通灯泡，只要在A中的两个开关或B中的三个开关中合上一只开关，就能使灯泡接通。故有2+3=5种不同的方法。（2）在图7.1.4中，按要求接通灯泡必须分两步进行：第一步，合上A中的一只开关，第二步，再合上B中的一只开关。故有2×3=6种不同的通电线路。答图7.1.3的电路中，只合上一只开关以接通灯泡，有5种不同的方法，图7.1.2中，分别在A、B中各合上一只开关以使电路接通，有6种不同的通电线路。例4许多网站提供免费电子信箱的服务．为了确保电子信箱的安全，在注册时，通常要设置电子信箱密码．（1）甲网站规定：信箱密码为4位，每位均为0到9这10个数字中的一个数字．那么在甲网站可注册多少个免费电子信箱？（2）乙网站规定：信箱密码为4位，每位是0到9这10个数字中的一个，或是从A到Z这26个字母中的1个．那么在乙网站可注册多少个免费电子信箱？图1.1.3图1.1.47（3）丙网站规定：信箱密码为4~6位，每位均为0到9这10个数字中的一个．那么在丙网站可注册多少个免费电子信箱？解（1）设置四位密码，每一位上都可以从0到9这10个数字中任取一个，有10种取法．根据分步乘法计数原理，四位密码的个数是N=10×10×10×10=10000．（2）设置四位密码，每一位上都可以从0到9这10个数字或从字母A到Z这26个字母中任取一个，共有10+26=36种取法．根据分步乘法计数原理，四位密码的个数是N=36×36×36×36=1679616．（3）设置一个由0到9这10个数字组成的4~6位密码，有3类办法：第一类办法是设置4位密码；第二类办法是设置5位密码；第三类办法是设置六位密码．第一类办法可以设置4位密码的个数为m1=10×10×10×10=104；同理，第二、三类办法可以设置5，6位密码的个数分别为m2=105，m3=106．根据分类加法计数原理，设置由数字0到9组成的4~6位密码的个数是N=m1+m2+m3=104+105+106=1110000．答在甲、乙和丙网站分别可注册10000，1679616，1110000个免费电子信箱．一排列某城市的一种彩票的规则是：将写有1到9九个数字规格相同的小球放入摇奖器内，依次随机摇出5个小球，当彩票号码与摇出的小球的号码（包括顺序）全部相同时，中一等奖，当彩票号码中有四个数字（包括顺序）相同时，中二等奖。一彩民买一张彩票，中一等奖和中二等奖的概率各有多大？设摇出的所有号码组成集合A，则中一等奖的概率为1Card(A),中二等奖的概率为2Card(A)，那么●用怎样的数学模型处理这种计数问题？计算Card(A)就是确定从1到9九个数字中依次抽取5个数字组成的五位数的个数，为简便起见，我们先研究将1到3三个数字依次抽出的情形：8将所有可能的情形用树形图表示：即共有6种不同的结果：123，132，213，231，312，321。事实上，这6种填法都是将1，2，3三个数字按一定的顺序排成了一列，我们将它们叫做用1，2，3三个元素的一个排列。如果考虑从1到9这九个数字从任选5个排成一列，那么可得到12345，12346，12347，…，56789等排法，其中每一种排法都称为从1到9这九个数字中选取5个数字所成的一个排列。一般地，从n个不同的元素中取出m(m≤n)个元素，按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列（Arrangement）．例1写出从a，b，c，d这4个元素中，每次取出2个元素的所有排列．解把a，b，c，d中的任意一个元素排在第一个位置上，有4种方法；第一个位置上的元素排好后，第二个位置上的元素就有3种排法．若第一个位置是a，那么第二个位置可以是b，c，或d，有三种排法，即ab，ac，ad．同理，第一个位置更换为b，c，或d，也分别各有三种排列，即共计有12种不同的排列，它们是ab，ac，ad，ba，bc，bd，ca，cb，cd，da，db，dc．abcbcdacdabddabc图1-2-3如无特别说明，取出若个元素都是指无重复地选取．第1个数第2个数第3个数123322133131221图1-2-19例2写出从a，b，c，d这4个元素中，每次取出3个元素的所有排列．解根据例1，从4个元素中每次取出2个元素的排列有12种，在每一种这样的排列后面排上其余两个元素的每一个，就得到取3个元素的所有排列．可以画出树图如下．共计有24种不同的排列，它们是abc，abd，acb，acd，adb，adc，bac，bad，bca，bcd，bda，bdc，cab，cad，cba，cbd，cda，cdb，dab，dac，dba，dbc，dca，dcb．按所给元素的先后顺序，依次考虑第一位、第二位、……各个位置上所有可能的变化，既保证了所有的排列无重复无遗漏，又保证了每一个排列里的元素无重复无遗漏．对3个元素的排列，我们很容易用树形图一一列举，但对从1到9九个数字从选出5个数字的所有排列，若用树形图列举就比较麻烦了。这时应该怎么办呢？从前面的排树形图的过程可以看出，处理排列问题可分步进行。对此问题可分3个步骤，从第1位到第3位分别选排：第1位可从这9个元素中任意取出一个来排，有9种方法；第2位从剩下的8个元素里任选一个来排，有8种排法；第3位从剩下的7个元素里任选一个来排，有7种排法（如图7-2-3）．三个位置排毕，构造一个排列的事件完成，根据乘法原理可知从9个元素中每次选取3个元素共可排成的排列的个数为987×6×5=15120，即有15120种不同的排列．一般地，我们把从n个不同元素中取出m（m≤n）个元素的所图1-2-4abcbcdacdabddabccbbcaabaabaaddcddcddbccb第1位第2位第3位第4位第5位9种方法8种方法7种方法图7-2-56种方法5种方法10有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号Amn表示，如A59=15120．“排列”与“排列数”有何区别与联系？对一般情况，从n个元素中，每次取出m个元素的排列，可把这m个元素所排列的位置划分为第1位，第2位，……第m位（如图7-2-4）．第1步第1位可以从n个元素中任选1个来排，有n种方法；第2步第2位只能在余下的n1个元素中任选1个来排，有n1种方法；第3步第3位只能在余下的n2个元素中任选1个来排，有n2种方法；……第m步第m位只能在余下的n(m1)个元素中任选1个来排，有nm+1种方法．m个位置排毕，事件完成，根据乘法原理，共有n(n1)(n2)…(nm+1)种填法．因此，我们得到排列数公式Amn=n(n1)(n2)…(nm+1)，其中n，mN*，且m≤n．排列数公式有如下特点：（1）它是m个连续正整数的积；（2）第一个因数最大，它是A的下标n；（3）第m个因数，即最后一个因数最小，它是A的下标n减去上标m再加1．n个不同元素全部取出的一个排列，叫做n个不同元素的一个全排列．在排列数公式中，当m=n时，即有Ann=n·(n1)·(n2)·…·3·2·1，称为n的阶乘（Factorial），通常用n!表示，即Ann=n！．思考第1位第2位第3位……第m位n种方法n1种方法n2种方法图7-2-6nm+1种方法右边的第一个因数是n，后面的因数都比它前面一个因数少1，共有n个因数相乘．排列数符号Amn在有的书中记为Pmn．11例62004年，首届中超足球联赛共有12支球队参加，每队都要与其余各队在主、客场分别比赛1次，共要进行多少场比赛？分析由于任何2队间进行1次主场比赛与1次客场比赛，表明比赛与主客场的顺序有关，所以本题相当于从12个不同元素中任取2个元素的一个排列．解原问题对应于从12个不同元素中任取2个元素的一个排列，因此总共进行的比赛场次是A212=1211=132（场）．答共要进行132场比赛．例7（1）有5本．不同的书，从中选3本送给3名同学，每人各1本，共有多少种不同的送法？（2）有5种．不同的书，要买3本送给3名同学，每人各1本，共有多少种不同的送法？解（1）从5本不同的书中选出3本分别送给3名同学，对应于从5个元素中任取3个元素的一个排列，因此不同送法的种数是A35=543=60．（2）送给第个同学1本书有5种不同的选购方法，送给第2、第3个同学1本书，仍各有5种不同的选购方法，因此，根据乘法原理，送给3名同学每人各1本书的不同方法种数是