組合數(shù)學(xué)是一個(gè)既古老又年輕的數(shù)學(xué)分支。說它古老,因?yàn)樗芯康膯栴}有的可追溯到很久很久以前。然而,它形成一個(gè)新的分支還是最近若干年的事,是受到電子計(jì)算機(jī)蓬勃發(fā)展影響的結(jié)果。
本節(jié)中的排列與組合、容斥原理、抽屜原理都是組合數(shù)學(xué)的內(nèi)容。
組合數(shù)學(xué)研究的主要內(nèi)容是計(jì)數(shù)和枚舉，即計(jì)算具有某種特性的對(duì)象有多少,并進(jìn)而把它完全列舉出來�！坝�(jì)數(shù)”在許多方面有其重大作用,比如本節(jié)中的概率部分，就是計(jì)數(shù)的應(yīng)用——要計(jì)算發(fā)生具有某種性質(zhì)的事件的概率,往往首先要計(jì)算出具有該性質(zhì)的事件的數(shù)目。
◎排列與組合
加法原理與乘法原理是在計(jì)數(shù)研究中最常用也是最基本的兩個(gè)法則。
一、加法原理
完成一件事有兩類不同方案(其中的方法互不相同)。在第1類方案中有m種不同的方法，在第2類方案中有n種不同的方法，那么完成這件事共有m+n種不同的方法。
例如：小華正準(zhǔn)備出國(guó)留學(xué)，不是去A國(guó)，就是去B國(guó)。其中A國(guó)有4所大學(xué)向他發(fā)出了錄取通知，而B國(guó)則有5所大學(xué)向他發(fā)出了入學(xué)邀請(qǐng)。故小華共有9所大學(xué)可以選擇，即共有9種留學(xué)方案。
二、乘法原理
完成一件事需要兩個(gè)步驟(第1步方法的選取不會(huì)影響第2步方法的選取)。做第1步有m種不同的方法，做第2步有n種不同的方法，那么完成這件事共有m×n種不同的方法。
例如，從A到B有3條不同的道路,從B到C有2條不同的道路,則從A經(jīng)B到C的道路數(shù)n=3×2=6。
三、排列與組合
排列組合的難點(diǎn)主要體現(xiàn)在對(duì)排列組合原理的理解與運(yùn)用上，也即確定是排列還是組合。排列與組合，前者與順序有關(guān)，后者與順序無關(guān)�？忌梢酝ㄟ^任選一種安排好的情況，調(diào)整其中兩個(gè)物體的前后順序，看是否會(huì)出現(xiàn)新的情形，若是則與順序有關(guān)，反之則與順序無關(guān)。對(duì)基本的排列組合題能夠迅速判斷是排列還是組合，并寫出對(duì)應(yīng)方法數(shù)�？忌赏ㄟ^多考慮一些應(yīng)用環(huán)境來鍛煉自己判斷排列組合的能力。
排列公式：
組合公式：
◎容斥原理
容斥原理又稱包含排斥原理，它是解決組合計(jì)數(shù)問題的重要工具。
加法原理告訴我們，在集合間沒有交集的情況下，求這些集合并集的簡(jiǎn)單計(jì)數(shù)公式。容斥原理則告訴我們一般情況下的公式，此時(shí)集合間可以重疊而沒有限制。
例如，在1到30的正整數(shù)中，有多少個(gè)整數(shù)能被2整除或能被3整除?
由于從1開始每連續(xù)2個(gè)的第2個(gè)數(shù)能被2整除，所以1到30中能被2整除的整數(shù)共30÷2=15個(gè)，它們分別是
2,4,6,8,10,12,14,16,18,20,22，24,26,28,30。
同理，由于從1開始每連續(xù)3個(gè)的第3個(gè)數(shù)能被3整除，所以1到30中能被3整除的整數(shù)共30÷3=10個(gè)，它們分別是
3,6,9,12,15,18,21,24,27,30。
又，同時(shí)能被2和3整除的整數(shù)共30÷(2×3)=5個(gè)，分別是
6,12,18,24,30。
所以計(jì)數(shù)時(shí)如果計(jì)算15+10=25，則重復(fù)計(jì)算了5個(gè)數(shù)。容斥原理可以幫我們巧妙地解決這一問題。
|A∪B|=|A|+|B|-|A∩B|
|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|B∩C|-|C∩A|+|A∩B∩C|
其中，兩集合容斥原理用簡(jiǎn)單語言敘述就是：
滿足條件1的個(gè)數(shù)+滿足條件2的個(gè)數(shù)-都滿足的個(gè)數(shù)=總數(shù)-都不滿足的個(gè)數(shù)=滿足至少一個(gè)條件的個(gè)數(shù)。
◎抽屜原理
抽屜原理是組合數(shù)學(xué)里最簡(jiǎn)單也是最基本的原理：n+1個(gè)物品放入n個(gè)抽屜中，則至少有一個(gè)抽屜，其中有兩個(gè)或更多的物品。也有人稱之為“鴿巢原理”,即“若有n個(gè)鴿子巢,n+1只鴿子,則至少有一個(gè)鴿子巢里至少有兩只鴿子”。
從這樣一個(gè)看來是顯而易見的原理出發(fā),可以導(dǎo)出許多組合數(shù)學(xué)中的并不那么顯而易見的有趣結(jié)論。下面先舉幾個(gè)例子,通過例子說明利用抽屜原理的一般步驟,從不同的例題中總結(jié)出規(guī)律。
例：
抽屜里有10雙手套,從中取11只出來,其中至少有兩只是完整配對(duì)的。
某次會(huì)議有n位代表參加,每一位代表至少認(rèn)識(shí)其余n-1位中的一位,則n位代表中,至少有兩位認(rèn)識(shí)的人數(shù)相等。
公考中，抽屜原理題目表述多為“黑色布袋中有……(具體物品)，至少要取出多少個(gè)，才可以保證……(滿足目標(biāo))”。
解決方案為反向構(gòu)造。即假設(shè)所有物品并非放在布袋中，而是在自己手中，然后逐一發(fā)出，在發(fā)出的過程中盡可能不要滿足題目的目標(biāo)，直到滿足目標(biāo)為止。那么在盡量不滿足題目要求情況下發(fā)出的最多數(shù)目就是題目的答案。
相關(guān)推薦：
2014年公務(wù)員考試行測(cè)專項(xiàng)備考：數(shù)字推理
