排列與組合基礎知識

1、排列與組合基礎知識有關排列與組合的基本理論和公式:加法原理：做一件事，完成它可以有n類辦法，在第一類辦法中有nn種不同的方法，在第二類中辦法中有種不同的方法在第n類辦法中有mn種不同方法。那么完成這件事共有N = m1 + m2 +*種不同的方法，這一原理叫做加法原理。乘法原理：做一件事，完成它需要分成n個步驟，做第一步有g種不同的方法，做第二步有im種不同 的方法做第n步有g種不同的方法，那么完成這件事共有N二mjimxX4種不同的方法，這一原理叫做乘法原理。公式：階乘公式，7!= ”,（-1）。7-2）321,規(guī)定0! = 1 ;全排列公式郡=！選排列公式以'=i-1）（-2）0?

2、-帆+ 1） = -、P；=C»琮（一 ?）！圓排列：n個不同元素不分首位圍成一個圓圈達到圓排列，則排列數(shù)為：- =（77-1）! n組合數(shù)公式£：=裳=二=-一、規(guī)定= 1P：ml"? !（一。！c：=c；f、c；£ = c： + cT、c：+a+c；+禺=2"）提示：（1）全排列問題和選排列問題，都可根據(jù)乘法原理推導出來。（2）書寫方式：以記為P（n,r）： C；記為C （n,r）»加法原理例題：圖1中從A點走到B點共有多少種方法？（答案：4+2 + 3=9）乘法原理例題：圖2中從A點走到B點共有多少種方法？（答案：4X6=24）

3、加法原理與乘法原理綜合：圖3、圖4中從A走到B共有多少種方法？（答案：28、42）注意：在信息學奧賽中，有許多只需計數(shù)而不需具體方案的問題，都可以通過思維轉換或方法轉換， 最后變?yōu)閮深悊栴}：一類是轉變?yōu)榕帕薪M合問題，另一類是轉變?yōu)檫f推公式問題。因此對于加法原理、乘 法原理、排列、組合等知識，需要非常熟練，以達到簡化問題的目的。加法原理、乘法原理、排列、組合例題：1 .（1）用數(shù)字0、1、2、3能組成多少個三位數(shù)？ （2）要求數(shù)字不能重復，又能組成多少個三位數(shù)？（提示：（1）先確定百位數(shù)，只能是1、2、3之間的數(shù)字；再確定十位數(shù)，可以為0、1、2、3任何一 個；最后確定個位數(shù)，可以為0、1、2、

4、3任何一個。根據(jù)乘法原理，共有3X4X4=48個。（2）同理，先確定百位數(shù)、再確定十位數(shù)、最后確定個位數(shù)，根據(jù)乘法原理，共有3X3X2個）2 .國際會議洽談貿(mào)易，有5家英國公司，6家日本公司，8家中國公司，彼此都希望與異國的每個公司 單獨洽談一次，問需要安排多少個會談場次？（提示：共分為中英、中日、英日會談三類，對于中英會談，先選定中方公司有8種選法，在選定英 方公司有5種選法，故根據(jù)乘法原理有5X8：同理中日8X6：英日5X6：總的會談：118）3 .有編號為1、2、3、4、5的五本書需要擺放在書架上，問有多少種不同的擺放方案數(shù)。（提示：此題為全排列，故擺放方案總數(shù)為P（5,5）=5!=12

5、O種。也可以按乘法原理思考，即擺放第一本 書有5種選擇，擺放第二本數(shù)有4種選擇，最后結果為5X4X3X2X1即5!）4 .有編號為1、2、3、4、5的五本書需要任選3本書擺放在書架上，問有多少種不同方案。（提示：可根據(jù)選排列公式計算，總數(shù)為P（53）。也可以根據(jù)乘法原理計算，答案為5X4X3=60）5 .有編號為1、2、3、4、5的五本書需要任選3本書，問有多少種方法。5x4x3（提示：此題為組合問題，答案為=10）6 .五種不同顏色的珠子串成一圈項鏈，問有多少種不同的方法。（提示：此題屬于圓排列問題，答案為（5-1）! =24）7 .把兩個紅色球、兩個藍色球、三個黃色球擺放在球架上，問有多少

6、種方案。（提示：此題為排列問題。擺放方案總數(shù)為（2+2+3）!種，但是兩個紅球一樣，所以要除以2!,同理兩個藍球，除以2!,三個黃球，除以3!,即擺放方案總數(shù)為（2-2-%= 210 ）21x25x3!8 .有男女各5人，其中3對是夫妻，他們坐成一排，若每對夫妻必須相鄰而坐，問有多少種方法？ （提示：因為3對夫妻必須相鄰而坐，因此可以將每對夫妻看為一個整體進行排列，這樣排列總數(shù)為 （75）種方法，又因為每對夫妻可以可以左右調換位置，因此總的方案為（7! X2X2X2）9 .（1）把3個相同的球放到4個不同顏色的盒子中去，問有多少種方法？（2）把4個相同的球放到3個不同顏色的盒子中去，問有多少種

7、方法？（3）推廣開來，把R個相同的球放到N個不同顏色的盒子中去，問有多少種方法？（提示：這是允許重復組合的典型模型。）（解答（1）： 3個球放入4個不同顏色盒子的分法共有3、0、0、0； 1、2、0、0： 1、1、1、0三類：對于第一類3、0、0、0的方法，共有8種方法，但是有3個0是一樣的，所以應該除以反,即第一類分法的方法數(shù)為5/斤種，同理，第二種分法的方法數(shù)為弓/月，第三種分法的方法數(shù)為p: Ip;,所以總共的方法數(shù)為（p: Ip: + p: Ip; + p: /p;）種。解答（2）自行求解。解答（3）：這一類問題，我們稱為重復組合問題，其求解公式為C （n+r-l.r）o請記住該公式即

8、可。） 排列組合練習習題：1 .有5本日文書、7本英文書、10本中文書。問（1）從中任取2本書有多少種方案？ （2）從中取2本 相同文字的書有多少種方案？ （3）從中取2本不同文字的書有多少種方案？（提示：此題為組合問題。答案分別為：。；+川0、C；+C；+C；）、C3mo-（C；+C； + C；）2 .把八個“車”放在8X8的國際象棋棋盤上，如果它們兩兩均不能互吃（即在任何一行、任何一列都只 有一個“車”），那么稱八個“車”處于一個安全狀態(tài)。問共有多少種不同的安全狀態(tài)？（提示：乘法原理。先在第一行放置一個“車”，有8種選法，再在第二行放置一個“車”，還有7種 選法，同理，總共有8X7XX2X

9、1,即8!種不同的安全狀態(tài)。3 .從1300之間任取3個不同的數(shù)，使得這3個數(shù)的和正好被3除盡，問有多少種方案？（提示：1300之間的數(shù)被3除的余數(shù)共有三類，分別是余數(shù)為0、余數(shù)為1、余數(shù)為2,每類各100 個數(shù)。任取3個數(shù)且這3個數(shù)相加的和正好被3除盡的情況只能是以下四種情況之一：余數(shù)為0+1 +2： 0+0+0： 1 + 1 + 1： 2+2+2。再根據(jù)乘法原理和加法原理即可求解。答案為：100X100X100+100X99X98+100X99X98+100X99X98）4 . 5對夫婦圍繞圓桌坐下吃飯，共有多少種方案？如果要求夫婦必須坐在一起，又有多少種方案？（提示：此題為圓排列問題。第

10、一問的答案為對于第二問，因為夫婦必須坐在一起，因此 可以將每對夫婦看為一個整體先行進行圓排列，排列方案為（5 1）!,又因為每對夫婦可以左右交換 位置，因此總的排列方案為（5-1）! X2X2X2X2X2o）5 . N個男同學和N個女同學圍繞圓桌坐下，要求男女必須交替就座，問共有多少種就座方法？（提示：先經(jīng)這N個男同學進行圓排列，方案為（N-1）!,然后每個女同學依次坐入到兩個男同學中 間，第一個女同學有N個位置可以選，第二個女同學有N-1個位置可以選，依此類推。根據(jù)乘法 原理，所有的就座方案為（N-l）! XN!）6 . 8人站成一排排隊，如果其中的甲和乙兩人要求一定站在一起，問有多少種排隊

11、方法？如果甲和乙兩 人要求一定不站在一起，又有多少種方法？（提示：第一問中，甲和乙一定站在一起，因此可以先將此二人看為一個整體，則排隊方法為7!,又 因為甲和乙可以交換位置，因此總的方案為7! X2。對于第二問，則用8個人的總排隊方案數(shù)減去 甲和乙站在一起的方案數(shù)即可，答案為8! -7! X2o）7 .有N個男同學和M個女同學站成一排，其中這M個女同學要求站在一起，問共有多少種排隊方法？ （提示：排列問題+乘法原理。分兩步：第一，先將這M個女同學看成一個整體排列；第二，再將這 M個女同學再排列。然后根據(jù)乘法原理即可求得。答案為：（N+l ）! XM!）8 . 一個長度為N+M個字符的01字符串

12、，問其中有N個1的字符串有多少個？（提示：組合問題。現(xiàn)有N+M個字符，如果把1看作取字符，把?？醋鞑蝗∽址敲雌渲杏蠳個 1的字符串即相當于從N + M個字符中，任取N個字符的組合。答案為：C （N + M, N）9 . 一個N*M （N表示行，M表示列）的網(wǎng)格，從左上角（1, 1）點開始走到右下角（N, M）點，每次 只能向右或者向下走，問有多少種不同的路徑。（方法一：從（1, 1）點走到（N, M）點，無論如何走一共都要走（N-l） + （M-1）步，其中N-1步向右走，M-1步向下 走，因為只有兩種走法，不妨用二進制表示走路方式，1表示向 | 右走，0表示向下走。則可用一個長度為（N

13、+ M 2）的二進制二）串來表示走路方法，其中如果出現(xiàn)了 N-1個1,則表示找到了一11 io_2 ）_一種路徑。從而把題目轉化為求長度為N+M2的2進制串中有N-1個1的個數(shù)，即求組合數(shù)學公式C （N + M2, N-1）的值。方法二：對本題稍加分析就能發(fā)現(xiàn)，要到達棋盤上的某個點，只能從該點的上邊過來，或者從該點的左邊過來，根據(jù)加法原理，要到達該點的路徑數(shù)目，就等于到達該點上點的路徑與該點左點的路 徑數(shù)目之和，因此我們可以按照逐行遞推的方法求出從起點到終點的路徑數(shù)目。初始化，左上角第 一個元素值為1,其它點的值為上點與左點的和。)對于如右圖的網(wǎng)格，用方法一的答案為C (4+3, 3) =35

14、：用方法二逐行遞推的方法得到網(wǎng)格上的數(shù)字，最后答案也為35。比較兩種方法，當數(shù)據(jù)較小時，采用公式一比較直接，但如果數(shù)據(jù)較大時，公式一的乘法運算量較 大，這時可考慮用方法二逐行遞推求得答案。10 .在上題中，若規(guī)定N<M,行走方向仍然只能是向右或者向下行走，并且要求所經(jīng)過的每一個點的坐標 (a.b)恒滿足a<b的關系(a為行坐標，b為列坐標)，問有多少條路徑？(測試數(shù)據(jù)：N=4, M=5：答案：)11 .在上上題中，如果其中有X個點設置有障礙而無法通過，問有多少條路徑？其中X的值以及這X個點 的坐標由鍵盤輸入。(測試數(shù)據(jù)：N=5, M=4, X=2,這2個障礙點坐標為(2,3)和(4

15、,2)：答案：)12 .一個由N個0和N個1組成的01字符串，要求從左往右，1的個數(shù)始終不少于。的個數(shù)的字符串共 有多少個?如N=1時,只有字符串10；如N = 2時，有1100、1010兩個字符串；如N=3時，有111000. 110100. 110010. 101100、101010 五個字符串。(提示：該字符串的長度為2N,其中規(guī)定有N個1,即相當于從2N個字符中取出N個字符，方案數(shù) 為C (2N, N)o該題還規(guī)定從左往右，1的個數(shù)始終不少于。的個數(shù)，那么在C (2N, N)個方案 中，必定有一些排列方案不符合要求，那么是哪些不符合要求呢？我們看N=2的例子，此時所有 的排列方案有00

16、11、0101、0110、1001、1010、1100六種，其中只有1010和1100兩種方案符合要 求，為什么呢？實際上，在N=2時，即有N個1,這樣，我們將任意一個0填充到這N個1中的 方案數(shù)有N+1種，如下圖有、三個格子可以填充0,但是要保證所有的0總在1之后，因 此也就只有的位置符合要求(如1100和1010我們都認為是所有的0在1的右邊，而1001則有一 個0不在1的右邊)，即只有C (2N, N)的1/ (N+1)種方案符合要求。所以答案為：C (2N, N) / (N+l)o該數(shù)列稱為Catalan數(shù)列，其數(shù)列為1、2、5、14、42。對于此問題，有許 多變形應用，漕熟記該公自。

17、) | 1 | | 1 | (舉一反三：一個由N個。和N個1組成的01字符串，要求從左往右，1的個數(shù)始終不多于。的 個數(shù)的字符串共有多少個？同理：相當于1的位置只能排在所有0的位置之后，因此個數(shù)同樣為：C (2N, N) / (N+l )0) 13.用N個A和N個B排列成一個字符串，要求從左往右的任意一位，A的個數(shù)不能少于B的個數(shù)，問 有多少種排列方案。14 .有2N個顧客排隊購買一種產(chǎn)品，該產(chǎn)品的售價為5元，其中N個顧客手持5元的貨幣，其余N個顧 客手持10元貨幣。由于售貨員手中沒有零錢找零，因此售貨員必須將這2N個顧客按照一定的次序排 好隊，問有多少種排隊方式可以依次順利發(fā)售貨品，而不出現(xiàn)

18、無法找零的情況。15 .學校某年級參加數(shù)學、物理、化學的培訓，人數(shù)分別是150、120、100人。同時培訓數(shù)學、物理兩門課的學生有21人；同時培訓數(shù)學、化學的有16人： 廠、同時培訓物理、化學的有8人：三科都培訓的有5人。問該年級共有多少人？(提示：對于此類問題，我們可以用一個圖示法表示，從圖中我們看出，總 嚇否乙 人數(shù)即為：A + B+C ACB - BAC CnA + AGBCC=150+120+100一 21 168 + 5 = 330) 排列組合考試題：16 .在15個同學中準備選出4名同學參加國際信息學奧林匹克競賽，其中學生甲和學生乙兩人中，至少有一人必須被選中，問共有多少種選法？（

19、提示：15人中任意選出4人的總方案為C（15, 4）, 15人中選4人并且甲和乙都不選的方案為C（13, 4）,這樣答案為：C （15, 4） -C （13, 4）17 .用A、B、C、D、E、F六個字母進行排列，其字符排列中不出現(xiàn)“ACE”或“DF”字串的排列方案 有多少種？（提示：六個字母的總排列方案為P（6, 6）,又因為要求排列的字符串中不得出現(xiàn)“ACE”或“DF” 字串，因此我們可以將“ACE”看作一個整體，排列方案為P （4, 4）,將“DF”看作一個整體，排 列方案為P（5, 5）, “ACE”和“DF”同時出現(xiàn)的方案為P （3, 3）,所以答案為：P （6. 6） 一P（4,

20、4） -P （5, 5） +P （3, 3）：即 6! （4! +5!） +3!。）18 .棧的計數(shù)。編號分別為1-N （1<=N<=18）的N輛列車順序進入一個棧式結構的站臺（先進后出），試 問這N輛列車開出車站的所有可能次序有多少種序列。（此題為NOIP2003年第九屆普及組復賽試題第三題）（分析：我們用1表示進棧，。表示出棧，考慮到列車必須先進棧再出棧，因此從左到右1的個數(shù)總 不少于0的個數(shù)（即總是進棧的列車多于或等于出站的列車，否則無列車可以出棧），這樣問題就轉 化為我們已經(jīng)解決了的問題。答案為：C （2N, N） / （N+D）19 .有一排格子排成一排，己知共有8個格子

21、?，F(xiàn)有兩個不同顏色的球要放在其中，要求兩個球不能相鄰, 問共有多少種擺放方案。（提示：在所有的擺放方案中，減去兩個球相鄰的擺放方案，即將此二球看為一個整體，（注意此二球 可以左右交換位值），因為有六個格子一樣，最后需要除以年,.答案：靖二殳=42種）20 .有一排格子排成一排，已知共有8個格子?，F(xiàn)有三個不同顏色的球要放在其中，要求任意兩個球不能 相鄰，問共有多少種擺放方案。（提示：為了方便理解說明，不妨將這三個不同顏色的球編號為1、2、3號。所有的擺放方案為耳，減去任意兩個球相鄰的擺放方案，共有六種情況（即12、21、13、31、23、32）,此時需要注意三個 球相鄰的情況，三個球相鄰的情況有

22、123、312、213、321、132、231共六種情況，在減去任意兩個球 相鄰的情況時，比如減去12相鄰的情況時，三個球相鄰的情況123和312同時被減去了，同理還有其 它五種情況，說明三球相鄰的情況各被多減了一次，所以最后需要加上三球相鄰的情況。答案為：代一6歹+6”、-7 = 120 種）4紅紅藍藍藍2種）2L有一排格子排成一排，已知共有8個格子。現(xiàn)有2個紅色球和3個藍色球要放在其中，要求如下：（1） 每個格子最多擺放一個球：（2）同一種顏色的球必須相鄰擺放；（3）不同顏色的球之間至少空出一個 格子。問共有多少種擺放方案。如下是其中一種擺放方案。（提示：將每種顏色的球看作一個整體后方法同

23、上。答案:22 .有一排格子排成一排，已知共有12個格子?，F(xiàn)有3個紅色球、2個藍色球和1個黃色球要放在其中， 要求如下：（1）每個格子最多擺放一個球：（2）同一種顏色的球必須相鄰擺放：（3）不同顏色的球之 間至少空出一個格子。問共有多少種擺放方案。如下是其中一種擺放方案。紅紅藍藍黃（提示：將每種顏色的球看作一個整體后方法同上。答案：咒-6吟+6鳥=210種）23 .有一排格子排成一排，已知共有8個格子?，F(xiàn)有兩個相同的球要放在其中，要求兩個球不能相鄰，問 共有多少種擺放方案。（提示：在19題的基礎上，只是因為兩個球相同而已，所以最后需除以耳，答案:24 .有一排格子排成一排，己知共有8個格子?，F(xiàn)

24、有三個相同的球要放在其中，要求任意兩個球不能相鄰, 問共有多少種擺放方案。（提示：方法同上題，因為三個球相同，故最后需除以答案:三、實力自測（一）基本題1、某公司內有副理5人，業(yè)務員30人，工人6人，現(xiàn)欲由副理、業(yè)務員、工人中各選一人組成考核 委員會，則其選法共有多少種？ Ans: 9002、書架上有不同的國文書7本，不同的英文書4本，不同的數(shù)學書5本，不同的會計書3本。今有 一同學欲由書架上選取國文、英文、數(shù)學、會計書各一本，其取法有多少種？ Ans： 4203、由甲村到乙村有5條路可通，若一人往返甲乙村，則有多少種不同走法？ Ans: 254、試求？ Ans: 145、甲、乙、丙、丁四人排

25、成一列，則其排法有多少種？ Ans: 246、試求？ Ans: 107、用1, 2, 3, 4, 5, 6, 7七個數(shù)字排成四位數(shù)，數(shù)字不可重復，共可排多少個？ Ans: 8408、將三個相同的a,二個b, 一個c排成一列，則排法共有多少種？ Ans: 609、把五封信投入3個郵筒，方法共有幾種？ Ans: 24310、某人有5種酒，4個不同的酒杯，每杯只許倒一種酒，則有倒法有多少種？ Ans: 62511、有三所學校同日招生，若規(guī)定每人祇可報考一個學校，則四個人報考之方法共有幾種？ Ans: 8112、五對夫婦圍一圓桌而坐，則全部的排法有多少種？ Ans:9!13、承上題，男女相間而坐的方法

26、有多少種？ Ans: 288014、承上題，夫婦相鄰之坐法有多少種？ Ans: 76815、個不同的球，選4個串成一項圈之方法有有多少種？ Ans: 10516、顆不同的珠子，可串成多少種項圈？ Ans:17、若，則？ Ans: 1518、由8本書中任取3本，每次必含指定之一本在內，則方法有多少種？ Ans: 2119、平而上相異1（）點，任三點均不共線，共可決定幾個三角形？ Ans: 12020、4個相同的球，贈予2位小朋友，則其法有多少種？ Ans: 521、一學校有4個班級，選出7人組成委員會的方法有多少種？ Ans: 12022、方程式x+y+z=9有非負整數(shù)解及正整數(shù)解各共有多少個？

27、 Ans: 55,2823、展開式中若欲求第11項，貝必應取多少？ Ans: 1024、展開式中常數(shù)項為？ Ans: 1525、展開式中項之系數(shù)為？ Ans: 80（二）進階題1、一兔穴有進出口共4處，則由不同一口進出的方法有多少種？ Ans: 122、某戲院有兩個入口、三個出口，則進出戲院的方法有多少種？ Ans: 63、展開式中共有多少項？ Ans: 244、甲、乙、丙、丁、戊、己等六人排成一列，試求甲必排首，乙必排末的方法有多少種？ Ans: 245、用0, 1, 2, 3, 4, 5共六個數(shù)字，在數(shù)字不重復之下，可組成的六位數(shù)有幾個？ Ans: 6006、7人排成一列，若其中有二人必相

28、鄰的排法有1440種，則此二人必不相鄰的排法有多少種？Ans: 36007、將5元硬幣4個，1元硬幣3個，分給10位兒童，每人至多一個硬幣，則分法有多少種？ Ans： 42008、三男四女排成一列，若首尾均須排男生，則其排法有多少種？ Ans: 7209、容許重復使用1, 2, 3, 4可以作出三位數(shù)共有多少種？ Ans: 6410、容許重復使用0, 1，2, 3可以作出三位數(shù)共有多少種？ Ans: 4811、有渡船三只，每只可容納6人，今有5人，要同時安全渡河，其過渡法有多少種？ Ans: 24312、試求由0, 1, 3, 5, 7五個數(shù)字，可作出多少個四位數(shù)？ Ans: 50013、一對

29、主人夫婦邀宴四對夫婦，共圍坐一圓桌，若其中一對林姓夫婦須相鄰，而另一對陳姓夫婦不 相鄰，則其法有多少種？ Ans: 6048014、父母子女共6人圍成一圓桌而坐，若父母須相對而坐，試求其坐法有多少種？ Ans: 2415、一對夫婦及三位子女共5人圍圓桌而坐，則夫婦相鄰的坐法有多少種？ Ans: 1216、若，則？ Ans: 717、由6個英國人，5個美國人選出5人組成委員會，若委員會中至少有2個美國人，則選法有多少 種？ Ans: 38118、承上題，若委員會中英國人、美國人至少各為二人，則選法有多少種？ Ans： 35019、6本相同的書，分給甲、乙、丙三人，每人至少得一本，共有幾種分法？ Ans: 1020、x+v+z+w=12的正整數(shù)解共有幾組？ Ans： 16521、將10個相同的水果，放入4