量词（接上讲）-Read.PPT

例：如果集合 S={ a, b, c}，则S的3个1-排列是 a, b, c P(3, 1)=3 S的6个2-排列是: ab, ac, ba, bc, ca, cb P(3, 2)=6 S的6个3-排列是: abc, acb, bac, bca, cab, cba P(3, 3)=6 S没有4-排列及其以上的排列, 因为S中最多只有3个元素。 排列的特征在于排出的字符串一定有顺序之分。 定理3.2.1 对于正整数n和r，若 r≤ n，则 P(n, r)＝n×(n－1)×…×(n－r＋1) 即: 我们定义n!（读作n的阶乘）为： n! = n×(n－1)×…×2 ×1 并约定0! = 1 四个对象有4！个排列。于是包含子串DEF的ABCDEF的排列数为4！=24。 DEF A B C 例2:ABCDEF的包含字母DEF不间隔任意顺序 的排列有多少个？ 例3:七个男人和五个女人坐一排开会，如果不允许两个女人坐在一起(可能是因为她们开会喜欢说话)，有多少种方法？ 解:我们可以用两步将男人和女人排列起来：先排列男人，再排列女人。男人有7！=5040种排法，一旦我们已经排好男人，因为不能有两个女人站在一起，女人有八个可能的位置可以站： _M1_M2_M3_M4_M5_M6_M7_ （这样就保证了女人不相邻） 因此女人有P(8,5)=8×7×6×5×4=6720种排列方法。根据乘法原理，七个男人和五个女人坐一排开会，如果不能有两个女人站在一起，共有：5040×6270方法。 例4 有多少取自{1, 2, …, 9}的各位互异的7位数 使得5和6不以任何顺序相继出现？ [解法一] {1, 2, …, 9}的7-排列中满足要求的可被分成4类： 1） 5，6均不出现。 即{1, 2 , 3 , 4 , 7 , 8 , 9}的7-排序P(7, 7) 2） 5出现6不出现。 即5有7个位置，其余是{1, 2 , 3 , 4 , 7 , 8 , 9}的6-排列 7×P(7, 6) 3） 5不出现6出现。 即5有7个位置，其余是{1, 2 , 3 , 4 , 7 , 8 , 9}的6-排列 7×P(7, 6) 4） 5与6同时出现，但是 a）第1位等于5。 此时6有5个位置，其余是{1, 2 , 3 , 4 , 7 , 8 , 9}的5-排列: 5×P(7，5) b）第7位等于5 。 此时6有5个位置，其余是{1, 2 , 3 , 4 , 7 , 8 , 9}的5-排列: 5×P(7，5) c）5出现在首尾之外的位置上。 此时，5有5个位置可选。对于每种5的选择，6仅 有4个位置可选。其余5位是{1, 2 , 3 , 4 , 7 , 8 , 9}的5-排列。于是 5×4×P(7，5) 综上所述，结论为 P(7,7)＋7×P(7,6)×2＋5×P(7,5)×2＋ 5×4×P(7,5) ＝151200 [解法二] 令T是{1,2,….,9}的所有7-排序的集合。 现对T构造划分S和 ,其中S是满足要求的7位数的集合 ，而 T= S ∪ ?T? = ?S? + ? ? 所以 ?S?=?T? － ? ? 而?T?＝P(9, 7) ; ? ?＝2×6×P(7, 5) 故 ?S?＝P(9, 7)－2×6×P(7, 5) ＝151200 5,6作为相连子串有:56或65之分,共有6个位置放。 以上我们讨论的是线性排列。 例如{1，2，3，4，5，6} 的两个6-排列： 5 6 1 2 3 4 与 2 3 4 5 6 1