電腦科學與數學密不可分。組合數學在資訊學競賽運用廣泛，特別大多數的搜尋類問題，動態規劃類問題（運籌學）、遞推計數類問題，都可以歸結到組合數學的應用問題。組合數學是以兩個計數原理為基礎的。
1)加法原理
【問題1】從甲地到乙地，可以乘火車，也可以乘汽車，還可以乘輪船．一天中，火車有4個班次，汽車有2個班次，輪船有3個班次．那麼一天中乘坐這些交通工具從甲地到乙地，共有多少種不同的走法？
【分析】因為一天中乘火車有4種走法，乘汽車有2種走法，乘輪船有3種走法，每種走法都可以完成由甲地到乙地這件事情．所以，一天中乘坐這些交通工具從甲地到乙地共有4+2+3=9 種不同的走法。解答樹如下:
【總結】將這型別的問題總結為乙個基本原理—— 加法原理：做一件事，完成它可以有幾類辦法，在第一類辦法中有m1種不同的方法，在第二類辦法中有m2種不同的方法，…，在第n類辦法中有mn種不同的方法．那麼，完成這件事共有n=m1+m2+…+mn種不同的方法。
解答樹如下：
2)、乘法原理
【問題2】由a村去b村的道路有3條，由b村去c村的道路有2條（見圖9－1），從a村經b村去c村，共有多少種不同的走法？
【分析】從a村到b村，有3種不同的走法，按這3種走法中的每一種走法到達b村後，再從b村到c村又各有2種不同的走法，因此，從a村經b村去c村共有3×2=6種不同的走法。解答樹如下：
【總結】將著型別的問題總結為乙個基本原理—— 乘法原理：做一件事，完成它需要分成n個步驟，做第一步有m1種不同的方法，做第二步有m2種不同的方法，…，做第n步有mn種不同的方法．那麼，完成這件事共有n＝m1×m2×…×mn種不同的方法．
解答樹如下：
3)加法原理和乘法原理的淺釋
它們的作用是：是用於計算完成一件事的所有不同的方法種數。
它們的區別是：乙個與分類有關，乙個與分步有關。
【問題1】找1～10這10個數中的所有合數。
【解答】第1類辦法是找含因數2的合數，共有4個；
第2類辦法是找含因數3的合數，共有2個；
第3類辦法是找含因數5的合數，共有1個，
所以，1～10中一共有n=4＋2＋1=7個合數。
【問題2】在前面的問題2中，步行從a村到b村的北路需要8時，中路需要4時，南路需要6時，b村到c村的北路需要5時，南路需要3時，要求步行從a村到c村的總時數不超過12時，共有多少種不同的走法？
【解答】 第1步從a村到b村有3種走法，
第2步從b村到c村有2種走法，
共有n=3×2=6種不同走法。
上面兩個例題的解答都是錯誤的：
問題1：1-10中的合數是4，6，8，9，10這五個，其中6既含有因數2，也含有因數3；10既含有因數2，也含有因數5，所以分類有問題。
問題2：從a村到c村總時數不超過12時的走法共有5種．題2中從a村走北路到b村後再到c村，只有南路這一種走法，所以分步有問題。
【總結】進行分類時，要求各類辦法彼此之間是相互排斥的，不論哪一類辦法中的哪一種方法，都能單獨完成這件事。只有滿足這個條件，才能直接用加法原理，否則不可以。
如果完成一件事需要分成幾個步驟，各步驟都不可缺少，需要依次完成所有步驟才能完成這件事，而各步要求相互獨立，即相對於前一步的每一種方法，下一步都有m種不同的方法，那麼計算完成這件事的方法數時，就可以直接應用乘法原理。
也就是說：類類互斥，步步獨立。
例1：書架上放有3本不同的數學書，5本不同的語文書，6本不同的英語書．
（1）若從這些書中任取一本，有多少種不同的取法？
（2）若從這些書中，取數學書、語文書、英語書各一本，有多少種不同的取法？
（3）若從這些書中取不同的科目的書兩本，有多少種不同的取法？
【分析】
(1)從書架上任取一本書，可以有3類辦法：
第1類辦法是從3本不同數學書中任取1本，有3種方法；
第2類辦法是從5本不同的語文書中任取1本，有5種方法；
第3類辦法是從6本不同的英語書中任取一本，有6種方法。
根據加法原理，得到的取法種數是：n＝m1＋m2＋m3＝3＋5＋6＝14。
(2)從書架上任取數學書、語文書、英語書各1本，需要分成三個步驟完成：
第1步取1本數學書，有3種方法；
第2步取1本語文書，有5種方法；
第3步取1本英語書，有6種方法．
根據乘法原理，得到不同的取法種數是n=m1×m2×m3=3×5×6=90．
(3)從書架上任取不同科目的書兩本，可以有3類辦法：
第1類辦法是數學書、語文書各取1本，需要分兩個步驟，有3×5種方法；
第2類辦法是數學書、英語書各取1本，需要分兩個步驟，有3×6種方法；
第3類辦法是語文書、英語書各取1本，有5×6種方法．
一共得到不同的取法種數是n=3×5＋3×6＋5×6=63。
例2 由數字0，1，2，3，4可以組成多少個三位整數（各位上的數字允許重複）？
【分析】要組成乙個三位數，需要分成三個步驟：
第1步確定百位上的數字，從1～4這4個數字中任選乙個數字，有4種選法；
第2步確定十位上的數字，由於數字允許重複，共有5種選法；
第3步確定個位上的數字，仍有5種選法．
根據乘法原理，得到可以組成的三位整數的個數是n=4×5×5=100。
例3 過河卒 p1293
如下圖a 點有乙個過河卒，需要走到目標 b 點。卒行走規則：可以向下、或向右。
同時在棋盤上的任一點有乙個對方的馬（如上圖的c點），該馬所在的點和所有跳躍一步可達的點稱為對方馬的控制點。例如上圖 c 點上的馬可以控制 9 個點。卒不能通過對方馬的控制點。
棋盤用座標表示，a 點（0，0）、b 點（n,m）(1<=n,m<=20)，同樣馬的位置座標是需要給出的（約定: c<>a，同時c<>b）。現在要求你計算出卒從 a 點能夠到達 b 點的路徑的條數。
【輸入】b點的座標（n,m）以及對方馬的座標(x,y)
【輸出】乙個整數（路徑的條數）。
【樣例】
【分析】
在不考慮有馬的棋盤中:
設函式f(x,y)=從出發點(0,0)走到(x,y)的路徑條數。則走到(x,y)的方法有兩類：
第1類是從上邊點(x-1,y)走下來，這類的方法數為：f(x-1,y)
第2類是從左邊點(x,y-1)走過來，這類的方法數為：f(x,y-1)
根據加法原理有，f(x,y)=f(x-1,y)+f(x,y-1)
邊界條件：f(0,0)=1;
如果有馬，則需要標記那些點被馬控制，所以需要設定乙個二維陣列horse[x][y]，表示棋盤，將馬控制點標記，在計算到標記點的時候，將氣方法數直接記為0。
程式，請自行完成。
◆分類時用加法原理，分步時用乘法原理。
◆分類時要求各類辦法彼此之間相互排斥；分步時要求各步是相互獨立的。
◆1．在所有的兩位數中，個位數字小於十位數字的共有多少個？
2．某學生填報高考志願，有m個不同的志願可供選擇，若只能按第
一、二、三志願依次填寫3個不同的志願，求該生填寫志願的方式的種數．
3．在所有的三位數中，有且只有兩個數字相同的三位數共有多少個？
4．某小組有10人，每人至少會英語和日語中的一門，其中8人會英語，5人會日語：
（1）從中任選乙個會外語的人，有多少種選法？
（2）從中選出會英語與會日語的各1人，有多少種不同的選法？
1. 排列
概念：從n個不同元素中，任取m(m≤n)個元素按照一定的順序排成一列，叫做從n個不同元素中取出m個元素的乙個排列。
排列數：從n個不同元素中取出m(m≤n)個元素的所有排列的個數，叫做從n個不同元素中取出m個元素的排列數，用符號表示。
計算公式：＝n(n－1)(n－2)……(n－m＋1)＝
以前排列會記為p。下面一些例題是p的表明也是排列。
2. 組合
概念：從n個不同元素中，任取m(m≤n)個元素並成一組，叫做從n個不同元素中取出m個元素的乙個組合。
組合數：從n個不同元素中取出m(m≤n)個元素的所有組合的個數，叫做從n個不同元素中取出m個元素的組合數，用符號表示。
計算公式：＝＝＝
組合恒等式：①②
③④⑤3. 高中數學知識補充：
n個人圍著一張圓桌坐在一起，共有(n－1)!種坐法。
把r個相同的球放到n個不同顏色的盒子中去，共有種方法。
從n個排成一排的數中取m個數，且數字之間互不相鄰，共有種取法。
catalan數列，其數列為1，2，5，14，42，132，429……，通項公式為hn＝。
解排列組合問題，首先要弄清一件事是「分類」還是「分步」完成，對於元素之間的關係，還要考慮「是有序」的還是「無序的」，也就是會正確使用分類計數原理和分步計數原理、排列定義和組合定義，其次，對一些複雜的帶有附加條件的問題，需掌握以下幾種常用的解題方法：
特殊優先法對於存在特殊元素或者特殊位置的排列組合問題，我們可以從這些特殊的東西入手，先解決特殊元素或特殊位置，再去解決其它元素或位置，這種解法叫做特殊優先法.例如：用0、1、2、3、4這5個數字，組成沒有重複數字的三位數，其中偶數共有________個.
（答案：30個）
科學分類法對於較複雜的排列組合問題，由於情況繁多，因此要對各種不同情況，進行科學分類，以便有條不紊地進行解答，避免重複或遺漏現象發生例如：從6臺原裝計算機和5臺組裝計算機中任取5臺，其中至少有原裝與組裝計算機各兩台，則不同的選取法有_______種.（答案：
350）
插空法解決一些不相鄰問題時，可以先排一些元素然後插入其餘元素，使問題得以解決例如：7人站成一行，如果甲乙兩人不相鄰，則不同排法種數是______.(答案:3600)
**法相鄰元素的排列，可以採用「整體到區域性」的排法，即將相鄰的元素當成「乙個」元素進行排列，然後再區域性排列例如：6名同學坐成一排，其中甲、乙必須坐在一起的不同坐法是________種.（答案：
240）
組合數學考試要點
考點1 排列，圓排列，組合 1 21個人沿著圓桌坐下，一張桌子坐10人，一張坐11人，試問有多少種坐法。解 首先從21個人中間選10個人坐第一張桌子，然後對第一張桌子上的10人進行圓排列，最後對第二張桌子上的11人進行圓排列，故一共有的坐法種數為 考點2 容斥原理 2 有100人參加考試，考題有甲乙...
組合數學四色證明
四色問題的證明 如果你仔細留心一張世界地圖，你會發現用一種顏色對乙個國家著色，那麼一共只需要四種顏色就能保證每兩個相鄰的國家的顏色不同。這樣的著色效果能使每乙個國家都能清楚地顯示出來。但要證明這個結論確是乙個著名的世界難題，最終借助計算機才得以解決，最近人們才發現了乙個更簡單的證明。根據尤拉創立的 ...
學習組合數學心得體會
學習數學我感覺是一件很有味道的事情，令人思維變得敏捷活躍。學習組合數學更是令人思維更嚴謹更具邏輯性。組合數學不僅在基礎數學研究中具有極其重要的地位，在其他的學科中也有重要的應用，如在電腦科學 編碼和密碼學 物理 化學 生物等學科中均有重要應用。我們組合數學這一門課程在吳克儉老師的指導下，經過半學期的...