1. 组合数学基础
1.1 加法与乘法原理
加法原理
有两类方式可以从\(1\)走到\(2\)，上面的方式有\(1\)种方法，下面的有\(2\)种方法，我们要想从\(1\)走到\(2\)，总共有几种方法呢？
每种方法都可以一次到达，总方案数很显然是上面的加上下面的也就是\(1+2=3\)种。
若有\(n\)类方式，第\(i\)类方式有\(m_i\)种方法，则总共有：
\(m_1+m_2+m_3+……+m_n=\sum \limits_{i=1}^{n}m_i\)种方法
可以这样想，走上面的\(1\)种和下面的\(2\)种来到达，这种或的关系，类似于分类讨论的思想，就是加法原理。
乘法原理
发现从\(1\)走到\(3\)需要分成两步，第一步是从\(1\)走到\(2\)，第二步是从\(2\)走到\(3\)，由上面加法原理，第一步总共有\(3\)种情况，第二步总共有\(8\)种情况，第一步每种情况都有第二步的所有情况与之对应，所以共有\(3 \times 8=24\)种情况。
若有\(n\)步，第\(i\)步有\(m_i\)种方式，则总共有：
\(m_1 \times m_2 \times m_3 \times …… \times m_n = \prod \limits_{i=1}^{n}m_i\)种方法
这种且的关系，需要分步的，就是乘法原理。
1.2 排列与组合
排列
问题1描述：班里有6个人，挑出3个人排队，有几种排法？
我们想一想啊，我们总共需要挑三个人，那么我们选第一个人时，有几种情况？
显然是6种吧，每个人都可以选，那么第二个人呢？
由于选完了一个人，还有5个人可选，那么第二个人就有5种情况。
第3个人很显然了吧，有4种。
那么总共就有\(6 \times 5 \times 4 = 120\)种情况
这例子显然比较特殊，我们要得到一个一般性结论。
也就是：班里有\(n\)个人，挑出\(m\)个排队，有几种排法？
我们规定\(1 \times 2 \times 3 …… \times n = n!\)，\(n!\)就叫做\(n\)的阶乘。
那么我们如何来用含有\(m\)、\(n\)的式子来表示这个问题的答案呢？
通过上面的问题1发现，6人里选3人排列是从6乘到6-3+1，那么我们这个问题的结果就可以这个样子表示：
\(n(n-1)(n-2)……(n-m+1)\)
有人就要问了：？？？为啥是\(n-m+1\)嘞？
可以这样想：上面的6是不是对应\(n\),3是不是对应\(m\)哇？也就是我们从\(n\)乘到了\(n-m+1\)
也可以这样想：第1项是\(n\)吧，第2项是\(n-1\)吧，第3项是\(n-2\)吧，那第\(m\)项是不是就是\(n-(m-1)\)也就是\(n-m+1\)吧。
这个样子表示比较丑，而且好像使用上也没方便到哪去，那么我们可以考虑用阶乘来表示。
还是回到我们的问题1，观察一下，我们的式子是\(6 \times 5 \times 4\)，和阶乘也有共同点吧，都是顺序乘下去的。
但是阶乘是乘到1欸，我们就没有办法用阶乘表示了吗？
没事，稍加思考发现，我们可以把式子变成这样：\(\large \frac{6 \times 5 \times 4 \times 3 \times 2 \times 1}{3 \times 2 \times 1}\)
是不是就等于\(\large \frac{6!}{3!}\)呢？
再转化成我们的\(n\)、\(m\)是不是就是：
\(\large \frac{n!}{(n-m)!}\)
恭喜你，得到了排列数公式，我们用\(A_n^m\)表示从\(n\)中选\(m\)个的排列数，完整可以表示成：
\(\large A_n^m=\frac{n!}{(n-m)!}\)
我们人为规定\(A_n^0=1\)。
还有个常用的：\(A_n^n=n!\)，从\(n\)个里面选\(n\)个人排队的方式，也就是全排列。
组合
我们将问题1稍加改编得到问题2，也就是：班里有\(6\)个人，挑出\(3\)个比赛，有几种挑法？
欸？改了哪个地方呢？
稍加观察，我们发现，这个问题只需要选出来人，不用排队，也就是顺序不需要考虑，123和321这算同一个答案。
上面的排列问题不仅要选出来人，而且要把每种情况的排列，也就是每种情况的全排列求出来，我们要去掉这些重复的情况。
哦哦，有全排列啊，上面我们不是已经推过了嘛。
每种组合的全排列数应该是一样的吧？很显然，我们打个比方，选1、2、3号同学，那么是不是有\(3!\)种情况，4、5、6是不是也是？1、5、2是不是也是？
所以我们在排列数的基础上除以上个全排列数是不是就是我们的结果？
最终结果就是\(\large \frac{3!}{(6-3)!} \div 3!= \frac{3!}{3!(6-3)!}=20\)
再推广成一般情况：班里有\(n\)个人，挑出\(m\)个比赛，有几种挑法？
有了我们排列数的推理思路，类比到这里。回顾一下，我们是不是用的排列数除上的全排列数，也就是：
\(\LARGE \frac{A_n^m}{A_m^m}\)
展开：
\(\LARGE \frac{\frac{n!}{(n-m)!}}{m!}=\frac{n!}{m!(n-m)!}\)
欸，恭喜你，这就是组合数的式子，我们用\(C_n^m\)来表示，或者简单点表示成：\(n \choose m\)表示\(n\)里选\(m\)个。（甚至 \(\LaTeX写法就是\) n \choose m）,完整表示如下：
\(\large C_n^m=\frac{n!}{m!(n-m)!}\)