离散数学中的排列

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

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

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

4、 照此下去，只要选定了前 项，则就有 种选法来选择排列的第 项. 由乘法法则，这 个项可以有 种选法. 故有 12 , n Aa aanrn r()rnAr ,P n r AAr 10 , 0 nr P n r nr , ,Aa b cA,ab ac ba ca bc cb ,abc acb bac bca cab cba3,26,3,36PP , ,n r rn ! ,11 ! n P n rn nnr nr A r An 12 , n a aa n 1n1n 1r 1nr r r 11n nnr ! ,11 ! n P n rn nnr nr 证毕. 注意，当 时，则称 的 -排列为全排列

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

6、P n nn nn 2nr ,1,1P n rnP nr An r nA1n 1r 1,1P nr ,1,1P n rnP nr 2nr ,1,11,P n rrP nrP nr 2r ArA 1 a 1 a 1 Aa 1r 1,1P nr 1 a 1 ar 共有 个，再由加法法则有 证毕. 例1 由数字1,2,3,4,5,6可以构成多少个数字互不相同的四位数. 解：由于所有的四位数字互不相同，故一个四位数就是集合 的一个4-排列，因而符合题目要求的四位数个数是 例2 将具有9个字母的单词FRAGMENTS进行排列，要求字母A总是紧跟在字 母R的右边，问有多少种这样的排法？ 解：由于A总在R的

7、右边，故这样的排列可以看成是具有8个元素的集合 的一个全排列，其个数为 例3 5面不同颜色的旗帜，20种不同的盆花，排成两端是两面旗帜，中间 放3盆花的形式，试问有多少种不同的方案数？ 解：5面旗取2面的排列数为 20盆花取3盆的排列数为 根据乘法法则，共有的方案数为 1,P nr ,1,11,P n rrP nrP nr 1,2,3,4,5,6 6! 6,4360 64 ! P , ,F RA G M E N T S8,88!40320P 5,25 420P 20,320 19 186840P 20 6840136800N 例4 求2000到7000间的偶数中，由不同数字组成的4位数的个数.

8、 解：设这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不重复出现组成的整数的和. 解：这样的整数最多只能有4位数. 1位数4个：1,3,5,7， 2位数的个数为 个：1

9、3,15,17,31,35,37,51,53,57,71,73,75， 3位数有 个：135,137,315,317,513,517,713,715 153,173,351,371,531,571,731,751 157,175,357,375,537,573,735,753 3210 n n n n 0 n 3 n 3 n 0 n 2 1 n n 3 48,212 8 7672P 3 n 0 n 2 1 n n 2 58,2560P 4,212P 4,324P 4位数有 个：1357,1375,1537,1573,1735,1753 3157,3175,3517,3571,3715,3751

10、 5137,5173,5317,5371,5713,5731 7135,7153,7315,7351,7513,7531. 求这些数的和. 直接对这些数求和不是目的，这是枚举，枚举只是在毫无 办法时才用. 现在设法找出其中的规律性来. 注意个位、十位、百位、千位中 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 两位

11、数中个位数之和= 三位数中个位数之和= 四位数中个位数之和= (2) 的计算 两位数中十位数之和= 三位数中十位数之和= 四位数中个位数之和= 4!24 1 S 2 S 34 ,S S 1234 ,S S S S 1234 101001000SSSSS 1 S 3,1163 1648P 3,2166 1696P 3,3166 1696P 1 16 48 96 96256S 2 S 3,1163 1648P 3,2166 1696P 3,3166 1696P 2 48 96 96240S (3) 的计算： 三位数中百位数之和= 四位数中百位数之和= (4) 的计算： 四位数中千位数之和= 所以

12、3 S 3,2166 1696P 3,3166 1696P 3 96 96 192S 4 S 3,3166 1696P 256240 10 192 10096 1000S 2562400 1920096000 117856 二、圆排列二、圆排列 定义定义1.2 1.2 从集合 的 个不同元素中取出 个元素按照某 种顺序（如逆势针）排成一个圆圈，称这样的排列为圆排列（或称循环排列）. 一般用 表示. 圆排列与线排列不同之处在于圆排列头尾相邻，比如4个元素 的 排列 是不同的排列，但将它围成圆排列，其实是一回 事，属于同一个圆排列，如图1-1 而且不难理解 定理定理1.2 1.2 集合 中的 个元

13、素的 圆排列的个数为 (1.6) 证明：由于把一个圆排列旋转所得到的另一个圆排列视为相同的圆排列， 因此排列 在圆排列 中是同一个，即一个圆排列可以产生 个线排列，而总共有 个线排列. 故圆排列的个数为 12 , n Aa aa n r ,Q n r , , P n r Q n r r , , ,a b c d ,abcd dabc cdab bcda ,!P n rrnr nr An r 122313412121 , rrrrr a aaa aa aa aa a aa a aa r ,P n r ,!P n rrnr nr 例6 4男4女围圆桌交替就坐有多少种方式？ 解：显然，这是一个圆排列

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

15、先考虑5个男生围圆桌而坐的方案数，然后3个女生依次 插入，其方案数位 例8 对夫妻围一桌而坐，求每对夫妻相邻而坐的方案数. 解：夫妻相邻而坐但可交换位置所求的方案数 4! 4 (4! 4) 4 3 2 1144 8,87!5040Q 1 G 1 B 1 G 1 G 1 G 1 B 1 G5 6!5 7203660 1 B 1 G2 6!2 7201440 4! 5 4 31440 n 1 ! 2 n Nn 例9 (1)有12个人分两桌，每桌6人，围成圆桌而坐，问几种安排方案？ (2)若有12对夫妻平分为两桌，围圆桌而坐问几种方案？ 解：(1)根据乘法法则，从12个人中取6个组各作围圆桌排列，故

16、 (2) . 三、重排列 上面我们讨论了从集合 （ 中的元素是互不相同的）中选 个元素进行排列， 在每种排列中每个元素至多只出现一次的情况. 现在考虑元素允许重复出现的 情况，即考虑在重集 中选 个元素进行的排列. 定义定义1.3 1.3 从重集 中选取 个元素按照一定的顺序 排列起来，称这种 -排列为重排列. 定理定理1.3 1.3 重集 的 -排列的个数为 . 证明：构造集合 的 排列可用如下方法：在选择 -排列的第一项时， 可以从 个元素中任选一个，因此有 种选法. 在选择 -排列的第二项时，由 于可以重复选取，仍有 种选法. .同理，在选择这样排列的第 项时仍有 种选法，由乘法法则可求

17、得 -排列的数目为 . 这个定理也可叙述为：在一个具有 个不同元素的集合 中，每一个元素 都可以重复选取无限多次的 -排列的个数等于 . 同时， 的 个不同元素的 重复数都至少是 ，则定理的结论仍然成立. 2 12,65!C 2 6 12,65!2C A Ar 1122 , nn Bka kakar 1122 , nn Bk b kbkb r r 12 , n Bbbb r r n Brr nn r n r nr r n B r r n Bn r 例10 由1,2,3,4,5,6这六个数字能组成多少个五位数？又可组成多少大于 34500的五位数？ 解：一个五位数，数字可以重复出现，这是一个重排

18、列问题. 由于五位数的每一位在重集 中有6种选择， 由定理1.3知，这六个数字可以组成 个五位数. 又大于34500的五位数可由下面三种情况组成： 1）万位上的数字是4,5或6，其余四位上的数字中的每一个数字都可以从重 集 中选取6个数字，由乘法法则知，共有 个这样的数. 2）万位数是3，千位上是5,6，其余三位上的数字中的每一个都可以从重集 中选取6个数字，故共有 个这样的数. 3）万位和千位上的数字分别是3和4，百位上的数字是5,6，其余两位上的 数字中的每一个都可以从重集 中选取6个数字，故共有 个这样的数. 由 加法法则知，大于34500的五位数的个数为 定理定理1.4 1.4 重集

19、的全排列的个数为 式中 . 1,2,3,4,5,6B 5 6 B 4 3 6 B 3 2 6 B 2 2 6 432 3 62 62 64392 1122 , kk Bn b nbnb 12 ! ! k n nnn 1 k k i nn 证明：将 中 个 分别赋予上标 ，即 . 这样一来，重集 就变成具有 个不同的元素的集合 . 显然，集合 的全排 列个数为 . 又由于 个 赋予上标 的办法有 种，于是对于重集 的任 一个全排列，都可以产生集合 的 个排列（由乘法法则），故 重集 的全排列个数为 证毕. 例11 由四面红旗，三面蓝旗，二面黄旗，五面绿旗可以组成多少由14 面旗子组成的一排彩旗？

20、 解：这是一个重排列问题，它是求重集4红旗,3蓝旗,2黄旗,5绿旗 的全排列的个数，由定理1.4知，组成一排彩旗的种数为 B i n i b1,2, i n 12 121212 111222 , k nnn kkk Ab bbbbbbbb B 12k nnnn A !n i n1,2, i n i b! i nB A 12 ! k n nn B 12 ! ! k n nnn 14! 4! 3! 2! 5! 例12 用字母 组成五个字母的符号，要求在每个符号里， 至多 出现2次， 至多出现1次， 至多出现3次，求此类符号的个数. 解：这也是一个重排列的问题. 根据分析，符合题目要求的符号只有三种

21、 情况： 和 . 由定理1.4知，各 种情况对应的符号个数分别为 ， 和 由加法法则知，此类符号的个数为 , ,A B CA BC 2,0,3, 1,1,3ABCABC2,1,2ABC 5! 2!1! 2! 5! 1!1! 3! 5! 2! 0! 3! 5!5!5! 60 2! 0! 3!1!1! 3!2!1! 2! 排列的生成算法 若说以前讨论了排列的个数，这一节则将这些排列一一罗列出来. 实际工作中有时要在计算机上模拟各种排列状态下出现的情况加以分析， 下面介绍若干排列的生成算法. 序数法 同样理由可得 代人上式可得 可得0到 的整数 可以唯一地表示为 其中 满足 . !=1 !111 !

22、 11 !1 ! nn nnn nnn 1 !=22 !2 !nnnn 1 1 !=11 !22 !2 ! 11 !22 !33 !2 2! 2! ! 1 ! 111 !22 !33 !2 2! 1 1! n k nnnnnn nnnnnn k k nnnnnnn ! 1n m 1221 1 !2 !2! nn mananaa k a0,1,2,1 k ak kn 所以可以证明0到 的 个整数和序数 一一对应. 下面讨论从 求序数 的方法. 除以2，令 ，故 除以2，余数 即 . 类似 令 . ! 1n !n 1221 , nn aaa a m 1221 1 !2 !2! nn mananaa

23、 1221 , nn aaa a m 1 nm 1 n 1 r 1 a 1 212211 1 !2 ! , 222 nn nnn naaa ra 2 312322 1 !2 ! , 333 nn nnn naaa ra 1 ,1,2,1 1 i iii n nra in i 1654321 1 2654321 2 3654322 3 46 40006!5!4!3!2! 40006!5!4!3! 2000,0 222222 20006!5!4! 666,2 333!3!3! 6666 166 44 naaaaaa n naaaaa a n naaaa ar n na 5433 4 56544 6

24、655 766 !5! ,2 4!4! 1666! 33,1 555! 33 5,3 6 5 0,5 7 aa ar n naa ar na ar nar 例13 ，以 作为例子，方法可推及一 般. 令 所以 4000,6!40007!m 4000n 40005 6! 3 5! 4! 2 3! 2 2! 综上所述，满足条件 的序数 (*) 序数和 间 个整数一一对应. 下面试图将 个元素的全排列和序数 建立起一一对应关系，不失一般性， 个元素不妨令 为 . 对应的规则如下：式(*)中第一个数 表示排列中数 的右（或左） 端比 小的数的个数，将 在排列的位置确定下来，接着取 ，它表示在排列 中

25、这个数在排列中的右（或左）端比 小的数的个数，依此类推， 表 示 这个数在排列中的位置其右方（或左方）比 小的数的个数， . 以1,2,3,4的排列4213为例，排列4213，4的右方比它小的数有3位，故 3的右方比3小的数为0，故 ；2的右方比2小的数为1，故 . 故排列4213 对应于序数(301)，反过来从(301)可推得排列4213. ，故4在排列中所在位 右方比4小的数有3个，故在下列4格的排列中第一格为4. ，故3的右方没有比它小的，故在第4格填上3， ，表示2的右方有一个 比2小的，故在第2格填上2，剩下的一格填上1，便得排列4213. 现将 的序 数 与对应的排列，列于下表.

26、0,1,2,1 i ai in 1221 , nn aaa a !n0! 1n n 1221 , nn aaa a n i 1,2,n 1n a n nn 2n a 1n1n i a 1i 1i 1,2,2,1inn 3=3 a 2=0 a 1=1 a 3=3 a 4 42 21 13 3 2=0 a 1=1 a =4n 321 a a a N N排列排列N N排列排列 10 0 01 2 3 4132 0 01 4 2 3 20 0 12 1 3 4142 0 12 4 1 3 30 1 01 3 2 4152 1 01 4 3 2 40 1 12 3 1 4162 1 12 4 3 1 5

27、0 2 03 1 2 4172 2 02 4 1 2 60 2 13 2 1 4182 2 13 4 2 1 71 0 01 2 4 3193 0 04 1 2 3 81 0 12 1 4 3203 0 14 2 1 3 91 1 01 3 4 2213 1 04 1 3 2 101 1 12 3 4 1223 1 14 2 3 1 111 2 03 1 4 2233 2 04 3 1 2 121 2 13 2 4 1243 2 14 3 2 1 上面的讨论将“右”改为“左”也可以得另一种对应关系. 字典序法： 以下图为例，高度为4的树，按从树根到树叶读出边的标号顺序得一排列， 自左至右，依此

28、为 1234,1243,1324,1342,1423,1432,4321 它是按字典的顺序排列的. 由前面一个排列 到下一个排列的生成算 法，归纳其规律为： 1 12 23 3 4 4 2 2 3 34 4 1 13 3 4 4 1 1 2 24 41 12 2 3 3 3 34 42 24 4 2 2 3 33 34 41 14 41 13 32 24 41 1 4 4 1 1 2 2 2 23 31 1 3 3 1 1 2 2 4 43 34 42 23 32 24 43 34 41 13 31 14 42 24 41 12 21 13 32 23 31 12 21 1 1234 p p

29、p p S1.求满足关系式 的 的最大值，设为 ，即 S2.求满足关系式 的 的最大值，设为 ，即 S3. 与 互换得 S4.令 的 的顺序逆转便得下一个排列 例如 S1. S2. S3. 和 互换得4321 S4. 将4321中321的顺序逆转得下一个排列4123 以 的排序利用字典序生成法，可从 开始，直到 结束，即直到不存在 为止. 换位法： 下面介绍一种比较直观的排列生成法，以 为初始排列，箭头所指一 侧，相邻的数若比它小时，则称该数处在活动状态， 的2,3,4都处在活动 状态. 下面叙述从 生成下一个排列的步骤： S1.若 没有数处于活动状态则结束. S2.将处于活动状态的各数中值最大者设为 ，则 和它的箭头所指一侧相 1jj pp j i 1 max jj ij pp 1ik pp kh 1 max ik hk pp 1i p h p 12n p pp 1211iiin p ppp pp 1iin p pp 1211inni p ppp pp 1234 3421p p p p 1 max2 jj ij pp 1 max2 ik hk pp 1 p 2 p 12n 121n n 1jj pp 1,2,n 1234