借容斥原理解排列組合和概率題

容斥原理是解決有限集合計數問題的重要原理之一． 事實上我們在利用加法原理解題時，就是先將問題分劃成若干個兩兩互不相交的子集（分類討論），再求各個集合中元素的個數． 但是在許多問題中，將其劃分為數個兩兩互不相交的集合并非易事，而容斥原理在一定程度上解決了這個問題． 熟練地掌握容斥原理的運用對解決高中數學中一些較難的題目有一定的幫助．

下面我們給出容斥原理的兩種等價形式，即以下的定理1和定理2，其中

表示有限集合A中的元素個數．

當k=3時，A∪B∪C=A+B+C－A∩B－A∩C－B∩C+A∩B∩C．

定理2設A1，A2，A3，…，Ak是集合S的k個子集合，則

由這兩個定理，我們可以解決一些需要討論多次的題目．

用容斥原理來解題時，關鍵在于能否用集合語言或符號語言將所要解決的問題表示出來．

一、在排列中的應用

先來看一道老題.

某市的4個化工廠，為了降低成本，適應市場變化，合并成一個化工集團公司，公司董事會由7名董事組成.

產生的7名董事全部分到各工廠進行生產管理，每廠至少一名，有幾種分法？

解析：方法一 —— 分情況討論

最后的分配方式有三種可能，（1）一個工廠4個，其余各1個；（2）一個工廠3個，一個工廠2個，其余各一個；（3）一工廠1個，其余各2個．

可得最后結果為CCA+CCCCA+CCCCC=8 400種．

方法二 —— 容斥原理

將這四個化工廠命名為A1，A2，A3，A4，設B1表示工廠A1無董事派入，B2表示工廠A2無董事派入，B3表示工廠）=47－4·37+C·27－C·17+C·0=8 400．

由此可知，容斥原理主要用于多個獨立條件共同作用的計數問題中．在高中數學中最常見的就是有限制的排列問題，下面，筆者列舉數例．

例19個人站成三排，第一排2人，第二排3人，第三排4人，其中甲不在第一排左端，乙不在第三排的右端，則有幾種排法？（禁位排列）

解析：設A表示甲站在第一排左端，B表示乙站在第三排右端，則有A=B=A，A∩B=A，依題意有，滿足條件的排法總=A－2A+A.

與容斥原理相同的思路，我們還可以得到下面幾個關系式．

上述公式可以用韋恩圖進行驗證．

例29個人站成三排，第一排2人，第二排3人，第三排4人，其中甲不在第一排左端，乙不在第三排的右端，丙必須站在第三排，問此時有幾種排法？

解析：此題用分類討論的方法可以得到解決，但靈活性較強． 同時此題也可以用上面所給出的公式直接求解．

方法一 —— 分類討論

對丙的情況進行討論，（1）當丙不在第三排右端時，排法先排丙有A種排法，再排剩下8人，按容斥原理（同例1）可得剩下8人的排法總數為A－2A+A，則這種情況的排法總數為A·（A-2A+A）=92 880；（2）當丙排在第三排右端時，分兩種情況進行討論：①當乙排在第一排左端時，有A=5 040種排法，②當乙不在第一排左端時有A·A·A=30 240種排法． 綜上，滿足條件的排法有92 880+5 040+30 240=128 160種排法．

方法二 —— 直接套用公式

設A1表示丙在第三排；A2表示甲在第一排左端；A3表示乙在第三排右端． 依題意有

二、在古典概型中的應用

因為古典概型和排列組合是一脈相承的，所以容斥原理也可以應用于概率問題． 對于獨立事件來說有如下公式．

設A，B是兩相互獨立的事件，P（A），P（B）表示A，B發生的概率，A+B表示A或B發生，A·B表示A和B同時發生，則有

P（A+B）=P（A）+P（B）－P（A）·P（B）.

對其進行推廣，當A1，A2，A3，…，An為n個相互獨立的事件，則有

P（A1＋A2＋A3＋…＋An）=P（Ai）－P（Ai）P（Aj）+P（Ai）· P（Aj）P（At）+…+（-1）n-1P（A1）P（A2）P（A3）·…·P（An），由數學歸納法可得上述結論．

和計數問題的思路一致，先將滿足條件的事件寫出，再套用公式即可解答概率問題．

例3甲、乙、丙三人各進行一次射擊，如果三人擊中目標的概率都是0.6，求

（Ⅰ）三人都擊中目標的概率；

（Ⅱ）至少有一人擊中目標的概率．

解析：（Ⅰ）P（A·B·C)=P（A）·P（B）·P（C）=0.63=0.216；

（Ⅱ）P（A+B+C）=P（A）+P（B）+P（C）－P（A）P（B）－P（B）P（C）－P（A）P（C）+P（A）P（B）P（C）=0.6×3－3×0.62+0.63=0.936．

例4如圖1所示，電路中五個方框均為保險匣，A，B，C，D，E各個保險絲被燒斷的概率分別為，，，，，且通電后保險絲是否燒斷是相互獨立的，則通電后不斷路的概率為多少？

[A][B][C][D][E]

圖1

解析：若我們設A′，B′，C′，D′，E′分別表示A，B，C，D，E不被燒斷這一事件． 依題意得，P（A′）=，P（B′)=，P（C′）=，P（D′）=，P（E′）=，通電后不斷路這一事件可寫成（A′·B′＋C′）·（D′＋E′），由A′，B′，C′，D′，E′相互獨立，則所求概率為

P［（A′·B′＋C′）·（D′＋E′）］

＝P（A′·B′＋C′）·P（D′＋E′）

=［P（A′·B′）+P（C′）－P（A′·B′·C′）］［P（D′）+P（E′）－P（D′·E′）］

=

對于可以用容斥原理及相關推論解決的題來說，先準確地寫出事件，再套用公式可以避免解題中過多的討論．

參考文獻

（1）楊振生著. 《組合數學及其算法》. 中國科學技術大學出版社，1997年11月.

（2）葉軍著. 《數學奧林匹克教程》. 湖南師范大學出版社，2003年6月.