谈各种排列组合问题

1、谈各种排列组合问题1 引言近几十年，排列组合在计算机、规划论、运筹学、概率论等新兴学科都有广泛的应用，在这些学科的刺激下，使排列组合得到迅速的发展但由于排列组合内容的抽象性、解题的灵活多样性，在学习排列组合时要善于总结类型，巧妙地利用组合思想2 背景介绍2.1 理论背景排列组合的理论主要集中在高中和大学两个阶段在高中课本中首先介绍分类计数原则和分步计数原则，然后给出排列组合的概念及计数公式，通过例题及练习题让大家理解概念的基础上利用排列组合的思想及计数公式解决简单的排列组合问题在大学阶段排列组合是组合数学的主要组成部分，先给出解决排列组合的常用计数原则，如相等原则、加法原则、乘法原则等然后给出

2、排列组合的定义并对各种排列组合问题分类进行讨论在高中的基础上有了很大的提高2.2 历史背景排列组合具有悠久的历史，最早可追溯到公元前2200 年左右的“洛书”在我国排列组合越来越受到人们的重视，从上世纪80 年代在许多高校开设了组合数学，为了培养排列组合的思想，排列组合已安排到数学教育的各个阶段，并成为高考的难点与重点，它在其它前沿学科都有着广泛应用，使排列组合成为发展最为迅速的数学分支，充满了生机与活力3 计数原则3.1 加法原则定义1加法原则也称分类计数原则，完成一件事情有n类方法，第i类方法中有ni种方法，则n完成这件事情共有Nn1 n 2 n n n i 种方法，加法原则主要针对的是可

3、以利用分类解决i1的问题，各种方法之间相互独立，其中任何一种方法都可以独立的完成这件事情利用加法原则正确解决问题的关键是善于并正确的分类例 1 从 1 到 200 的自然数中，各位上都不含有数字5 的自然数有多少个？解 设满足条件的自然数有N 个，分为三类：第一类：一位数中不含有数字5 的有 n18 个；第二类：两位数中十位含有5 的有 10 个数，个位含有5 的有 9 个数，但55 只能除去一次，两位数中不含有5的有n290 10 9 1 72 个；第三类：三位数中十位含5 的有 10 个数，个位中含5 的有 10 个数，但155 只能除去一次，三位数中不含有5的有n3 101 10 10

4、1 82 个；3由分类计数原则N 8 72 82 162个3.2 乘法原则定义2乘法原则也称分步计数原则，完成一件事情要依次经过n个步骤，第i个步骤有ni种方n法，完成这件事情共有N n1 n2 nnni 种方法如果完成一件事情的各个步骤都完成，这i1件事情才能完成，那么计算完成这件事情的方法数就要用乘法原则，正确分步是解决该类问题的关键例 2 有 7 个人参加六项比赛，每人参加一项（ 1）有多少种参赛方法？（2） 7 人要争夺六项比赛的冠军，冠军的获得者有多少可能？解 （ 1）设有 N 种参赛方法，分为七步：第 i 步：安排第i 个人，则有6 种选择，由分步计数原则N67 种参赛方法；（ 2

5、）设冠军获得者有N 种可能，分为六步：第 i 步：安排第i 个冠军，则有7 种选择，由分步计数原则N76 种此类问题分步的关键在于，当问题模糊不清的时候， “哪一项可以多对一”，按照“多”进行分步例 3 某班联欢会上，已安排好了七个节目，开演前又增加了三个节目，把这三个节目插入到原节目当中，有多少种不同的插入方法？解 插入法，设有N 种方法，分为三步：第一步：插入第一个节目，因已安排好7 个节目有8 个空，所以n1 8 种；第二步：插入第二个节目，现有8 个节目有9 个空，所以n 2 9 种；第三步：插入第三个节目，现有9 个节目有10 个空，所以n3 10种；由分步计数原则，则N n1 n2

6、 n3 8 9 10 720 种4 排列4.1 n元集的m排列4.1.1 n元集的m线排列3（P55）定义3 设集合A为n元集，Aa1,a2 an ,从A中取出m个不同的元素，按次序排列，称为A的n元集的m线排列，其个数称为m的排列，记做作p n,m或pm.当n m时A的 排列又称为 A的全排列，其个数 pn,n又称为全排数.常用计数公式有 p n,n n!, p n,mn!n m例4某小组学生照相，其中有 8名男生7名女生.（1）将15个人排成一排，有多少种不同的排法？ （ 2）男生必须站在一起有多少种不同排法？ （3）其中有正副两名组长必须站在两端有多少种不同的排法？ （ 4）正组长必须站

7、在中间有多少种排法？解（1） 15个人排成一排，即是 15个人的全排列，p 15,1515!;（2）捆绑法，男生必须站在一起，分两步：第一步：对男生进行全排列p 8,8 8!;第二步：把男生当做一个整体作为一个元素，与7名女生进行全排列 p 8,88!.由分步计数原则 N 8! 8!种.（3）特殊元素法，分两步：第一步：先排正副组长 p 2,22! 2种；第二步：剩下13名同学进行全排列 p 13,1313!；由分步计数原则 N 2 13!种.（4）特殊位置法，正组长必须站中间，剩下的14名同学进行全排列 N p 14,14 14!例5在一次文艺晚会中，舞蹈类节目有7个，歌曲类节目有 4个，要

8、求任意两个歌曲都不相邻的节目安排方式有多少种？解插入法，分两步：第一步：先对所有舞蹈类节目进行全排列p 7,7 7!种；第二步：将4个歌曲类节目插入舞蹈节目当中，即从 8个位置中选出 4个位置进行安排歌曲8! 一，p 8,4 一种；4!由分步计数原则 N 7!冬种.4!例6 有0、1、2、3、4组成的五位数中，要求各位互异有多少种？解 方法一，直接法.分两步：第一步：安排首位，有 4种选择.第二步：剩下的四位数作全排列，p 4,4 4! 24种；由分步计数原则，N 4 24 96种；方法二，间接法.所有的五位数为 p 5,55! 120种，其中以0为首位p 4,44! 24种.所以 N 120

9、 24 96 种.4.1.2 n元集的m循环排列定义44(P26) n元集的m循环排列，集合 A为n元集，A a，a2 an .从中选取m个互异元，排在一个圆周上，并且只考虑它们在圆周上相互之间的相对位置，这样的一个排列叫做循环排列.一个循环排列可以想象成m个孩子手拉手沿圆行进.n个元素的集合 Aai,a2 an的m循环排列计数公式为 p n,m 一n一 .m m n m !例7五个人坐在一个圆桌上吃饭，(1)问有多少种就坐方法？ ( 2)若其中有两个人不愿意彼此挨着，问有多少种不同的就坐方法？解(1)由循环排列的计数公式 上刍5 5! 4! 24种；5 5(2)间接法、捆绑法.当两个人挨着时

10、，先对这两个人进行排列p 2,2 2! 2种，把这两个p 4 44!人当成一个元素与其他三个人进行循环排列"4 2 6种，这两个人不坐在一起的方法数为4 4N 24 6 18 种.例8有10个人围着圆桌而坐，其中有5男5女，要求男女交替而坐有多少种不同的就坐方法？解插入法.分两步：第一步：安排男士，有 5人围桌而坐 上05 2 24种；5 5第二步：5位男士形成5个空安排女士有 5!种；由分步计数原则 N 41 5! 24 120 2880种就坐方法.注意 在循环排列当中，因为首尾相连，所以相当于将第一个元素与最后一个元素当作一个元素进行线排列.4.2 n元集的m可重复排列定义59(

11、P7) A为n元集，A a1,a2 an ,从A中可重复的选取 m个元素，作为一个原列，则称为对 A的一个可重复排列.计数公式为n 元集的 m 可重复排列的个数为n m 例 9 七位的电话号码，其中每一位都是由0、1、29中的某个数构成，（1）有多少个电话号码？（2）若增至八位，则增加多少个电话号码？解 （ 1） 七位号码中，每一位有10 种选择，则是 10 元集的 7 可重复排列N1107个电话号码；2）间接法，升至八位则是10 元集的 8 可重复排列N2 108个电话号码，号码增加N N 2 N1108 107个电话号码例10 三位数中 a1、a2、a3其中a1 a2,a3 a2称为凹数，

12、求三位数中有多少个凹数?解 特殊元素法.按 a2进行分成10类，a2分别取0、1、2、9时.第一类：当a?。时，a1a2,a3a2 .a1，a3都有9种选择，n19 981种.第二类：当a21 时，a1a2, a3a2.a1,a3者B有8 种选择，n28 864 种.第十类：当a2 9时，a1 a2,a3 a2. a1,a3都有0种选择，n10 0种.由分类计数原则N n1 n2n10 92 820 285 个例 11 三位数中，有多少个可以被3 整除，又不含有数字9 的？解 特殊元素法，设这样的三位数有N 个，分三步：第一步：百位从1 、2、3、4、5、6、7、8 中选择，n18 种；第二步

13、：十位从0、1、2、3、4、5、6、7、8 中选择，n29 种；第三步：个位，要想三位数被3 整除，则三位数之和必为3 的倍数，设已选好的百位和十位之和除以 3 余 d 当 d 0 时， 个位从0、 3、 6 中选择 当 d 1 时，个位从 2、 5、 8中选择当 d 2时，个位从1、 4、 7 中选择所以n33种；由分步计数原则N 8 9 3 216 个4.3 多重集的排列定义6集合A由n1个a1 , n2个a2 ,，nk个ak组成，称 A为多重集，表示为An1a1，n2a2，nkak，其中n1n2nk n 7定义7多重集排列指对于多重集 A n1a1, n2 a2, nk ak中的元素进行

14、全排列，其中n n2nk n 常用的计数公式为 N2一nnkn1!n2! nk!n!n1! n2! nk!例12 某人忘记了自己的银行卡密码，但六位中有2个3,个4, 2个5, 1个8,他将这数排成一个六位数，问他最多尝试的次数为多少次?设最多尝试 N次A 2 3,1 4,2 5,1 8为多重集排列,2 12 1!6!次.13% X23x3展开式中X1 X3的系数为多少?X2X3的系数为A2 Xi,1 X3多重集的全排列,3!2!1!3.对于多重集子集的排列，关键在于正确给出所有子集.例 14 A 2 a,1 b,3C的4排列.2!1!1!2!1!2!2!180解 A 2 a,1 b,3的4排

15、列，含有4个元素的所有子集为A12 a,2 c , A2a,1 b,1 c，A3b,3c ， A4a,14!n16, n22!2!4!2!1!12,n34!1!3!n44!1!1!2!12, n5由分类计数原则，Nn1n2n3n4n512 45组合5.1 n元集的m组合定义8集合aa1,a2an为一个n元集，从一个集合，称为集合 A的n元集的m组合.计数公式为Cmn其中0 m n m! n m !例15圆上有12个点，（1）可以组成多少条直线?所以X2X3的系数为3.b,2 c , A51 a,3c.4!一 4.1!3!12 4 38 .n个元素中不重复的任意选取m个元素做成（2）可以组成多少

16、个三角形?解（1）圆上12个点中任意三个点都不共线，因为任意两个点都可以确定一条线.一_ ,212!所以有N C12266条直线;2! 12 2 !9（2）圆上的任意三点都不共线，因为任意三点都可以确定一个三角形.一，,312!所以有N C12 220个三角形.3! 12 3!例16 （均分问题）有 8本不同的书，（1）分给甲乙丙丁四个人，每人两本，有多少种不同的分法？ （ 2）分成4份，每份两本，有多少种不同的分法？解（1）分四步完成：第一步：先给甲分两本，有 n1 C； 28种；第二步：给乙分两本，有 n2 C： 15种；第三步：给丙分两本，有 n3 C； 6种；第四步：给丁分两本，有 n

17、4 C22 1种；由分步计数原则，N n1 n2 n3 n4 28 15 6 1 2520种.（2）设共有N种分法，由（1）可按如下两步进行：第一步：将8本书分成4份；第二步：将4份书分给甲乙丙丁四个人，P 4,44! 24种；由分步计数原则,N 4! C；C2C：C；, N_2_2_2_2C8c6c4c24!105 种.12注意在解决均分问题时一定要注意所分给的对象是否跟顺序有关.例17某条马路上有10盏灯，为了节约用电又不影响照明，决定同时熄灭三盏灯，但两端的不能熄灭，熄灭的两盏灯不能相邻，问有多少种熄灭方式？解 插入法，10盏灯熄灭3盏灯则剩下7盏灯，因不能熄灭两端，则有 6个空隙，让熄

18、灭的三盏灯去才1空，N C； 20种.注意 在利用插入法解决问题时，一定要注意插入的对象是否与顺序有关，若与顺序有关，则先排序后插入.例18 （1）四个相同小球放入编号为 1、2、3、4的 四个盒子中，恰有一个空盒，有多少种不同方法？（2）四个不同小球放入编号为1、2、3、4的四个盒子中，恰有一个空盒，有多少种不同方法？解（1）捆绑法，分三步完成：第一步：从四个盒子中，选一个空盒子,n1c44种;第二步：确定放两个小球的盒子，n2 C 133 种；第三步：剩下两个球分别放入两个盒子中，n3 C22 1 种；由分步计数原则，Nn1n2n3 4 3 1 12种（ 2）捆绑法，分三步完成：第一步：从四个盒子中，选一个空盒子，有n1 C14 4种；第二步：确定两个小球捆绑在一起，n2C42 6 种；第三步：把捆绑在一起