1、研究排列问题的主要目的是求出根据已知的研究排列问题的主要目的是求出根据已知的条件所能作出的不同排列的种数。条件所能作出的不同排列的种数。分类分类 线排列线排列圆排列圆排列重排列重排列线线排列是把一些元素排成一条排列是把一些元素排成一条直线直线,A A=r r是正整数，从这是正整数，从这n n个不同的元素中取个不同的元素中取r r个按照一定的个按照一定的次序排列起来次序排列起来(rnrn)，称为集合称为集合A A的的r-r-排列排列。集合集合A A的所有的所有r-r-排列的个数记为排列的个数记为P(n,r)。（定义。（定义1-1-1 1）注意：注意：A A的的r-r-排列为排列为A A的的r r
2、有序子集。有序子集。例：集合例：集合A=a,b,c集合集合A有有6个个2-排列：排列：ab,ac,ba,ca,bc,cb 即即P(3,2)=6 A有有6个个3-排列：排列：abc,acb,bac,bca,cab,cba,即即P(3,3)=6 naaa,.,21线排列线排列定理1.1 对于正整数对于正整数n,r,rn,有有P(n,r)=n(n-1)(n-r+1)=n!(n-r)!(1.3)证明证明：集合第一项，有：集合第一项，有a1,a2,an n种选法种选法第二项，有除第一项外的第二项，有除第一项外的n-1种选法种选法.第第r项，有项，有n-r+1种选法种选法 由乘法规则，这由乘法规则，这r个
3、项可以有个项可以有n(n-1)(n-r+1)种选法。种选法。所以所以 P(n,r)=n(n-1)(n-r+1)=n!(n-r)!推论推论1 当当nr2时，有时，有 P(n,r)=nP(n-1,r-1)(1.4)推论推论2 当当nr2时，有时，有 P(n,r)=rP(n-1,r-1)+P(n-1,r)(1.5)线排列例一例一：由数字：由数字1，2，3，4，5，6可以构成多少个数字互不可以构成多少个数字互不相同的四位数。相同的四位数。解：很显然解：很显然 这是一个排列这是一个排列P(6,4)=360。例二例二：将具有将具有9个字母的单词个字母的单词FRAGMENTS进行排列，要进行排列，要求字母求
4、字母A总是紧跟在字母总是紧跟在字母R的右边，问有多少种这样的的右边，问有多少种这样的排法排法?解：解：A和和R可以算一个元素，所以这是一个可以算一个元素，所以这是一个P(8,8),P(8,8)=8!=40320。例一些一些元素排成一个圆圈的排列元素排成一个圆圈的排列 定义定义1.2从从集合集合A=A=a a1 1,a,a2 2,a,an n的的n n个不同元素中个不同元素中取出取出r r个元素按照个元素按照某种顺序某种顺序(如逆时针如逆时针)排成排成一个圆圈，称这样的排列为圆排列一个圆圈，称这样的排列为圆排列(或称循或称循环排列环排列)。圆排列注意：把一个圆排列旋转所得到的另一个圆排列注意：把
5、一个圆排列旋转所得到的另一个圆排列视为相同的圆排列。即排列视为相同的圆排列。即排列a a1 1a a2 2a ar r,a a2 2a a3 3aar ra a1 1,a a3 3aar ra a1 1a a2 2,a ar ra a1 1a a2 2aar-1r-1 在圆排列中是同一在圆排列中是同一个个.所以圆排列的个数为所以圆排列的个数为P(P(n,rn,r)/r=n!/(r(n-r)!)/r=n!/(r(n-r)!)(1.6)1.6)圆排列有有8 8人围圆桌就餐，问有多少种就座方式人围圆桌就餐，问有多少种就座方式?如果有两人不如果有两人不愿坐在一起，又有多少种就座方式愿坐在一起，又有多少
6、种就座方式?解解：由由公式公式(1(1.6).6)知，知，8 8人围圆桌就座一共有人围圆桌就座一共有8!8!8=7!8=7!种种就座方式就座方式。又由于两人不愿坐在一起，设这两个人为甲和乙，又由于两人不愿坐在一起，设这两个人为甲和乙，当甲和乙坐在一起时，相当于当甲和乙坐在一起时，相当于7 7个人围圆桌而坐，其个人围圆桌而坐，其就座方式为就座方式为7!7!7=67=6!而而甲和乙坐在一起时，又有两种情况，或者甲坐在甲和乙坐在一起时，又有两种情况，或者甲坐在乙的右面，或者甲坐在乙的左面，这样一来，甲和乙的右面，或者甲坐在乙的左面，这样一来，甲和乙坐在一起时共有乙坐在一起时共有2 26!6!种就座方
7、式种就座方式 .例三甲和乙不坐在一起时共有就座方式的种数为甲和乙不坐在一起时共有就座方式的种数为7!26!=56!=3600 例三4 4男男4 4女围圆桌交替就座有多少种方式女围圆桌交替就座有多少种方式?解：解：首先首先这是一个圆排列这是一个圆排列先让四个男（女）的围圆桌而坐，有先让四个男（女）的围圆桌而坐，有4!/44!/4种就座方式。种就座方式。加入一个女（男）的进去就座就有加入一个女（男）的进去就座就有4 4种方式种方式 加入第二个女（男）的又有加入第二个女（男）的又有3种方式种方式 由由乘法规则乘法规则知，知，4 4男男4 4女围圆桌交替就座的方式数为女围圆桌交替就座的方式数为(4!/
8、4)4321=144 例四重排列 上面我们讨论了从集合上面我们讨论了从集合A(AA(A中的元素是互不相中的元素是互不相同的同的)中选中选r r个元素进行排列，在每种排列中每个元素进行排列，在每种排列中每个元素至多只出现一次的情况个元素至多只出现一次的情况 现在考虑元素现在考虑元素允许重复允许重复出现的情况，即考虑在出现的情况，即考虑在重重集集B B=k k1 1aa1 1,k,k2 2aa2 2,k kn naan n中选中选r r个元个元素进行的排列。素进行的排列。从从重集重集B=B=k k1 1bb1 1,k,k2 2bb2 2,k kn nbbn n中选取中选取r r个元素按照一定的顺序
9、排列起个元素按照一定的顺序排列起来，称这种来，称这种r-r-排列排列为重排列。为重排列。定义1-3重重集集B B=b=b1 1,b,b2 2,b bn n 的的r r排列的个数为排列的个数为 证明证明：选择选择r-排列的第一项，可以从排列的第一项，可以从n个元素中任选一个元素中任选一个个 有有n种选法种选法 第二第二项，由于可以重复选取，仍有项，由于可以重复选取，仍有n种选法种选法。由由乘法规则可求得乘法规则可求得r排列的数目排列的数目为为rnrn定理1-3 由由1，2，3，4，5，6这六个数字能组成多少个五位数这六个数字能组成多少个五位数?又又可组成多少大于可组成多少大于34500的五位数的
10、五位数?一个五位数，数字可以重复出现，这是一个一个五位数，数字可以重复出现，这是一个重重排列排列问题问题。由由定理定理1.31.3知知，这六个数字可以，这六个数字可以组成组成 个个五五位位数数 。解：解：56例五万位：可选万位：可选4 4，5 5，6 6。其余四位。其余四位任选任选所以个数为所以个数为3 36 64 4万位选万位选3 3，千位选千位选5 5，6 6后三位任选，后三位任选，个数为个数为2 26 63 3万位和千位上的数字分别是万位和千位上的数字分别是3和和4，百位上的数字是百位上的数字是5，6。个数为。个数为262 由加法规则知，大于由加法规则知，大于3450034500的五位数
11、的个数为的五位数的个数为36364 4+26+263 3+26+262 2=4392=4392 例五重集重集B=nB=n1 1bb1 1,n,n2 2bb2 2,n nk kbbk k 的全的全排列个数为排列个数为n!/n1!n2!n!/n1!n2!nknk!将将B B中的中的n ni i个个b bi i分别赋予上标分别赋予上标1 1，2 2，n ni i，即即B=A=b b1 11 1,b,b1 12 2,b,b1 1n1n1,b bk k1 1,b,bk k2 2,b,bk knknk。A A中元中元素个数为素个数为n nn1+n2+nkn1+n2+nk显然，集合显然，集合A A的全排列个
12、数为的全排列个数为n n!。定理1-4证明证明：),2,1(,21kibbbiniii又由于又由于n ni i个个b bi i赋予上标赋予上标1 1，2 2，n ni i的办法有的办法有n ni i!种种 对于重集对于重集B B的任一个全排列，都可以产生集合的任一个全排列，都可以产生集合A A的的n n1 1!n!n2 2!n nk k!个排列个排列(由乘法规则由乘法规则)故重集故重集B B的全排列个数为的全排列个数为n!n!n n1 1!n!n2 2!n nk k!证证毕。毕。定理1-4四面红旗、三面蓝旗、二面黄旗、五面绿旗可以组四面红旗、三面蓝旗、二面黄旗、五面绿旗可以组成多少由成多少由1
13、414面旗子组成的一排彩旗面旗子组成的一排彩旗?这是一个重排列问题，它是求重集4红旗，3蓝旗，2黄旗，5绿旗的全排列的个数由定理1.4知，组成一排彩旗的种数为14!4!3!2!5!例六解：解：用字母用字母A A、B B、C C组成五个字母的符号，要求在每个组成五个字母的符号，要求在每个符号里，符号里，A A至多出现至多出现2 2次，次，B B至多出现至多出现1 1次，次，C C至多至多出现出现3 3次，求此类符号的个数。次，求此类符号的个数。这也是一个重排列问题。根据分析，符合题目要求的符号只有三种情况：2A，0B，3C，1A，1B，3C和2A，1B，2C。解：由定理1.4和加法规则知：此类符号的个数为5!/2!0!3!+5!/1!1!3!+5!/2!1!2!=60 例七
