組合數(shù)學幻燈片12

1、研究排列問題的主要目的是求出根據(jù)已知的研究排列問題的主要目的是求出根據(jù)已知的條件所能作出的不同排列的種數(shù)。條件所能作出的不同排列的種數(shù)。 分類分類 線排列線排列圓排列圓排列重排列重排列線排列是把一些元素排成一條直線線排列是把一些元素排成一條直線, ,A=A= r r是正整數(shù)，從這是正整數(shù)，從這n n個不同的元素中取個不同的元素中取r r個按照一定的個按照一定的次序排列起來次序排列起來( (rn)rn)，稱為集合稱為集合A A的的r-r-排列排列。集合集合A A的所有的所有r-r-排列的個數(shù)記為排列的個數(shù)記為P(n,r)。（定義。（定義1-11-1）注意：注意：A A的的r-r-排列為排列為A

2、A的的r r有序子集。有序子集。 例：集合例：集合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 對于正整數(shù)對于正整數(shù)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種選法種選法 由乘法

3、規(guī)則，這由乘法規(guī)則，這r個項可以有個項可以有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) 線排列例一例一：由數(shù)字：由數(shù)字1，2，3，4，5，6可以構成多少個數(shù)字互不可以構成多少個數(shù)字互不相同的四位數(shù)。相同的四位數(shù)。解：很顯然解：很顯然 這是一個排列這是一個排列P(6,4)= 360 。例二例二：將具有將具有9個字母的單詞個字母的單詞FRA

4、GMENTS進行排列，要進行排列，要求字母求字母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個元素按照個元素按照某種順序某種順序( (如逆時針如逆時針) )排成排成一個圓圈，稱這樣的排列為圓排列一個圓圈，稱這樣的排列為圓排列( (或稱循或稱循環(huán)排列環(huán)排

5、列) )。圓排列注意：把一個圓排列旋轉所得到的另一個圓排列注意：把一個圓排列旋轉所得到的另一個圓排列視為相同的圓排列。即排列視為相同的圓排列。即排列a a1 1a a2 2aar 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 在圓排列中是同一個在圓排列中是同一個. .所以圓排列的個數(shù)為所以圓排列的個數(shù)為P(n,r)/r=n!/(r(n-r)!) (1.6) P(n,r)/r=n!/(r(n-r)!) (1.6) 圓排列有有8 8人圍圓桌就餐，問有多少種就座方式人圍圓桌

6、就餐，問有多少種就座方式? ?如果有兩人不如果有兩人不愿坐在一起，又有多少種就座方式愿坐在一起，又有多少種就座方式? ?解：解：由公式由公式(1(1.6).6)知，知，8 8人圍圓桌就座一共有人圍圓桌就座一共有8!8!8=7!8=7!種種就座方式。就座方式。又由于兩人不愿坐在一起，設這兩個人為甲和乙，又由于兩人不愿坐在一起，設這兩個人為甲和乙，當甲和乙坐在一起時，相當于當甲和乙坐在一起時，相當于7 7個人圍圓桌而坐，其個人圍圓桌而坐，其就座方式為就座方式為7!7!7=6!7=6!而甲和乙坐在一起時，又有兩種情況，或者甲坐在而甲和乙坐在一起時，又有兩種情況，或者甲坐在乙的右面，或者甲坐在乙的左面

7、，這樣一來，甲和乙的右面，或者甲坐在乙的左面，這樣一來，甲和乙坐在一起時共有乙坐在一起時共有2 26!6!種就座方式種就座方式 . .例三甲和乙不坐在一起時共有就座方式的種數(shù)為甲和乙不坐在一起時共有就座方式的種數(shù)為7!26!=56!=3600 例三4 4男男4 4女圍圓桌交替就座有多少種方式女圍圓桌交替就座有多少種方式? ? 解：解：首先這是一個圓排列首先這是一個圓排列先讓四個男（女）的圍圓桌而坐，有先讓四個男（女）的圍圓桌而坐，有4!/44!/4種就座方式。種就座方式。加入一個女（男）的進去就座就有加入一個女（男）的進去就座就有4 4種方式種方式 加入第二個女（男）的又有加入第二個女（男）的

8、又有3種方式種方式 由由乘法規(guī)則乘法規(guī)則知，知，4 4男男4 4女圍圓桌交替就座的方式數(shù)為女圍圓桌交替就座的方式數(shù)為(4!/4)4321=144 例四重排列 上面我們討論了從集合上面我們討論了從集合A(AA(A中的元素是互不相中的元素是互不相同的同的) )中選中選r r個元素進行排列，在每種排列中每個元素進行排列，在每種排列中每個元素至多只出現(xiàn)一次的情況個元素至多只出現(xiàn)一次的情況 現(xiàn)在考慮元素現(xiàn)在考慮元素允許重復允許重復出現(xiàn)的情況，即考慮在出現(xiàn)的情況，即考慮在重集重集B=B=k k1 1aa1 1,k,k2 2aa2 2,k,kn naan n中選中選r r個元個元素進行的排列。素進行的排列。

9、 從從重集重集B=B=k k1 1bb1 1,k,k2 2bb2 2,k,kn nbbn n中選取中選取r r個元素按照一定的順序排列起個元素按照一定的順序排列起來，稱這種來，稱這種r-r-排列為重排列。排列為重排列。 定義1-3重集重集B=bB=b1 1,b,b2 2,b,bn n 的的r r排列的個數(shù)為排列的個數(shù)為 證明證明：選擇選擇r-排列的第一項，可以從排列的第一項，可以從n個元素中任選一個個元素中任選一個 有有n種選法種選法 第二項，由于可以重復選取，仍有第二項，由于可以重復選取，仍有n種選法種選法。 由乘法規(guī)則可求得由乘法規(guī)則可求得r排列的數(shù)目為排列的數(shù)目為rnrn定理1-3 由由

10、1，2，3，4，5，6這六個數(shù)字能組成多少個五位數(shù)這六個數(shù)字能組成多少個五位數(shù)?又可組成多少大于又可組成多少大于34500的五位數(shù)的五位數(shù)?一個五位數(shù)，數(shù)字可以重復出現(xiàn)，這是一個重一個五位數(shù)，數(shù)字可以重復出現(xiàn)，這是一個重排列問題。排列問題。由定理由定理1.31.3知，這六個數(shù)字可以組成知，這六個數(shù)字可以組成 個五位個五位數(shù)數(shù) 。解：解：56例五萬位：可選萬位：可選4 4，5 5，6 6。其余四位。其余四位任選任選所以個數(shù)為所以個數(shù)為36364 4萬位選萬位選3 3，千位選千位選5 5，6 6后三位任選，后三位任選，個數(shù)為個數(shù)為26263 3萬位和千位上的數(shù)字分別是萬位和千位上的數(shù)字分別是3和和

11、4，百位上的數(shù)字是百位上的數(shù)字是5，6 。個數(shù)為。個數(shù)為262 由加法規(guī)則知，大于由加法規(guī)則知，大于3450034500的五位數(shù)的個數(shù)為的五位數(shù)的個數(shù)為36364 4+26+263 3+26+262 2=4392=4392 例五重集重集B=nB=n1 1bb1 1,n,n2 2bb2 2,n,nk kbbk k 的全排列個數(shù)為的全排列個數(shù)為n!/n1!n2!nk! n!/n1!n2!nk! 將將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

12、,bk k2 2, ,b,bk knknk 。A A中元中元素個數(shù)為素個數(shù)為n nn1+n2+nkn1+n2+nk顯然，集合顯然，集合A A的全排列個數(shù)為的全排列個數(shù)為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! !個排列個排列( (由乘法規(guī)則由乘法規(guī)則) ) 故重集故重集B B的全排列個數(shù)為的全排列個數(shù)為n!n!n n1 1!n!n2 2!n!nk k! ! 證畢。證畢。定理1-4四面紅旗、三面藍旗、二面黃旗、五面綠旗可以組四面紅旗、三面藍旗、二面黃旗、五面綠旗可以組成多少由成多少由1414面旗子組成的一排彩旗面旗子組成的一排彩旗? ?這是一個重排列問題，它是求重集4紅旗，3藍旗，2黃旗，5綠旗的全排列的個數(shù)由定理1.4知，組成一排彩旗的種數(shù)為14!4!3!2!5! 例六解：解：用字母用字母A A、B B、C C組成五個字母的符號，要求在每個組成五個字母的符號，要求在每個符號