摘要

概述：

組合數(shù)學(xué)又被稱為離散數(shù)學(xué)，是數(shù)學(xué)中的一個重要分支。在信息學(xué)領(lǐng)域，主要用到的內(nèi)容為排列、組合、容斥原理等。

1.知識點梳理：

? 加法原理與乘法原理

加法原理：做一件事情，完成它可以有n類辦法，在第一類辦法中有m₁種不同的方法，在第二類辦法中有m₂種不同的方法，……，在第n類辦法中有m_n種不同的方法。那么完成這件事共有N＝m₁＋m₂＋,…,＋m_n種不同的方法。

乘法原理：做一件事情，完成它需要分成n個步驟，做第一步有m₁種不同的方法，做第二步有m₂種不同的方法，……，做第n步有種m_n不同的方法，那么完成這件事有N＝m₁*m₂*,…,*m_n種不同的方法。

兩個原理的區(qū)別：一個與分類有關(guān)，一個與分步有關(guān)；加法原理是“分類完成”，乘法原理是“分步完成”。

? 組合

? 鴿巢原理（抽屜原理）

簡單形式：如果n＋1個物體被放進n個盒子，那么至少有一個盒子包含兩個或更多的物體。

加強形式：令q_1, q₂, ... ,q_n為正整數(shù)。如果將q₁＋q₂＋…＋q_n－n＋1個物體放入n個盒子內(nèi)，那么或者第一個盒子至少含有q₁個物體，或者第二個盒子至少含有q₂個物體，…，或者第n個盒子含有q_n個物體

? 容斥原理與錯位排列

2. 重難點分析：

u 求解組合數(shù)學(xué)類題目時，需要明確該用哪種組合數(shù)學(xué)方法。

u 計算過程中，根據(jù)題目要求，使用直接求解公式或遞推公式（一般使用遞推公式）。

u 在需要用高精度運算情況下使用高精度。

3. 例題解析：