算法专题（6）-组合数学

摘要

       算法专题（1）-信息学基本解题流程！

        算法专题（2）-模拟

        算法专题（3）-枚举

        算法专题（4）-递归与递推

        算法专题（5）-分治 

六、组合数学

概述：

组合数学又被称为离散数学，是数学中的一个重要分支。在信息学领域，主要用到的内容为排列、组合、容斥原理等。

1.知识点梳理：

Ø 加法原理与乘法原理

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

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

两个原理的区别：一个与分类有关，一个与分步有关；加法原理是“分类完成”，乘法原理是“分步完成”。

Ø 组合

Ø 鸽巢原理（抽屉原理）

简单形式：如果n＋1个物体被放进n个盒子，那么至少有一个盒子包含两个或更多的物体。

加强形式：令q_1, q₂, ... ,q_n为正整数。如果将q₁＋q₂＋…＋q_n－n＋1个物体放入n个盒子内，那么或者第一个盒子至少含有q₁个物体，或者第二个盒子至少含有q₂个物体，…，或者第n个盒子含有q_n个物体

Ø 容斥原理与错位排列

2. 重难点分析：

u 求解组合数学类题目时，需要明确该用哪种组合数学方法。

u 计算过程中，根据题目要求，使用直接求解公式或递推公式（一般使用递推公式）。

u 在需要用高精度运算情况下使用高精度。

3. 例题解析：