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

1、排列與組合基礎(chǔ)知識有關(guān)排列與組合的基本理論和公式:加法原理：做一件事，完成它可以有n類辦法，在第一類辦法中有m1種不冋的方法，在第二類中辦法中有m2種不冋的方法，在第n類辦法中有mn種不冋方法。那么完成這件事共有N = mi+ m2+-+ mn種不同的方法，這一原理叫做加法原理。乘法原理：做一件事，完成它需要分成n個(gè)步驟，做第一步有 mi種不同的方法，做第二步有 m2種不同的方法， ，做第 n步有mn種不同的方法，那么完成這件事共有N = mi Xm2X >mn種不同的方法，這一原理叫做乘法原理。公式：階乘公式 n! = n (n -1) (n -213 2 1，規(guī)定 0!= 1;全排列

2、公式Pnn = n!選排列公式仁-嘰泗“占、PJcWn丨圓排列：n個(gè)不同元素不分首位圍成一個(gè)圓圈達(dá)到圓排列，則排列數(shù)為：(n -1)!n組合數(shù)公式cn"Pmn(n-1)( n-2川|( n-m 1) n!Pmm!m!( n-m)!規(guī)定C0 =1n -m nmm mJ012n n、Cn 1 = G ' Cn 、Cn ' Cn ' CnCn = 2 )提示：(1)全排列問題和選排列問題，都可根據(jù)乘法原理推導(dǎo)出來。(2)書寫方式： 戌記為P (n,r); C；記為C (n,r)。加法原理例題：圖1中從A點(diǎn)走到B點(diǎn)共有多少種方法？(答案：4+ 2+ 3 = 9)乘法原

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

4、數(shù)字；再確定十位數(shù)，可以為0、1、2、3任何一個(gè)；最后確定個(gè)位數(shù)，可以為0、1、2、3任何一個(gè)。根據(jù)乘法原理，共有3X 4X 4 = 48個(gè)。（2）同理，先確定百位數(shù)、再確定十位數(shù)、最后確定個(gè)位數(shù)，根據(jù)乘法原理，共有3X 3X 2個(gè)）2. 國際會議洽談貿(mào)易，有 5家英國公司，6家日本公司，8家中國公司，彼此都希望與異國的每個(gè)公 司單獨(dú)洽談一次，問需要安排多少個(gè)會談場次？（提示：共分為中英、中日、英日會談三類，對于中英會談，先選定中方公司有8種選法，在選定英方公司有 5種選法，故根據(jù)乘法原理有 5X &同理中日8X6;英日5X 6;總的會談：118）3. 有編號為1、2、3、4、5的五本

5、書需要擺放在書架上，問有多少種不同的擺放方案數(shù)。（提示：此題為全排列，故擺放方案總數(shù)為P（5,5）=5!=120種。也可以按乘法原理思考，即擺放第一本書有5種選擇，擺放第二本數(shù)有 4種選擇，最后結(jié)果為 5X 4 X 3 X 2X 1即5!）4. 有編號為1、2、3、4、5的五本書需要任選 3本書擺放在書架上，問有多少種不同方案。（提示：可根據(jù)選排列公式計(jì)算，總數(shù)為P（5,3）。也可以根據(jù)乘法原理計(jì)算，答案為5X 4X 3= 60）5. 有編號為1、2、3、4、5的五本書需要任選 3本書，問有多少種方法。5 4 3（提示：此題為組合問題，答案為c3二5= 10）53!6. 五種不同顏色的珠子串成

6、一圈項(xiàng)鏈，問有多少種不同的方法。（提示：此題屬于圓排列問題，答案為（5- 1）!= 24）7. 把兩個(gè)紅色球、兩個(gè)藍(lán)色球、三個(gè)黃色球擺放在球架上，問有多少種方案。（提示：此題為排列問題。擺放方案總數(shù)為（2+ 2+ 3 ）!種，但是兩個(gè)紅球一樣，所以要除以2!,同理兩個(gè)藍(lán)球，除以 2!,三個(gè)黃球，除以 3!,即擺放方案總數(shù)為 （2 +2*3）! =210 ）2聲2嚴(yán)3!8. 有男女各5人，其中3對是夫妻，他們坐成一排，若每對夫妻必須相鄰而坐，問有多少種方法？（提示：因?yàn)?3對夫妻必須相鄰而坐，因此可以將每對夫妻看為一個(gè)整體進(jìn)行排列，這樣排列總數(shù)為（7!）種方法，又因?yàn)槊繉Ψ蚱蘅梢钥梢宰笥艺{(diào)換位置

7、，因此總的方案為（7! X 2X 2X 2）9. （ 1）把3個(gè)相同的球放到4個(gè)不同顏色的盒子中去，問有多少種方法？（2）把4個(gè)相同的球放到3個(gè)不同顏色的盒子中去，問有多少種方法？ （3 ）推廣開來，把 R個(gè)相同的球放到 N個(gè)不同顏色的盒子中去，問有多少種方法？ （提示：這是允許重復(fù)組合的典型模型。）（解答（1） : 3個(gè)球放入4個(gè)不同顏色盒子的分法共有3、0、0、0;1、2、0、0;1、1、1、0三類；對于第一類3、0、0、0的方法，共有P4種方法，但是有3個(gè)0是一樣的，所以應(yīng)該除以P3 ,即第一類分法的方法數(shù)為 p4/P33種，同理，第二種分法的方法數(shù)為p4/p2，第三種分法的方法數(shù)為F/

8、P3，所以總共的方法數(shù)為（ P4/P3 + P4/P2 + P：/戌）種。解答（2）自行求解。解答（3）:這一類問題，我們稱為重復(fù)組合問題，其求解公式為C（n+r-1,r）。請記住該公式即可。）排列組合練習(xí)習(xí)題：1. 有5本日文書、7本英文書、10本中文書。問（1 ）從中任取2本書有多少種方案？ （2）從中取2本相同文字的書有多少種方案？ （3）從中取2本不同文字的書有多少種方案？（提示：此題為組合問題。答案分別為：C；.710、C； C； C0、C：7.10-2； - C； - C10）2. 把八個(gè)“車”放在 8X 8的國際象棋棋盤上，如果它們兩兩均不能互吃（即在任何一行、任何一列都只有一個(gè)

9、“車”）,那么稱八個(gè)“車”處于一個(gè)安全狀態(tài)。問共有多少種不同的安全狀態(tài)？（提示：乘法原理。先在第一行放置一個(gè)“車” ，有8種選法，再在第二行放置一個(gè)“車”，還有7 種選法，同理，總共有 8 X 7 X-X 2 X 1, 即卩8!種不同的安全狀態(tài)。）3. 從1300之間任取3個(gè)不同的數(shù)，使得這 3個(gè)數(shù)的和正好被3除盡，問有多少種方案？（提示：1300之間的數(shù)被3除的余數(shù)共有三類，分別是余數(shù)為0、余數(shù)為1、余數(shù)為2,每類各100個(gè)數(shù)。任取3個(gè)數(shù)且這3個(gè)數(shù)相加的和正好被 3除盡的情況只能是以下四種情況之一：余數(shù) 為0+ 1 + 2; 0+ 0+ 0; 1 + 1+ 1; 2 + 2+ 2。再根據(jù)乘法

10、原理和加法原理即可求解。答案為：100X 100X 100+ 100X 99X 98+ 100X 99X 98+ 100X 99X 98）4. 5對夫婦圍繞圓桌坐下吃飯，共有多少種方案？如果要求夫婦必須坐在一起，又有多少種方案？（提示：此題為圓排列問題。第一問的答案為（10- 1）!。對于第二問，因?yàn)榉驄D必須坐在一起，因此可以將每對夫婦看為一個(gè)整體先行進(jìn)行圓排列，排列方案為（5 1） !,又因?yàn)槊繉Ψ驄D可以左右交換位置，因此總的排列方案為（5 1）! X 2X 2 X 2 X 2X 2。）5. N個(gè)男同學(xué)和N個(gè)女同學(xué)圍繞圓桌坐下，要求男女必須交替就座，問共有多少種就座方法？（提示：先經(jīng)這 N個(gè)

11、男同學(xué)進(jìn)行圓排列，方案為（ N 1）!,然后每個(gè)女同學(xué)依次坐入到兩個(gè)男同 學(xué)中間，第一個(gè)女同學(xué)有 N個(gè)位置可以選，第二個(gè)女同學(xué)有N- 1個(gè)位置可以選，依此類推。根據(jù)乘法原理，所有的就座方案為（N 1） ! X N !）6. 8人站成一排排隊(duì)，如果其中的甲和乙兩人要求一定站在一起，問有多少種排隊(duì)方法？如果甲和乙兩人要求一定不站在一起，又有多少種方法？（提示：第一問中，甲和乙一定站在一起，因此可以先將此二人看為一個(gè)整體，則排隊(duì)方法為7!,又因?yàn)榧缀鸵铱梢越粨Q位置，因此總的方案為7!X 2。對于第二問，則用8個(gè)人的總排隊(duì)方案數(shù)減去甲和乙站在一起的方案數(shù)即可，答案為8! 7! X 2。）7. 有N個(gè)男

12、同學(xué)和M個(gè)女同學(xué)站成一排，其中這M個(gè)女同學(xué)要求站在一起，問共有多少種排隊(duì)方法？（提示：排列問題+乘法原理。分兩步：第一，先將這M個(gè)女同學(xué)看成一個(gè)整體排列；第二，再將這M個(gè)女同學(xué)再排列。然后根據(jù)乘法原理即可求得。答案為：（N + 1）! X M !）8. 一個(gè)長度為N + M個(gè)字符的01字符串，問其中有 N個(gè)1的字符串有多少個(gè)？（提示：組合問題?，F(xiàn)有 N + M個(gè)字符，如果把1看作取字符，把0看作不取字符，那么其中有 N 個(gè)1的字符串即相當(dāng)于從 N + M個(gè)字符中，任取 N個(gè)字符的組合。答案為：C （ N + M , N）9. 一個(gè)N*M （N表示行，M表示列）的網(wǎng)格，從左上角（1, 1）點(diǎn)開始

13、走到右下角（N, M）點(diǎn)， 每次只能向右或者向下走，問有多少種不同的路徑。(方法一：從(1 , 1)點(diǎn)走到(N , M )點(diǎn)，無論如何走一共都要 走(N 1) + ( M 1)步，其中N 1步向右走，M 1步向下 走，因?yàn)橹挥袃煞N走法，不妨用二進(jìn)制表示走路方式，1表示向右走，0表示向下走。則可用一個(gè)長度為( N + M 2)的二進(jìn)制 串來表示走路方法，其中如果出現(xiàn)了N 1個(gè)1，則表示找到了一種路徑。從而把題目轉(zhuǎn)化為求長度為N+ M 2的2進(jìn)制串中有N 1個(gè)1的個(gè)數(shù)，即求組合數(shù)學(xué)公式 C ( N + M 2, N 1)的值。方法二：對本題稍加分析就能發(fā)現(xiàn)，要到達(dá)棋盤上的某個(gè)點(diǎn)，只能從該點(diǎn)的上邊過

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

15、(a,b)恒滿足a<b的關(guān)系(a為行坐標(biāo)，b為列坐標(biāo))，問有多少條路徑？(測試數(shù)據(jù)：N = 4，M = 5; 答案：)11. 在上上題中，如果其中有 X個(gè)點(diǎn)設(shè)置有障礙而無法通過，問有多少條路徑？其中 X的值以及這X 個(gè)點(diǎn)的坐標(biāo)由鍵盤輸入。(測試數(shù)據(jù)：N = 5，M = 4，X = 2,這2個(gè)障礙點(diǎn)坐標(biāo)為(2,3)和(4,2);答案：)12. 一個(gè)由N個(gè)0和N個(gè)1組成的01字符串，要求從左往右，1的個(gè)數(shù)始終不少于 0的個(gè)數(shù)的字符串 共有多少個(gè)？如 N = 1時(shí)，只有字符串 10;如N = 2時(shí)，有1100、1010兩個(gè)字符串；如 N = 3時(shí)， 有 111000、110100、110010

16、、101100、101010 五個(gè)字符串。(提示：該字符串的長度為2N，其中規(guī)定有N個(gè)1,即相當(dāng)于從2N個(gè)字符中取出N個(gè)字符，方案數(shù)為C (2N , N)。該題還規(guī)定從左往右，1的個(gè)數(shù)始終不少于 0的個(gè)數(shù)，那么在 C (2N , N ) 個(gè)方案中，必定有一些排列方案不符合要求，那么是哪些不符合要求呢？我們看N = 2的例子，此時(shí)所有的排列方案有 0011、0101、0110、1001、1010、1100六種，其中只有 1010和1100兩 種方案符合要求，為什么呢？實(shí)際上，在N = 2時(shí)，即有N個(gè)1,這樣，我們將任意一個(gè) 0填充到這N個(gè)1中的方案數(shù)有N + 1種，如下圖有、三個(gè)格子可以填充0,

17、但是要保證所有的0總在1之后，因此也就只有的位置符合要求(如 1100和1010我們都認(rèn)為是所有的 0在1 的右邊，而1001則有一個(gè)0不在1的右邊)，即只有C (2N , N )的1/( N + 1)種方案符合要 求。所以答案為：C (2N , N)/( N + 1)。該數(shù)列稱為 Catalan數(shù)列，其數(shù)列為1、2、5、14、42。對于此問題，有許多變形應(yīng)用，請熟記該公式。)11(舉一反三：一個(gè)由 N個(gè)0和N個(gè)1組成的01字符串，要求從左往右，1的個(gè)數(shù)始終不多于 0的 個(gè)數(shù)的字符串共有多少個(gè)？同理：相當(dāng)于1的位置只能排在所有 0的位置之后，因此個(gè)數(shù)同樣為：C (2N , N) / ( N +

18、 1)。)13. 用N個(gè)A和N個(gè)B排列成一個(gè)字符串，要求從左往右的任意一位，A的個(gè)數(shù)不能少于 B的個(gè)數(shù)，問有多少種排列方案。14. 有2N個(gè)顧客排隊(duì)購買一種產(chǎn)品，該產(chǎn)品的售價(jià)為5元，其中N個(gè)顧客手持5元的貨幣，其余 N個(gè)顧客手持10元貨幣。由于售貨員手中沒有零錢找零，因此售貨員必須將這2N個(gè)顧客按照一定的次序排好隊(duì)，問有多少種排隊(duì)方式可以依次順利發(fā)售貨品，而不出現(xiàn)無法找零的情況。15. 學(xué)校某年級參加數(shù)學(xué)、物理、化學(xué)的培訓(xùn)，人數(shù)分別是150、120、100人。同時(shí)培訓(xùn)數(shù)學(xué)、物理兩門課的學(xué)生有21人；同時(shí)培訓(xùn)數(shù)學(xué)、化學(xué)的有16人；同時(shí)培訓(xùn)物理、化學(xué)的有8人；三科都培訓(xùn)的有5人。問該年級共有多少人

19、？(提示：對于此類問題，我們可以用一個(gè)圖示法表示，從圖中我們看出，總?cè)藬?shù)即為： a + b + c a n b b n c c n a + a n b n c= 150+ 120+ 100 21 16 8 + 5= 330)排列組合考試題:16. 在15個(gè)同學(xué)中準(zhǔn)備選出 4名同學(xué)參加國際信息學(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六個(gè)字母進(jìn)行排列，其字符排

20、列中不出現(xiàn)“ACE”或“ DF”字串的排列方案有多少種？(提示：六個(gè)字母的總排列方案為 P (6, 6),又因?yàn)橐笈帕械淖址胁坏贸霈F(xiàn)“ACE”或“DF”字串，因此我們可以將“ ACE”看作一個(gè)整體，排列方案為 P (4, 4),將“DF”看作一個(gè)整體， 排列方案為P(5,5),“ ACE ”和“ DF ”同時(shí)出現(xiàn)的方案為P( 3,3),所以答案為：P(6,6)P (4, 4) P ( 5, 5)+ P (3, 3);即 6! ( 4! + 5!) + 3!。)18. 棧的計(jì)數(shù)。編號分別為1N (1<=N<=18 )的N輛列車順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的站臺(先進(jìn)后出)，試問這N輛列

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