排列與組合基礎知識
有關排列與組合的基本理論和公式：
加法原理：做一件事，完成它可以有n類辦法，在第一類辦法中有m1種不同的方法，在第二類中辦法中有m2種不同的方法，……，在第n類辦法中有mn種不同方法。那麼完成這件事共有n＝m1＋m2＋…＋mn種不同的方法，這一原理叫做加法原理。
乘法原理：做一件事，完成它需要分成n個步驟，做第一步有m1種不同的方法，做第二步有m2種不同的方法，……，做第n步有mn種不同的方法，那麼完成這件事共有n＝m1×m2×…×mn種不同的方法，這一原理叫做乘法原理。
公式：階乘公式，規定0！＝1；
全排列公式
選排列公式、
圓排列：n個不同元素不分首位圍成乙個圓圈達到圓排列，則排列數為：
組合數公式、規定
、、）提示：（1）全排列問題和選排列問題，都可根據乘法原理推導出來。
2）書寫方式：記為p（n,r）；記為c（n,r）。
加法原理例題：圖1中從a點走到b點共有多少種方法？（答案：4＋2＋3＝9）
乘法原理例題：圖2中從a點走到b點共有多少種方法？（答案：4×6＝24）
加法原理與乘法原理綜合：圖3、圖4中從a走到b共有多少種方法？（答案：28、42）
注意：在資訊學奧賽中，有許多只需計數而不需具體方案的問題，都可以通過思維轉換或方法轉換，最後變為兩類問題：一類是轉變為排列組合問題，另一類是轉變為遞推公式問題。
因此對於加法原理、乘法原理、排列、組合等知識，需要非常熟練，以達到簡化問題的目的。
加法原理、乘法原理、排列、組合例題：
1. （1）用數字0、1、2、3能組成多少個三位數？（2）要求數字不能重複，又能組成多少個三位數？
（提示：（1）先確定百位數，只能是1、2、3之間的數字；再確定十位數，可以為0、1、2、3任何乙個；最後確定個位數，可以為0、1、2、3任何乙個。根據乘法原理，共有3×4×4＝48個。
（2）同理，先確定百位數、再確定十位數、最後確定個位數，根據乘法原理，共有3×3×2個）
2. 國際會議洽談**，有5家英國公司，6家日本公司，8家中國公司，彼此都希望與異國的每個公司單獨洽談一次，問需要安排多少個會談場次？
（提示：共分為中英、中日、英日會談三類，對於中英會談，先選定中方公司有8種選法，在選定英方公司有5種選法，故根據乘法原理有5×8：同理中日8×6；英日5×6；總的會談：118）
3. 有編號為1、2、3、4、5的五本書需要擺放在書架上，問有多少種不同的擺放方案數。
（提示：此題為全排列，故擺放方案總數為p(5,5)=5!=120種。
也可以按乘法原理思考，即擺放第一本書有5種選擇，擺放第二本數有4種選擇，……，最後結果為5×4×3×2×1即5！）
4. 有編號為1、2、3、4、5的五本書需要任選3本書擺放在書架上，問有多少種不同方案。
（提示：可根據選排列公式計算，總數為p(5,3)。也可以根據乘法原理計算，答案為5×4×3＝60）
5. 有編號為1、2、3、4、5的五本書需要任選3本書，問有多少種方法。
（提示：此題為組合問題，答案為＝10）
6. 五種不同顏色的珠子串成一圈項鍊，問有多少種不同的方法。
（提示：此題屬於圓排列問題，答案為（5－1）！＝24）
7. 把兩個紅色球、兩個藍色球、三個黃色球擺放在球架上，問有多少種方案。
（提示：此題為排列問題。擺放方案總數為（2＋2＋3）！種，但是兩個紅球一樣，所以要除以2！，同理兩個藍球，除以2！，三個黃球，除以3！，即擺放方案總數為）
8. 有男女各5人，其中3對是夫妻，他們坐成一排，若每對夫妻必須相鄰而坐，問有多少種方法？
（提示：因為3對夫妻必須相鄰而坐，因此可以將每對夫妻看為乙個整體進行排列，這樣排列總數為（7!）種方法，又因為每對夫妻可以可以左右調換位置，因此總的方案為（7！×2×2×2））
9. （1）把3個相同的球放到4個不同顏色的盒子中去，問有多少種方法？
（2）把4個相同的球放到3個不同顏色的盒子中去，問有多少種方法？
（3）推廣開來，把r個相同的球放到n個不同顏色的盒子中去，問有多少種方法？
（提示：這是允許重複組合的典型模型。）
（解答（1）：3個球放入4個不同顏色盒子的分法共有3、0、0、0；1、2、0、0；1、1、1、0三類；對於第一類3、0、0、0的方法，共有種方法，但是有3個0是一樣的，所以應該除以，即第一類分法的方法數為種，同理，第二種分法的方法數為，第三種分法的方法數為，所以總共的方法數為（＋＋）種。
解答（2）自行求解。
解答（3）：這一類問題，我們稱為重複組合問題，其求解公式為c（n+r-1,r）。請記住該公式即可。）
排列組合練習習題：
1. 有5本日文書、7本英文書、10本中文書。問（1）從中任取2本書有多少種方案？（2）從中取2本相同文字的書有多少種方案？（3）從中取2本不同文字的書有多少種方案？
（提示：此題為組合問題。答案分別為：、、）
2. 把八個「車」放在8×8的西洋棋棋盤上，如果它們兩兩均不能互吃（即在任何一行、任何一列都只有乙個「車」），那麼稱八個「車」處於乙個安全狀態。問共有多少種不同的安全狀態？
（提示：乘法原理。先在第一行放置乙個「車」，有8種選法，再在第二行放置乙個「車」，還有7種選法，同理……，總共有8×7×…×2×1，即8！種不同的安全狀態。）
3. 從1～300之間任取3個不同的數，使得這3個數的和正好被3除盡，問有多少種方案？
（提示：1～300之間的數被3除的餘數共有三類，分別是餘數為0、餘數為1、餘數為2，每類各100個數。任取3個數且這3個數相加的和正好被3除盡的情況只能是以下四種情況之一：
餘數為0＋1＋2；0＋0＋0；1＋1＋1；2＋2＋2。再根據乘法原理和加法原理即可求解。
答案為：100×100×100＋100×99×98＋100×99×98＋100×99×98）
4. 5對夫婦圍繞圓桌坐下吃飯，共有多少種方案？如果要求夫婦必須坐在一起，又有多少種方案？
（提示：此題為圓排列問題。第一問的答案為（10－1）！。
對於第二問，因為夫婦必須坐在一起，因此可以將每對夫婦看為乙個整體先行進行圓排列，排列方案為（5－1）！，又因為每對夫婦可以左右交換位置，因此總的排列方案為（5－1）！×2×2×2×2×2。
）5. n個男同學和n個女同學圍繞圓桌坐下，要求男女必須交替就座，問共有多少種就座方法？
（提示：先經這n個男同學進行圓排列，方案為（n－1）！，然後每個女同學依次坐入到兩個男同學中間，第乙個女同學有n個位置可以選，第二個女同學有n－1個位置可以選，依此類推。
根據乘法原理，所有的就座方案為（n－1）！×n！）
6. 8人站成一排排隊，如果其中的甲和乙兩人要求一定站在一起，問有多少種排隊方法？如果甲和乙兩人要求一定不站在一起，又有多少種方法？
（提示：第一問中，甲和乙一定站在一起，因此可以先將此二人看為乙個整體，則排隊方法為7！，又因為甲和乙可以交換位置，因此總的方案為7！
×2。對於第二問，則用8個人的總排隊方案數減去甲和乙站在一起的方案數即可，答案為8！－7！
×2。）
7. 有n個男同學和m個女同學站成一排，其中這m個女同學要求站在一起，問共有多少種排隊方法？
（提示：排列問題＋乘法原理。分兩步：
第一，先將這m個女同學看成乙個整體排列；第二，再將這m個女同學再排列。然後根據乘法原理即可求得。答案為：
（n＋1）！×m！）
8. 乙個長度為n＋m個字元的01字串，問其中有n個1的字串有多少個？
（提示：組合問題。現有n＋m個字元，如果把1看作取字元，把0看作不取字元，那麼其中有n個1的字串即相當於從n＋m個字元中，任取n個字元的組合。答案為：c（n＋m，n））
9. 乙個n*m（n表示行，m表示列）的網格，從左上角（1，1）點開始走到右下角（n，m）點，每次只能向右或者向下走，問有多少種不同的路徑。
（方法一：從（1，1）點走到（n，m）點，無論如何走一共都要走（n－1）＋（m－1）步，其中n－1步向右走，m－1步向下走，因為只有兩種走法，不妨用二進位制表示走路方式，1表示向右走，0表示向下走。則可用乙個長度為（n＋m－2）的二進位制串來表示走路方法，其中如果出現了n－1個1，則表示找到了一種路徑。
從而把題目轉化為求長度為n＋m－2的2進製串中有n－1個1的個數，即求組合數學公式c（n＋m－2，n－1）的值。
方法二：對本題稍加分析就能發現，要到達棋盤上的某個點，只能從該點的上邊過來，或者從該點的左邊過來，根據加法原理，要到達該點的路徑數目，就等於到達該點上點的路徑與該點左點的路徑數目之和，因此我們可以按照逐行遞推的方法求出從起點到終點的路徑數目。初始化，左上角第乙個元素值為1，其它點的值為上點與左點的和。
）對於如右圖的網格，用方法一的答案為c（4＋3，3）＝35；
用方法二逐行遞推的方法得到網格上的數字，最後答案也為35。
比較兩種方法，當資料較小時，採用公式一比較直接，但如果資料較大時，公式一的乘法運算量較大，這時可考慮用方法二逐行遞推求得答案。
10. 在上題中，若規定n（測試資料：n＝4，m＝5； 答案：）
11. 在上上題中，如果其中有x個點設定有障礙而無法通過，問有多少條路徑？其中x的值以及這x個點的座標由鍵盤輸入。
（測試資料：n＝5，m＝4，x＝2，這2個障礙點座標為（2,3）和（4,2答案：）
12. 乙個由n個0和n個1組成的01字串，要求從左往右，1的個數始終不少於0的個數的字串共有多少個？如n＝1時，只有字串10；如n＝2時，有1100、1010兩個字串；如n＝3時，有111000、110100、110010、101100、101010五個字串。
（提示：該字串的長度為2n，其中規定有n個1，即相當於從2n個字元中取出n個字元，方案數為c（2n，n）。該題還規定從左往右，1的個數始終不少於0的個數，那麼在c（2n，n）個方案中，必定有一些排列方案不符合要求，那麼是哪些不符合要求呢？
我們看n＝2的例子，此時所有的排列方案有0011、0101、0110、1001、1010、1100六種，其中只有1010和1100兩種方案符合要求，為什麼呢？實際上，在n＝2時，即有n個1，這樣，我們將任意乙個0填充到這n個1中的方案數有n＋1種，如下圖有、、三個格仔可以填充0，但是要保證所有的0總在1之後，因此也就只有的位置符合要求（如1100和1010我們都認為是所有的0在1的右邊，而1001則有乙個0不在1的右邊），即只有c（2n，n）的1／（n＋1）種方案符合要求。所以答案為：
c（2n，n）／（n＋1））。該數列稱為catalan數列，其數列為1、2、5、14、42……。對於此問題，有許多變形應用，請熟記該公式。）
資訊學奧賽選拔賽題目
對於乙個四位數a來說，它的前兩位我們可以這樣來表示a div 100,例如a 3456，a的前兩位是34與a div 100 結果相同，那麼a的後兩位可以怎麼表示 這樣我們想表示整數a是偶數可以這樣表示 a mod 2 0,那麼我們想表示整數a能被整數b整除應該如何表示已知整數a，那麼a的十位數如何...
資訊學奧賽初賽程序填空
1.下列程式計算1000以內能被3整除的自然數之和，請完成程式。include void main cout 2.下面的函式fun未使用中間變數實現對兩個數的交換，請完成下列函式的定義。void fun int x,int y 3.下面的函式bubble 是對整數陣列a按公升序排序的冒泡演算法，其中...
資訊學奧賽pascal檔案輸入輸出精要
begin assign input,in reset input assign output,out rewrite output 程式的主體部分 close input close output end.ex 從檔案中讀入兩個加數，把它們的和寫入輸出檔案中。program mm var a,b,...