信息學(xué)奧賽輔導(dǎo)排列與組合基礎(chǔ)知識

1、排列與組合基礎(chǔ)知識有關(guān)排列與組合的基本理論和公式：加法原理：做一件事，完成它可以有n類辦法，在第一類辦法中有m1種不同的方法，在第二類中辦法中有m2種不同的方法，在第n類辦法中有mn種不同方法。那么完成這件事共有Nm1m2mn種不同的方法，這一原理叫做加法原理。乘法原理：做一件事，完成它需要分成n個步驟，做第一步有m1種不同的方法，做第二步有m2種不同的方法，做第n步有mn種不同的方法，那么完成這件事共有Nm1m2mn種不同的方法，這一原理叫做乘法原理。公式：階乘公式，規(guī)定0！1；全排列公式選排列公式、圓排列：n個不同元素不分首位圍成一個圓圈達(dá)到圓排列，則排列數(shù)為：組合數(shù)公式、規(guī)定、）提示：（

2、1）全排列問題和選排列問題，都可根據(jù)乘法原理推導(dǎo)出來。（2）書寫方式：記為P（n,r）；記為C（n,r）。加法原理例題：圖1中從A點走到B點共有多少種方法？（答案：4239）乘法原理例題：圖2中從A點走到B點共有多少種方法？（答案：4624）加法原理與乘法原理綜合：圖3、圖4中從A走到B共有多少種方法？（答案：28、42） 注意：在信息學(xué)奧賽中，有許多只需計數(shù)而不需具體方案的問題，都可以通過思維轉(zhuǎn)換或方法轉(zhuǎn)換，最后變?yōu)閮深悊栴}：一類是轉(zhuǎn)變?yōu)榕帕薪M合問題，另一類是轉(zhuǎn)變?yōu)檫f推公式問題。因此對于加法原理、乘法原理、排列、組合等知識，需要非常熟練，以達(dá)到簡化問題的目的。加法原理、乘法原理、排列、組合例

3、題：1. （1）用數(shù)字0、1、2、3能組成多少個三位數(shù)？（2）要求數(shù)字不能重復(fù)，又能組成多少個三位數(shù)？（提示：（1）先確定百位數(shù)，只能是1、2、3之間的數(shù)字；再確定十位數(shù)，可以為0、1、2、3任何一個；最后確定個位數(shù)，可以為0、1、2、3任何一個。根據(jù)乘法原理，共有34448個。（2）同理，先確定百位數(shù)、再確定十位數(shù)、最后確定個位數(shù)，根據(jù)乘法原理，共有332個）2. 國際會議洽談貿(mào)易，有5家英國公司，6家日本公司，8家中國公司，彼此都希望與異國的每個公司單獨洽談一次，問需要安排多少個會談場次？（提示：共分為中英、中日、英日會談三類，對于中英會談，先選定中方公司有8種選法，在選定英方公司有5種選

4、法，故根據(jù)乘法原理有58：同理中日86；英日56；總的會談：118）3. 有編號為1、2、3、4、5的五本書需要擺放在書架上，問有多少種不同的擺放方案數(shù)。（提示：此題為全排列，故擺放方案總數(shù)為P(5,5)=5!=120種。也可以按乘法原理思考，即擺放第一本書有5種選擇，擺放第二本數(shù)有4種選擇，最后結(jié)果為54321即5！）4. 有編號為1、2、3、4、5的五本書需要任選3本書擺放在書架上，問有多少種不同方案。（提示：可根據(jù)選排列公式計算，總數(shù)為P(5,3)。也可以根據(jù)乘法原理計算，答案為54360）5. 有編號為1、2、3、4、5的五本書需要任選3本書，問有多少種方法。（提示：此題為組合問題，答

5、案為10）6. 五種不同顏色的珠子串成一圈項鏈，問有多少種不同的方法。（提示：此題屬于圓排列問題，答案為（51）！24）7. 把兩個紅色球、兩個藍(lán)色球、三個黃色球擺放在球架上，問有多少種方案。（提示：此題為排列問題。擺放方案總數(shù)為（223）！種，但是兩個紅球一樣，所以要除以2！，同理兩個藍(lán)球，除以2！，三個黃球，除以3！，即擺放方案總數(shù)為）8. 有男女各5人，其中3對是夫妻，他們坐成一排，若每對夫妻必須相鄰而坐，問有多少種方法？（提示：因為3對夫妻必須相鄰而坐，因此可以將每對夫妻看為一個整體進(jìn)行排列，這樣排列總數(shù)為（7!）種方法，又因為每對夫妻可以可以左右調(diào)換位置，因此總的方案為（7！222）

6、9. （1）把3個相同的球放到4個不同顏色的盒子中去，問有多少種方法？（2）把4個相同的球放到3個不同顏色的盒子中去，問有多少種方法？（3）推廣開來，把R個相同的球放到N個不同顏色的盒子中去，問有多少種方法？（提示：這是允許重復(fù)組合的典型模型。）（解答（1）：3個球放入4個不同顏色盒子的分法共有3、0、0、0；1、2、0、0；1、1、1、0三類；對于第一類3、0、0、0的方法，共有種方法，但是有3個0是一樣的，所以應(yīng)該除以，即第一類分法的方法數(shù)為種，同理，第二種分法的方法數(shù)為，第三種分法的方法數(shù)為，所以總共的方法數(shù)為（）種。 解答（2）自行求解。 解答（3）：這一類問題，我們稱為重復(fù)組合問題，

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

8、 從1300之間任取3個不同的數(shù)，使得這3個數(shù)的和正好被3除盡，問有多少種方案？（提示：1300之間的數(shù)被3除的余數(shù)共有三類，分別是余數(shù)為0、余數(shù)為1、余數(shù)為2，每類各100個數(shù)。任取3個數(shù)且這3個數(shù)相加的和正好被3除盡的情況只能是以下四種情況之一：余數(shù)為012；000；111；222。再根據(jù)乘法原理和加法原理即可求解。答案為：100100100100999810099981009998）4. 5對夫婦圍繞圓桌坐下吃飯，共有多少種方案？如果要求夫婦必須坐在一起，又有多少種方案？（提示：此題為圓排列問題。第一問的答案為（101）！。對于第二問，因為夫婦必須坐在一起，因此可以將每對夫婦看為一個整體

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

10、為一個整體，則排隊方法為7！，又因為甲和乙可以交換位置，因此總的方案為7！2。對于第二問，則用8個人的總排隊方案數(shù)減去甲和乙站在一起的方案數(shù)即可，答案為8！7！2。）7. 有N個男同學(xué)和M個女同學(xué)站成一排，其中這M個女同學(xué)要求站在一起，問共有多少種排隊方法？（提示：排列問題乘法原理。分兩步：第一，先將這M個女同學(xué)看成一個整體排列；第二，再將這M個女同學(xué)再排列。然后根據(jù)乘法原理即可求得。答案為：（N1）！M?。?. 一個長度為NM個字符的01字符串，問其中有N個1的字符串有多少個？（提示：組合問題。現(xiàn)有NM個字符，如果把1看作取字符，把0看作不取字符，那么其中有N個1的字符串即相當(dāng)于從NM個字符

11、中，任取N個字符的組合。答案為：C（NM，N）9. 一個N*M（N表示行，M表示列）的網(wǎng)格，從左上角（1，1）點開始走到右下角（N，M）點，每次只能向右或者向下走，問有多少種不同的路徑。（方法一：從（1，1）點走到（N，M）點，無論如何走一共都要走（N1）（M1）步，其中N1步向右走，M1步向下走，因為只有兩種走法，不妨用二進(jìn)制表示走路方式，1表示向右走，0表示向下走。則可用一個長度為（NM2）的二進(jìn)制串來表示走路方法，其中如果出現(xiàn)了N1個1，則表示找到了一種路徑。從而把題目轉(zhuǎn)化為求長度為NM2的2進(jìn)制串中有N1個1的個數(shù)，即求組合數(shù)學(xué)公式C（NM2，N1）的值。方法二：對本題稍加分析就能發(fā)現(xiàn)

12、，要到達(dá)棋盤上的某個點，只能從該點的上邊過來，或者從該點的左邊過來，根據(jù)加法原理，要到達(dá)該點的路徑數(shù)目，就等于到達(dá)該點上點的路徑與該點左點的路徑數(shù)目之和，因此我們可以按照逐行遞推的方法求出從起點到終點的路徑數(shù)目。初始化，左上角第一個元素值為1，其它點的值為上點與左點的和。）對于如右圖的網(wǎng)格，用方法一的答案為C（43，3）35；用方法二逐行遞推的方法得到網(wǎng)格上的數(shù)字，最后答案也為35。比較兩種方法，當(dāng)數(shù)據(jù)較小時，采用公式一比較直接，但如果數(shù)據(jù)較大時，公式一的乘法運算量較大，這時可考慮用方法二逐行遞推求得答案。10. 在上題中，若規(guī)定NM，行走方向仍然只能是向右或者向下行走，并且要求所經(jīng)過的每一個

13、點的坐標(biāo)(a,b)恒滿足ab的關(guān)系（a為行坐標(biāo)，b為列坐標(biāo)），問有多少條路徑？（測試數(shù)據(jù)：N4，M5；答案：）11. 在上上題中，如果其中有X個點設(shè)置有障礙而無法通過，問有多少條路徑？其中X的值以及這X個點的坐標(biāo)由鍵盤輸入。（測試數(shù)據(jù)：N5，M4，X2，這2個障礙點坐標(biāo)為（2,3）和（4,2）；答案：）12. 一個由N個0和N個1組成的01字符串，要求從左往右，1的個數(shù)始終不少于0的個數(shù)的字符串共有多少個？如N1時，只有字符串10；如N2時，有1100、1010兩個字符串；如N3時，有111000、110100、110010、101100、101010五個字符串。（提示：該字符串的長度為2N，

14、其中規(guī)定有N個1，即相當(dāng)于從2N個字符中取出N個字符，方案數(shù)為C（2N，N）。該題還規(guī)定從左往右，1的個數(shù)始終不少于0的個數(shù)，那么在C（2N，N）個方案中，必定有一些排列方案不符合要求，那么是哪些不符合要求呢？我們看N2的例子，此時所有的排列方案有0011、0101、0110、1001、1010、1100六種，其中只有1010和1100兩種方案符合要求，為什么呢？實際上，在N2時，即有N個1，這樣，我們將任意一個0填充到這N個1中的方案數(shù)有N1種，如下圖有、三個格子可以填充0，但是要保證所有的0總在1之后，因此也就只有的位置符合要求（如1100和1010我們都認(rèn)為是所有的0在1的右邊，而100

15、1則有一個0不在1的右邊），即只有C（2N，N）的1（N1）種方案符合要求。所以答案為：C（2N，N）（N1）。該數(shù)列稱為Catalan數(shù)列，其數(shù)列為1、2、5、14、42。對于此問題，有許多變形應(yīng)用，請熟記該公式。）11（舉一反三：一個由N個0和N個1組成的01字符串，要求從左往右，1的個數(shù)始終不多于0的個數(shù)的字符串共有多少個？同理：相當(dāng)于1的位置只能排在所有0的位置之后，因此個數(shù)同樣為：C（2N，N）（N1）。）13. 用N個A和N個B排列成一個字符串，要求從左往右的任意一位，A的個數(shù)不能少于B的個數(shù)，問有多少種排列方案。14. 有2N個顧客排隊購買一種產(chǎn)品，該產(chǎn)品的售價為5元，其中N個顧

16、客手持5元的貨幣，其余N個顧客手持10元貨幣。由于售貨員手中沒有零錢找零，因此售貨員必須將這2N個顧客按照一定的次序排好隊，問有多少種排隊方式可以依次順利發(fā)售貨品，而不出現(xiàn)無法找零的情況。15. 學(xué)校某年級參加數(shù)學(xué)、物理、化學(xué)的培訓(xùn)，人數(shù)分別是150、120、100人。同時培訓(xùn)數(shù)學(xué)、物理兩門課的學(xué)生有21人；同時培訓(xùn)數(shù)學(xué)、化學(xué)的有16人；同時培訓(xùn)物理、化學(xué)的有8人；三科都培訓(xùn)的有5人。問該年級共有多少人？（提示：對于此類問題，我們可以用一個圖示法表示，從圖中我們看出，總?cè)藬?shù)即為：ABCABBCCAABC150120100211685330）排列組合考試題：16. 在15個同學(xué)中準(zhǔn)備選出4名同學(xué)

17、參加國際信息學(xué)奧林匹克競賽，其中學(xué)生甲和學(xué)生乙兩人中，至少有一人必須被選中，問共有多少種選法？（提示：15人中任意選出4人的總方案為C（15，4），15人中選4人并且甲和乙都不選的方案為C（13，4），這樣答案為：C（15，4）C（13，4）17. 用A、B、C、D、E、F六個字母進(jìn)行排列，其字符排列中不出現(xiàn)“ACE”或“DF”字串的排列方案有多少種？（提示：六個字母的總排列方案為P（6，6），又因為要求排列的字符串中不得出現(xiàn)“ACE”或“DF”字串，因此我們可以將“ACE”看作一個整體，排列方案為P（4，4），將“DF”看作一個整體，排列方案為P（5，5），“ACE”和“DF”同時出現(xiàn)的方案

18、為P（3，3），所以答案為：P（6，6）P（4，4）P（5，5）P（3，3）；即6?。?！5?。?！。）18. 棧的計數(shù)。編號分別為1N（1=N=18）的N輛列車順序進(jìn)入一個棧式結(jié)構(gòu)的站臺（先進(jìn)后出），試問這N輛列車開出車站的所有可能次序有多少種序列。（此題為NOIP2003年第九屆普及組復(fù)賽試題第三題）（分析：我們用1表示進(jìn)棧，0表示出棧，考慮到列車必須先進(jìn)棧再出棧，因此從左到右1的個數(shù)總不少于0的個數(shù)（即總是進(jìn)棧的列車多于或等于出站的列車，否則無列車可以出棧），這樣問題就轉(zhuǎn)化為我們已經(jīng)解決了的問題。答案為：C（2N，N）（N1）19. 有一排格子排成一排，已知共有8個格子?，F(xiàn)有兩個不同顏色的球要放在其中，要求兩個球不能相鄰，問共有多少種擺放方案。（提示：在所有的擺放方案中，減去兩個球相鄰的擺放方案，即將此二球看為一個整體，（注意此二球可以左右交換位值），因為有六個格子一樣，最后需要除以。答案：42種）20. 有一排格子排成一排，已知共有8個格子?，F(xiàn)有三個不同顏色的球要放在其中，要求任意兩個球不能相鄰，問共有多少種擺放方案。（提示：為了方便理解說明，不妨將這三個不同顏色的球編號為1、2、3號。所有的擺放方案為，減去任意兩個球相鄰的擺放方案，共有六種情況（即12、21、13、31、23、32），此時需要注意三個球相鄰的情況，三個球相鄰的情況有123、312、21