分类计数原理：做一件事，有\(n\)类办法，在第\(1\)类办法中有\(m_1\)种不同的方法，在第\(2\)类办法中有\(m_2\)种不同的方法，…，在第\(n\)类办法中有\(m_n\)种不同的方法，那么完成这件事共有\(N=m_1+m_2+…+m_n\)种不同的方法。

分步计数原理：完成一件事，需要分成\(n\)个步骤，做第\(1\)步有\(m_1\)种不同的方法，做第\(2\)步有\(m_2\)种不同的方法，…，做第\(n\)步有\(m_n\)种不同的方法,那么完成这件事共有\(N=m_1×m_2×\cdots ×m_n\)种不同的方法。

区别：分类计数原理是加法原理，不同的类加起来就是我要得到的总数；分步计数原理是乘法原理，是同一事件分成若干步骤，每个步骤的方法数相乘才是总数。

从\(n\)个不同元素种取出\(m(m\leq n)\)个元素的所有不同排列的个数，叫做从\(n\)个不同元素种取出\(m\)个元素的排列数，用符号\(A_n^m\)表示。

\[A_n^m=n(n-1)(n-2)\cdots(n-m+1)=\frac{n!}{(n-m)!},\quad n,m\in \mathbb{N}^* ,\text{并且}m\leq n \] （规定\(0!=1\)）

推导：把\(n\)个不同的元素任选\(m\)个排序，按计数原理分步进行：

取第一个：有\(n\)种取法； 取第二个：有\((n-1)\)种取法； 取第三个：有\((n-2)\)种取法； …… 取第\(m\)个：有\((n-m+1)\)种取法；

根据分步乘法原理，得出上述公式。

\(A_n^m = nA_{n-1}^{m-1}\) 可理解为“某特定位置”先安排，再安排其余位置。

\(A_n^m = mA_{n-1}^{m-1} + A_{n-1}^m\) 可理解为：含特定元素的排列有\(mA_{n-1}^{m-1}\)，不含特定元素的排列为\(A_{n-1}^m\)。

从\(n\)个不同元素种取出\(m(m\leq n)\)个元素的所有不同组合的个数，叫做从\(n\)个不同元素种取出\(m\)个元素的组合数，用符号\(C_n^m\)表示。

\[C_n^m=\frac{A_n^m}{A_m^m}=\frac{n(n-1)(n-2)\cdots (n-m+1)}{m!}=\frac{n!}{m!(n-m)!},\quad n,m\in \mathbb{N}^* ,\text{并且}m\leq n \]

\[C_n^0=C_n^n=1\]

证明：利用排列和组合之间的关系以及排列的公式来推导证明。

将部分排列问题\(A_n^m\)分解为两个步骤： 

第一步，就是从\(n\)个球中抽\(m\)个出来，先不排序，此即组合数问题\(C_n^m\)；

第二步，则是把这\(m\)个被抽出来的球排序，即全排列\(A_m^m\)。

根据乘法原理，\(A_n^m=C_n^m A_m^m\)，那么\[C_n^m=\frac{A_n^m}{A_m^m}=\frac{n(n-1)(n-2)\cdots (n-m+1)}{m!}=\frac{n!}{m!(n-m)!}\]

\(C_n^m = C_n^{n-m}\) 可以理解为：将原本的每个组合都反转，把原来没选的选上，原来选了的去掉，这样就变成从\(n\)个元素种取出\(n-m\)个元素，显然方案数是相等的。

递推公式\(C_n^m=C_{n-1}^m+C_{n-1}^{m-1}\) 可理解为：含特定元素的组合有\(C_{n-1}^{m-1}\)，不含特定元素的排列为\(C_{n-1}^m\)。还不懂？看下面。

Example

从1，2，3，4，5（\(n=5\)）中取出2（\(m=2\)）个元素的组合（\(C_n^m\)）：

12 13 14 15 23 24 25 34 35 45

显然，这些组合中要么含有元素“1”，要么不含。

其中含有“1”的是：12 13 14 15

把里面的“1”都挖掉：2 3 4 5

其中不含“1”的是：23 24 25 34 35 45 上面等价于从2，3，4，5（\(n-1\)）中取出2（\(m\)）个元素的组合。

而总方案数等于上面两种情况方案数之和，即\(C_n^m=C_{n-1}^m+C_{n-1}^{m-1}\)。

\[C_n^0+C_n^1+C_n^2+\cdots+C_n^n=2^n\]

我们感性认知一下，上面这个式子的左边表示什么呢？

把从\(n\)个球中抽出\(0\)个球的组合数（值为\(1\)）、抽出\(1\)个球的组合数、抽出\(2\)个球的组合数、……、抽出\(n\)个球的组合数相加。

换句话说，就是从\(n\)个球中随便抽出一些不定个数球，问一共有多少种组合。

对于第1个球，可以选，也可以不选，有2种情况。 对于第2个球，可以选，也可以不选，有2种情况。 对于任意一个球，可以选，也可以不选，有2种情况。

根据乘法原理，一共\(\underbrace{2\times 2\times \cdots \times 2}_{n\text{个2相乘}} = 2^n\)种组合。

想要严谨的证明？数学归纳法：

也可偷懒地用二项式定理证明（其实二项式定理也是用数学归纳法证明的）：

\[(a+b)^n=\sum_{k=0}^{n}C_n^k a^{n-k}b^k\] 令\(a=b=1\)，就得到了\[\sum_{i=0}^{n} C_n^i=2^n\]

类似的公式（由\(C_n^m = C_n^{n-m}\)推导）：

\[C_n^0 + C_n^2 + C_n^4 + \cdots = C_n^1 + C_n^3 + C_n^5 + \cdots =2^{n-1}\]

这个神奇的图形和组合数、二项式定理密切相关。（图片来自百度百科）

杨辉三角可以帮助你更好地理解和记忆组合数的性质：

以下来自维基百科（我只是随便贴这）

二项式系数

二项式系数可排列成帕斯卡三角形。 在数学上，二项式系数是二项式定理中各项的系数。一般而言，二项式系数由两个非负整数\(n\)和\(k\)为参数决定，写作，定义为的多项式展开式中，项的系数，因此一定是非负整数。如果将二项式系数写成一行，再依照顺序由上往下排列，则构成帕斯卡三角形。 \(\tbinom nk {\displaystyle (1+x)^{n}}x^{k}{\displaystyle {\binom {n}{0}},{\binom {n}{1}},\dots ,{\binom {n}{n}}}{\displaystyle n=0,1,2,\dots }\)

二项式系数常见于各数学领域中，尤其是组合数学。事实上，可以被理解为从\(n\)个相异元素中取出\(k\)个元素的方法数，所以大多读作「\(n\)取\(k\)」。二项式系数的定义可以推广至\(n\)是复数的情况，而且仍然被称为二项式系数。

二项式系数亦有不同的符号表达方式，包括：\(C(n,k)\)、\(_nC_k\)、\(^nC_k\)、、[注3]，其中的C代表组合（combinations）或选择（choices）。很多计算机使用含有C的变种记号，使得算式只占一行的空间，相同理由也发生在置换数，例如写作\(P( n , k )\)。 \({\displaystyle C_{n}^{k}}{\displaystyle C_{k}^{n}}{\displaystyle P_{k}^{n}}\)

定义及概念 对于非负整数\(n\)和\(k\)，二项式系数定义为的多项式展开式中，项的系数，即 \(\tbinom nk{\displaystyle (1+x)^{n}}x^{k}\)

\({\displaystyle (1+x)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}x^{k}={\binom {n}{0} }+{\binom {n}{1}}x+\cdots +{\binom {n}{n}}x^{n}}\) 事实上，若\(x\)、\(y\)为交换环上的元素，则

\((x+y)^n=\sum_{k=0}^n\binom nk x^{nk}y^k\)

此数的另一出处在组合数学，表达了从\(n\)物中，不计较次序取\(k\)物有多少方式，亦即从一\(n\)元素集合中所能组成\(k\)元素子集的数量。

计算二项式系数

除展开二项式或点算组合数量之外，尚有多种方式计算的值。 \(\tbinom nk\)

递归公式 以下递归公式可计算二项式系数：

\(\binom nk = \binom{n-1}{k-1} + \binom{n-1}k \quad \forall n,k\in\N\)

其中特别指定：

\(\binom n0 = 1 \quad \forall n\in\N\cup\{0\}, \binom 0k = 0 \quad \forall k\in\N\).

此公式可由计算(1 + X ) n −1 (1 + X )中的X k项，或点算集合{1, 2, ..., n }的k个元素组合中包含n与不包含n的数量得出。

显然，如果k > n，则。而且对所有n，，故此上述递归公式可于此等情况下中断。递归公式可用作建构帕斯卡三角形。 \tbinom nk=0\tbinom nn=1

帕斯卡三角形(杨辉三角)

有关二项式系数的恒等式

关系式

阶乘公式能联系相邻的二项式系数，例如在k是正整数时，对任意n有：

\({\binom {n+1}{k}}={\binom {n}{k}}+{\binom {n}{k-1}} \binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1} \binom {n-1}{k} - \binom{n-1}{k-1} = \frac{n-2k}{n} \binom{n}{k}\).

两个组合数相乘可作变换：

\[\binom ni \binom im=\binom nm \binom {nm}{im} \sum_{r=0}^n \binom nr = 2^{n} \]

\[{\displaystyle \sum _{r=0}^{k}{\binom {n+r-1}{r}}={\binom {n+k}{k}}}\]

\[{\displaystyle \sum _{r=0}^{nk}{\frac {(-1)^{r}(n+1)}{k+r+1}}{\binom {nk}{r} }={\binom {n}{k}}^{-1}}\]

\[ \sum_{r=0}^n \binom {dn}{dr}=\frac{1}{d}\sum_{r=1}^d (1+e^{\frac{2 \pi ri}{ d}})^{dn}\]

\[ \sum_{i=m}^n \binom {a+i}{i} = \binom {a+n+1}{n} - \binom {a+m}{m-1} \]

\[ \binom {a+m}{m-1} + \binom {a+m}{m} + \binom {a+m+1}{m+1} + ... + \binom {a+n} {n} = \binom {a+n+1}{n} \]

\[ F_n=\sum_{i=0}^{\infty} \binom {ni}{i}\]

\[ F_{n-1}+F_n=\sum_{i=0}^{\infty} \binom {n-1-i}{i}+\sum_{i=0}^{\infty} \binom {ni }{i}=1+\sum_{i=1}^{\infty} \binom {ni}{i-1}+\sum_{i=1}^{\infty} \binom {ni}{i} =1+\sum_{i=1}^{\infty} \binom {n+1-i}{i}=\sum_{i=0}^{\infty} \binom {n+1-i}{ i}=F_{n+1}\] 主条目：朱世杰恒等式\[ \sum_{i=m}^n \binom ia = \binom {n+1}{a+1} - \binom {m}{a+1} \binom {m}{a+1} + \binom ma + \binom {m+1}a ... + \binom na = \binom {n+1}{a+1} \] 二阶求和公式\[{\displaystyle \sum _{r=0}^{n}{\binom {n}{r}}^{2}={\binom {2n}{n}}}\]\[\sum_{i=0}^n \binom {r_1+n-1-i}{r_1-1} \binom {r_2+i-1}{r_2-1}=\binom {r_1+r_2+n-1 }{r_1+r_2-1}\]\[(1-x)^{-r_1} (1-x)^{-r_2}=(1-x)^{-r_1-r_2}\]\[(1-x)^{-r_1} (1-x)^{-r_2}=(\sum_{n=0}^{\infty} \binom {r_1+n-1}{r_1-1} x^ n)(\sum_{n=0}^{\infty} \binom {r_2+n-1}{r_2-1} x^n)=\sum_{n=0}^{\infty} (\sum_{ i=0}^n \binom {r_1+n-1-i}{r_1-1} \binom {r_2+i-1}{r_2-1}) x^n \]\[(1-x)^{-r_1-r_2}=\sum_{n=0}^{\infty} \binom {r_1+r_2+n-1}{r_1+r_2-1} x^n\] 主条目：范德蒙恒等式\[\sum_{i=0}^k \binom ni \binom m{ki}=\binom {n+m}k\] 三阶求和公式 主条目：李善兰恒等式\[{\binom {n+k}k}^2=\sum_{j=0}^k {\binom kj}^2 \binom {n+2k-j}{2k}\]