离散数学中的排列

《离散数学中的排列》由会员分享，可在线阅读，更多相关《离散数学中的排列（23页珍藏版）》请在金锄头文库上搜索。

1、 排列在实际中，很多问题和计数有关. 而大量的计数问题分为两类：1. 计算事物的有序安排或有序选择数. 这又分为如下两种情况：a. 不允许任何事物重复；b. 允许事物重复2. 计算事物的无序安排和无序选择数. 这又分为如下两种情况：a.不允许任何事物重复；b. 允许事物重复第一类就是本节要讨论的排列问题，第二类就是下节要讨论的组合问题. 其实，一一对应也是计数常用的一种技巧. 最有趣而且直观的一个例子， 比如有100位乒乓球选手通过淘汰赛，最后产生一名冠军，先分50对比赛，第 一轮结束留下50名胜利者. 第二轮将50名第一轮胜出的选手分成25对进行比赛， 25名胜利者参加第三轮比赛，分12组，

2、其中一人直接参加第四轮比赛. 第四 轮开始时13名选手，分6对比赛，一人直接进入第五轮，第五轮有7人，分3组， 同样有一个直接进入第六轮；第六轮有四人，分两组，其中胜者参加最后的 决赛. 现统计共进行多少对比赛，总比赛台数50+25+12+6+3+2+1=99.其实比赛的台数和每一场比赛淘汰一名选手一一对应，100名选手要选出 一名单打冠军，必须淘汰99名，故必须进行99台比赛. 1000位选手要选出一 名单打冠军，不必犹豫回答要进行999台比赛.研究排列问题的主要目的是求出根据已知的条件所能作出的不同排列的种数.排列按照元素的排列方式可分为三种排列：1.线排列；2.圆排列；3.重排列.一、线

3、排列定义1.1 设 是具有 个元素的集合， 是正整数. 从这 个 不同的元素中取 个按照一定的次序排列起来 ，称为集合 的 -排列. 其排列数记为 . 换言之， 的 -排列为 的 有序子集.另外，为了 处理问题的方便，我们定义例如，集合 ，则集合 有6个2-排列： 和 6个3-排列： ，故有 .定理1.1 对于正整数 ，有(1.3)证明：在构造集合 的 -排列时，可以从集合 的 个元素 中 任选一个元素作为排列的第一项，这可以有 种选法. 当第一项选定后，又可以 从剩下的 个元素中任选一个元素作为排列的第二项，这又有 种选法. 照此下去，只要选定了前 项，则就有 种选法来选择排列的第 项. 由

4、乘法法则，这 个项可以有 种选法. 故有证毕.注意，当 时，则称 的 -排列为全排列，于是由公式(1.3)有推论1 当 时，有(1.4)证明：在集合 的 个元素中，任何一个元素都可以排在它的 -排列的首 位，故首元有 种取法. 当首元取定后，其他位置上的元正好是从 的另 个 元素中取 个的排列，因此有 种取法. 由乘法规则知有证毕.推论2 当 时，有(1.5)证明：当 时，把集合 的 -排列分为两大类：一类含有 中的某固定 元，比如是 ；另一类不含 . 如果先从 中选取 个元进行排列， 共有 个这样的排列. 对于每一个上述排列，可将 放入而得到 第一类排列. 由于对任一上述排列， 都有 种放入

5、方法，因此第一类排列共有 个，再由加法法则有 证毕.例1 由数字1,2,3,4,5,6可以构成多少个数字互不相同的四位数.解：由于所有的四位数字互不相同，故一个四位数就是集合 的一个4-排列，因而符合题目要求的四位数个数是例2 将具有9个字母的单词FRAGMENTS进行排列，要求字母A总是紧跟在字 母R的右边，问有多少种这样的排法？解：由于A总在R的右边，故这样的排列可以看成是具有8个元素的集合的一个全排列，其个数为例3 5面不同颜色的旗帜，20种不同的盆花，排成两端是两面旗帜，中间 放3盆花的形式，试问有多少种不同的方案数？解：5面旗取2面的排列数为20盆花取3盆的排列数为根据乘法法则，共有

6、的方案数为例4 求2000到7000间的偶数中，由不同数字组成的4位数的个数. 解：设这4位数为 ，由于偶数，故 只能取0,2,4,6,8五个数字.限制在2000到7000之间的数，故 只能取2,3,4,5,6五位数字. 分别讨论 如下：(1) 当 取2,4或6时， 只能有4种选择，而 则只能从余下的8位数字取 2个进行排列，故符合条件的数，根据乘法法则有个 (2) 若 不取2,4,6，则 有5种选择， 为余下的8位数字取2个进行排列 ，故有符合条件的偶数个数为 个根据加法法则，所求的偶数数目为 672+560=1232个例5 求由1,3,5,7不重复出现组成的整数的和.解：这样的整数最多只能

7、有4位数.1位数4个：1,3,5,7，2位数的个数为 个：13,15,17,31,35,37,51,53,57,71,73,75，3位数有 个：135,137,315,317,513,517,713,715153,173,351,371,531,571,731,751 157,175,357,375,537,573,735,7534位数有 个：1357,1375,1537,1573,1735,1753 3157,3175,3517,3571,3715,37515137,5173,5317,5371,5713,57317135,7153,7315,7351,7513,7531.求这些数的和. 直

8、接对这些数求和不是目的，这是枚举，枚举只是在毫无 办法时才用. 现在设法找出其中的规律性来. 注意个位、十位、百位、千位中 1,3,5,7的分布特点，以三位数为例，第1位为1的135,153,137,173,157,175， 其中35,53,37,73,57,75是从3,5,7中取两个的排列.令 表示个位数之和， 表示十位数之和，同理 分别是百位、千位数之 和. 求得 ，则问题所求的和数 (1) 的计算：一位数中个位数之和=1+3+5+7=16两位数中个位数之和=三位数中个位数之和=四位数中个位数之和=(2) 的计算两位数中十位数之和=三位数中十位数之和=四位数中个位数之和= (3) 的计算：

9、 三位数中百位数之和=四位数中百位数之和=(4) 的计算：四位数中千位数之和= 所以 二、圆排列定义1.2 从集合 的 个不同元素中取出 个元素按照某 种顺序（如逆势针）排成一个圆圈，称这样的排列为圆排列（或称循环排列）. 一般用 表示.圆排列与线排列不同之处在于圆排列头尾相邻，比如4个元素 的 排列 是不同的排列，但将它围成圆排列，其实是一回 事，属于同一个圆排列，如图1-1而且不难理解 定理1.2 集合 中的 个元素的 圆排列的个数为(1.6)证明：由于把一个圆排列旋转所得到的另一个圆排列视为相同的圆排列， 因此排列 在圆排列 中是同一个，即一个圆排列可以产生 个线排列，而总共有 个线排列

10、. 故圆排列的个数为例6 4男4女围圆桌交替就坐有多少种方式？ 解：显然，这是一个圆排列问题. 先让4个男的围圆桌而坐，由公式(1.6) 共有 种就坐方式. 然后加入一个女的进去就坐就有4种方式，加入第二个女 的又有3种方式，加入第三个女的又有2种方式，加入第四个女的只有一种方式. 由乘法法则知，4男4女围圆桌交替就坐的方式数为例7 5个男生，3个女生围一圆桌而坐. 若没加任何要求，则. 若要求男生 不和女生 相邻而坐有多少种方案？若要求 3个女生不相邻，又有多少方案数？解：方法1 先将 排除在外，7个人围一圆桌而坐，然后 插入. 插入 有5种选择，故 和 不相邻的方案数为 . 方法2 先求出

11、 和 相邻而坐的方案数： ， 5040-1440=3600.若3位女生不相邻. 先考虑5个男生围圆桌而坐的方案数，然后3个女生依次 插入，其方案数位例8 对夫妻围一桌而坐，求每对夫妻相邻而坐的方案数.解：夫妻相邻而坐但可交换位置所求的方案数例9 (1)有12个人分两桌，每桌6人，围成圆桌而坐，问几种安排方案？ (2)若有12对夫妻平分为两桌，围圆桌而坐问几种方案？解：(1)根据乘法法则，从12个人中取6个组各作围圆桌排列，故(2) .三、重排列上面我们讨论了从集合 （ 中的元素是互不相同的）中选 个元素进行排列， 在每种排列中每个元素至多只出现一次的情况. 现在考虑元素允许重复出现的 情况，即

12、考虑在重集 中选 个元素进行的排列.定义1.3 从重集 中选取 个元素按照一定的顺序 排列起来，称这种 -排列为重排列.定理1.3 重集 的 -排列的个数为 .证明：构造集合 的 排列可用如下方法：在选择 -排列的第一项时， 可以从 个元素中任选一个，因此有 种选法. 在选择 -排列的第二项时，由 于可以重复选取，仍有 种选法. .同理，在选择这样排列的第 项时仍有种选法，由乘法法则可求得 -排列的数目为 .这个定理也可叙述为：在一个具有 个不同元素的集合 中，每一个元素 都可以重复选取无限多次的 -排列的个数等于 . 同时， 的 个不同元素的 重复数都至少是 ，则定理的结论仍然成立.例10

13、由1,2,3,4,5,6这六个数字能组成多少个五位数？又可组成多少大于 34500的五位数？解：一个五位数，数字可以重复出现，这是一个重排列问题.由于五位数的每一位在重集 中有6种选择， 由定理1.3知，这六个数字可以组成 个五位数.又大于34500的五位数可由下面三种情况组成：1）万位上的数字是4,5或6，其余四位上的数字中的每一个数字都可以从重 集 中选取6个数字，由乘法法则知，共有 个这样的数.2）万位数是3，千位上是5,6，其余三位上的数字中的每一个都可以从重集中选取6个数字，故共有 个这样的数.3）万位和千位上的数字分别是3和4，百位上的数字是5,6，其余两位上的 数字中的每一个都可以从重集 中选取6个数字，故共有 个这样的数. 由 加法法则知，大于34500的五位数的个数为定理1.4 重集 的全排列的个数为式中 .证明：将 中 个 分别赋予上标 ，即 . 这样一来，重集 就变成具有 个不同的元素的集合. 显然，集合 的全排 列个数为 .又由于 个 赋予上标