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

1、信息學(xué)奧林匹克競賽輔導(dǎo)——排列與組合基礎(chǔ)知識第1頁排列與組合基礎(chǔ)知識有關(guān)排列與組合的基本理論和公式：加法原理：做一件事，完成它可以有n類辦法，在第一類辦法中有m1種不同的方法，在第二類中辦法中有m2種不同的方法，……，在第n類辦法中有mn種不同方法。那么完成這件事共有N＝m1＋m2＋…＋mn種不同的方法，這一原理叫做加法原理。乘法原理：做一件事，完成它需要分成n個(gè)步驟，做第一步有m1種不同的方法，做第二步有m2種不同的方法，……，做第n

2、步有mn種不同的方法，那么完成這件事共有N＝m1m2…mn種不同的方法，這一原理叫做乘法原理。公式：階乘公式，規(guī)定0！＝1；!(1)(2)321nnnn????????全排列公式!nnPn?選排列公式、!(1)(2)(1)()!mnnPnnnnmnm????????mmmnnmPCP?A圓排列：n個(gè)不同元素不分首位圍成一個(gè)圓圈達(dá)到圓排列，則排列數(shù)為：!(1)!nnn??組合數(shù)公式、規(guī)定(1)(2)(1)!!!()!mmnnmmPnnnn

3、mnCPmmnm?????????01nC?、、）mnmnnCC??11mmmnnnCCC????0122nnnnnnCCCC??????提示：（1）全排列問題和選排列問題，都可根據(jù)乘法原理推導(dǎo)出來。（2）書寫方式：記為P（nr）；記為C（nr）。rnPrnC加法原理例題：圖1中從A點(diǎn)走到B點(diǎn)共有多少種方法？（答案：4＋2＋3＝9）乘法原理例題：圖2中從A點(diǎn)走到B點(diǎn)共有多少種方法？（答案：46＝24）加法原理與乘法原理綜合：圖3、圖4中

4、從A走到B共有多少種方法？（答案：28、42）AB圖1AB圖2AB圖3AB圖4信息學(xué)奧林匹克競賽輔導(dǎo)——排列與組合基礎(chǔ)知識第3頁法的方法數(shù)為，所以總共的方法數(shù)為（＋＋）種。4343PP4343PP4242PP4343PP解答（2）自行求解。解答（3）：這一類問題，我們稱為重復(fù)組合問題，其求解公式為C（nr1r）。請記住該公式即請記住該公式即可。）排列組合練習(xí)習(xí)題：1.有5本日文書、7本英文書、10本中文書。問（1）從中任取2本書有多少種

5、方案？（2）從中取2本相同文字的書有多少種方案？（3）從中取2本不同文字的書有多少種方案？（提示：此題為組合問題。答案分別為：、、）25710C??2225710CCC??222257105710()CCCC?????2.把八個(gè)“車”放在88的國際象棋棋盤上，如果它們兩兩均不能互吃（即在任何一行、任何一列都只有一個(gè)“車”），那么稱八個(gè)“車”處于一個(gè)安全狀態(tài)。問共有多少種不同的安全狀態(tài)？（提示：乘法原理。先在第一行放置一個(gè)“車”，有8種選

6、法，再在第二行放置一個(gè)“車”，還有7種選法，同理……，總共有87…21，即8！種不同的安全狀態(tài)。）3.從1～300之間任取3個(gè)不同的數(shù)，使得這3個(gè)數(shù)的和正好被3除盡，問有多少種方案？（提示：1～300之間的數(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ù)乘法原理和加法原理即可求解

7、。答案為：100100100＋1009998＋1009998＋1009998）4.5對夫婦圍繞圓桌坐下吃飯，共有多少種方案？如果要求夫婦必須坐在一起，又有多少種方案？（提示：此題為圓排列問題。第一問的答案為（10－1）！。對于第二問，因?yàn)榉驄D必須坐在一起，因此可以將每對夫婦看為一個(gè)整體先行進(jìn)行圓排列，排列方案為（5－1）！，又因?yàn)槊繉Ψ驄D可以左右交換位置，因此總的排列方案為（5－1）！22222。）5.N個(gè)男同學(xué)和N個(gè)女同學(xué)圍繞圓桌坐下

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

9、先將此二人看為一個(gè)整體，則排隊(duì)方法為7！，又因?yàn)榧缀鸵铱梢越粨Q位置，因此總的方案為7！2。對于第二問，則用8個(gè)人的總排隊(duì)方案數(shù)減去甲和乙站在一起的方案數(shù)即可，答案為8?。?！2。）7.有N個(gè)男同學(xué)和M個(gè)女同學(xué)站成一排，其中這M個(gè)女同學(xué)要求站在一起，問共有多少種排隊(duì)方法？（提示：排列問題＋乘法原理。分兩步：第一，先將這M個(gè)女同學(xué)看成一個(gè)整體排列；第二，再將這M個(gè)女同學(xué)再排列。然后根據(jù)乘法原理即可求得。答案為：（N＋1）！M?。?.一個(gè)長度