做一件事，完成他的方法可以分为\(n\)个互不相交的类，每一类有\(a_i\)中方法，则完成这件事一共有
\[
a_1+a_2+...+a_n
\]
种方法。
加法原理的核心思想就是，把“整体”分作每个“部分”，分别对每个部分进行计数，最后求和。
若完成一件事有\(n\)个步骤，每个步骤有\(a_i\)种方法，则完成这件事一共有
\[
a_1\times a_2 \times ...\times a_n
\]
种方法。
乘法原理的核心思想就是，把这件事分成几个步骤，且每一个步骤的方法数目比较好确定。
加乘原理很简单，你们小学奥数学的都比本蒟蒻强，但加乘原理是计数的基础。
一般地，从\(n\)个不同元素中取出\(m（m≤n）\)个元素，按照一定的顺序排成一列，叫做从\(n\)个元素中取出\(m\)个元素的一个排列，记作\(A_n^m\)（或者记作\(P_n^m\)）。
由乘法原理得：
\[
A_n^m=n\times(n-1)\times (n-2)\times\dots\times (n-m+1)
\]
特别地，如果\(m=n\)，则我们就可以得到关于\(n\)的全排列：
\[
A_n^n=n\times(n-1)\times(n-2)\times \dots \times 1=n!
\]
我们约定\(0!=1\)，则排列公式可写为
\[
A_n^m=\frac{n!}{(n-m)!}
\]
这也是这个公式的更为常见的形式。
一般地，从\(n\)个不同的元素中，任取\(m（m≤n）\)个元素为一组，叫作从\(n\)个不同元素中取出\(m\)个元素的一个组合，记作\(C_n^m\)（或者记作\(\binom{n}{m}\)）
组合和排列数的区别是，组合数要求无序
所以我们可以得到：
\[
C_n^m=\frac{A_n^m}{m!}
\]
展开我们可以得到：
\[
C_n^m=\frac{n!}{m!(n-m)!}
\]
关于排列和组合还有一些经典的数学问题，由于纯数学不是我们讨论的重点，这里仅给出结论，需要证明的可以自行在网上查阅。
1.可重排列：\(n^m\)
2.有限元素的可重排列：\(\frac{n!}{n_1!\times n_2!\times \dots \times n_m!}\)
3.可重组合：\(C_{n+m-1}^m\)
4.有限元素的可重组合：\(C_{m+k-1}^{k-1}\)（这里\(k\)小于等于每个元素的数量）
组合数\(C_n^m\)也被称作二项式系数，它有三重面目：
1.组合意义：\(n\)个不同元素的\(m\)-组合
2.显示表示：\(C_n^m=\frac{n!}{m!\times (n-m)!}\)
3.二项展开式的系数，即有恒等式
\[
(x+y)^n=\sum^n_{i=0}C_n^i\times x^n \times y^{n-i}
\]
上面的恒等式称为二项式定理。
二项式定理的证明有很多种，这里给出一种基于其组合意义的证明：
显然
\[
(x+y)^n=\begin{matrix}\underbrace{(x+y)(x+y)\dots(x+y)} \\ n个(x+y) \end{matrix}
\]
对于其中的一项\(x^iy^{n-i}\)，相当于是从\(n\)个\((x+y)\)中任意取\(i\)个，从中挑出\(x\)，再在剩下的\((x+y)\)中挑出\(y\)来相乘，所以该项的系数是\(C_n^i\)，由此不难验证二项式定理。
常见的组合恒等式有以下几个，它们大多都和二项式相关
\[ C_n^m=C_n^{n-m} \]
\[ C_n^m=C_{n-1}^m+C_{n-1}^{m-1} \]
\[ C_n^0+C_n^1+C_n^2+\dots+C_n^n=2^n \]
\[
C_n^0<C_n^1<\dots<C_n^{\frac{n}{2}}>\dots>C_n^{n-1}>C_n^n
\]
若\(n\)是奇数，则
\[ C_n^0<C_n^1<\dots<C_n^{\frac{n-1}{2}}=C_n^{\frac{n+1}{2}}>\dots>C_n^{n-1}>C_n^n \]
\[ C_n^0+C_{n+1}^1+\dots+C_{n+k}^k=C_{n+k+1}^{k+1} \]
\[ C_n^0-C_n^1+C_n^2+\dots+(-1)^nC_n^n=0 \]
\[ C_{m}^0C_n^k+C_m^1C_n^{k-1}+C_m^2C_n^{k-2}+\dots+C_m^kC_n^0=C_{n+m}^k \]
\[ C_n^k=\frac{n}{k}C_{n-1}^{k-1} \]
\[
C_n^kC_k^m=C_n^mC_{n-k}^{m-k}
\]
它们的证明如下：
1.从\(n\)个数中选\(m\)个数，他们呢构成了一个，剩下没选的数也构成了一个集合，等式一显然成立。
2.假设我们现在面对的是第\(n\)号元素，我们无非就两种选择：选和不选。
如果我们选择第\(n\)号元素，那么我们就需要在前\(n-1\)个元素中选\(m-1\)个元素。
如果我们不选择第\(n-1\)号元素，那么我们就需要在前\(n-1\)一元素中选\(m\)个元素。
由加法原理不难验证等式2的正确性。
3.从\(n\)个元素中取任意个元素，要么选，要么不选，所以是\(2^n\)种。
我们也可以看成取0个，取1个， 取2个，...，取\(n\)个，就相当于等式的左边。
所以等式3成立。
4.我们完全可以通过暴力展开的形式来证明，或者我们结合性质1也不难证明
5.反复运用递推公式，我们有：
\[
C_n^0+C_{n+1}^1=C_{n+1}^0+C_{n+1}^1=C_{n+2}^1\C_{n+2}^1+C_{n+2}^2=C_{n+3}^2\C_{n+3}^2+C_{n+3}^3=C_{n+4}^3\\cdots\C_{n+k}^{k-1}+C_{n+k}^k=C_{n+k+1}^k
\]
6.在二项式定理中取\(x=1\)，\(y=-1\)即可。
推论：
\[
C_n^0+C_n^2+C_n^4+\dots=C_n^1+C_n^3+C_n^5+\dots
\]
7.同样地，我们仍然可以暴力展开证明，但很麻烦。
我们仍然考虑从它的组合意义上证明。
如果我们从\(n\)个zrw和\(m\)个lsy中任意选取\(k\)个人组成一组，显然，答案为\(C_{n+m}^k\)。
所有的方案可以分为\(k+1\)个类：第\(i\)类由\(i\)个zrw和\(k-i\)个lsy组成一组（\(i\in[0,k]且i\in \Z\)），每一类的答案就是\(C_n^iC_m^{k-i}\)，根据加法原理不难验证等式7的正确性。
8&9.暴力展开得
\[
\begin{align}
C_n^kC_k^m &=\frac{n!}{k!(n-k)!}\times\frac{k!}{m!(k-m)!}\&=\frac{n!}{m!(n-m)!}\times\frac{(n-m)!}{(k-m)!(n-k)!}\&=C_n^mC_{n-k}^{m-k}
\end{align}
\]
当\(k=1\)时即为等式8
这部分可以看看本蒟蒻的一篇博客：二项式反演笔记
如有不足尽请指正，谢谢！
参考资料：
1.华东师范大学出版社 《奥数教程》高中第三分册
2.李煜东 《算法竞赛进阶指南》
原文：https://www.cnblogs.com/ybwowen/p/11216720.html