绪论：加法原理、乘法原理
分类计数原理：做一件事，有(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(mleq n))个元素的所有不同排列的个数，叫做从(n)个不同元素种取出(m)个元素的排列数，用符号(mathrm{A}_n^m)表示。
排列数公式
[mathrm{A}_n^m=n(n-1)(n-2)cdots(n-m 1)=frac{n!}{(n-m)!},quad n,min mathbb{N}^* ,text{并且}mleq n ]
（规定(0!=1)）
推导：把(n)个不同的元素任选(m)个排序，按计数原理分步进行：
取第一个：有(n)种取法； 取第二个：有((n-1))种取法； 取第三个：有((n-2))种取法； …… 取第(m)个：有((n-m 1))种取法；
根据分步乘法原理，得出上述公式。
排列数性质
(mathrm{A}_n^m = nmathrm{A}_{n-1}^{m-1}) 可理解为“某特定位置”先安排，再安排其余位置。
(mathrm{A}_n^m = mmathrm{A}_{n-1}^{m-1} mathrm{A}_{n-1}^m) 可理解为：含特定元素的排列有(mmathrm{A}_{n-1}^{m-1})，不含特定元素的排列为(mathrm{A}_{n-1}^m)。
组合问题
组合数
从(n)个不同元素种取出(m(mleq n))个元素的所有不同组合的个数，叫做从(n)个不同元素种取出(m)个元素的组合数，用符号(mathrm{C}_n^m)表示。
组合数公式
[mathrm{C}_n^m=frac{mathrm{A}_n^m}{mathrm{A}_m^m}=frac{n(n-1)(n-2)cdots (n-m 1)}{m!}=frac{n!}{m!(n-m)!},quad n,min mathbb{N}^* ,text{并且}mleq n ]
[mathrm{C}_n^0=mathrm{C}_n^n=1 ]
证明：利用排列和组合之间的关系以及排列的公式来推导证明。
将部分排列问题(mathrm{A}_n^m)分解为两个步骤：
第一步，就是从(n)个球中抽(m)个出来，先不排序，此即组合数问题(mathrm{C}_n^m)；
第二步，则是把这(m)个被抽出来的球排序，即全排列(mathrm{A}_m^m)。
根据乘法原理，(mathrm{A}_n^m=mathrm{C}_n^m mathrm{A}_m^m)，那么
[mathrm{C}_n^m=frac{mathrm{A}_n^m}{mathrm{A}_m^m}=frac{n(n-1)(n-2)cdots (n-m 1)}{m!}=frac{n!}{m!(n-m)!} ]
组合数的性质
(mathrm{C}_n^m = mathrm{C}_n^{n-m}) 可以理解为：将原本的每个组合都反转，把原来没选的选上，原来选了的去掉，这样就变成从(n)个元素种取出(n-m)个元素，显然方案数是相等的。
递推公式(mathrm{C}_n^m=mathrm{C}_{n-1}^m mathrm{C}_{n-1}^{m-1}) 可理解为：含特定元素的组合有(mathrm{C}_{n-1}^{m-1})，不含特定元素的排列为(mathrm{C}_{n-1}^m)。还不懂？看下面。
Example
从1，2，3，4，5（(n=5)）中取出2（(m=2)）个元素的组合（(mathrm{C}_n^m)）：
12 13 14 15 23 24 25 34 35 45
显然，这些组合中要么含有元素“1”，要么不含。
- 其中含有“1”的是：12 13 14 15 把里面的“1”都挖掉：2 3 4 5 而上面这个等价于从2，3，4，5（(n-1)）中取出1（(m-1)）个元素的组合。
- 其中不含“1”的是：23 24 25 34 35 45 上面等价于从2，3，4，5（(n-1)）中取出2（(m)）个元素的组合。
而总方案数等于上面两种情况方案数之和，即(mathrm{C}_n^m=mathrm{C}_{n-1}^m mathrm{C}_{n-1}^{m-1})。
组合数求和公式
[mathrm{C}_n^0 mathrm{C}_n^1 mathrm{C}_n^2 cdots mathrm{C}_n^n=2^n ]
我们感性认知一下，上面这个式子的左边表示什么呢？
把从(n)个球中抽出(0)个球的组合数（值为(1)）、抽出(1)个球的组合数、抽出(2)个球的组合数、……、抽出(n)个球的组合数相加。
换句话说，就是从(n)个球中随便抽出一些不定个数球，问一共有多少种组合。
对于第1个球，可以选，也可以不选，有2种情况。 对于第2个球，可以选，也可以不选，有2种情况。 对于任意一个球，可以选，也可以不选，有2种情况。
根据乘法原理，一共(underbrace{2times 2times cdots times 2}_{ntext{个2相乘}} = 2^n)种组合。
想要严谨的证明？数学归纳法：
- 当(n=1)时，(mathrm{C}_1^0 mathrm{C}_1^1=2=2^1)成立。
- 假设(n=k(kin mathbb{N}^*))时等式成立，即 [sum_{i=0}^{k} mathrm{C}_k^i=2^n ] 成立，当(n=k 1)时， [begin{aligned} & mathrm{C}_{k 1}^0 mathrm{C}_{k 1}^1 mathrm{C}_{k 1}^2 cdots mathrm{C}_{k 1}^{k} mathrm{C}_{k 1}^{k 1}\ = & mathrm{C}_{k 1}^0 left(mathrm{C}_k^0 mathrm{C}_k^1right) left(mathrm{C}_k^1 mathrm{C}_k^2right) cdots left(mathrm{C}_k^{k-1} mathrm{C}_k^kright) mathrm{C}_{k 1}^{k 1}\ = & left(mathrm{C}_k^0 mathrm{C}_k^1 mathrm{C}_k^2 cdots mathrm{C}_k^kright) left(mathrm{C}_k^0 mathrm{C}_k^1 mathrm{C}_k^2 cdots mathrm{C}_k^kright)\ = & 2 times 2^k\ = & 2^{k 1} end{aligned}] 等式也成立。
- 由1、2得，等式对(nin mathbb{N}^*)都成立。
也可偷懒地用二项式定理证明：
[(a b)^n=sum_{k=0}^{n}mathrm{C}_n^k a^{n-k}b^k ]
令(a=b=1)，就得到了
[sum_{i=0}^{n} mathrm{C}_n^i=2^n ]
类似的公式（由(mathrm{C}_n^m = mathrm{C}_n^{n-m})推导）：
[mathrm{C}_n^0 mathrm{C}_n^2 mathrm{C}_n^4 cdots = mathrm{C}_n^1 mathrm{C}_n^3 mathrm{C}_n^5 cdots =2^{n-1} ]
杨辉三角
这个神奇的图形和组合数、二项式定理密切相关。（图片来自百度百科）
杨辉三角可以帮助你更好地理解和记忆组合数的性质：
- 第(n)行的(m)个数可表示为 (mathrm{C}_{n-1}^{m-1})，即为从(n-1)个不同元素中取(m-1)个元素的组合数。
- 第(n)行的数字有(n)项。
- 每行数字左右对称（第(n)行的第(m)个数和第(n-m 1)个数相等，(mathrm{C}_n^m = mathrm{C}_n^{n-m})），由(1)开始逐渐变大。
- 每个数等于它上方两数之和（第(n 1)行的第(i)个数等于第(n)行的第(i-1)个数和第(i)个数之和，即(mathrm{C}_{n 1}^i=mathrm{C}_n^i mathrm{C}_n^{i-1})）。
- ((a b)^n)的展开式中的各项系数依次对应杨辉三角的第(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))、(_nmathrm{C}_k)、(^nmathrm{C}_k)、、[注3]，其中的C代表组合（combinations）或选择（choices）。很多计算机使用含有C的变种记号，使得算式只占一行的空间，相同理由也发生在置换数，例如写作(P( n , k ))。 ({displaystyle mathrm{C}_{n}^{k}}{displaystyle mathrm{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}^nbinom nk x^{n-k}y^k)
此数的另一出处在组合数学，表达了从(n)物中，不计较次序取(k)物有多少方式，亦即从一(n)元素集合中所能组成(k)元素子集的数量。
计算二项式系数
除展开二项式或点算组合数量之外，尚有多种方式计算的值。 (tbinom nk)
递归公式 以下递归公式可计算二项式系数：
(binom nk = binom{n-1}{k-1} binom{n-1}k quad forall n,kinN)
其中特别指定：
(binom n0 = 1 quad forall ninNcup{0}, binom 0k = 0 quad forall kinN).
此公式可由计算(1 X ) n −1 (1 X )中的X k项，或点算集合{1, 2, …, n }的k个元素组合中包含n与不包含n的数量得出。
显然，如果k > n，则。而且对所有n，，故此上述递归公式可于此等情况下中断。递归公式可用作建构帕斯卡三角形。 tbinom nk=0tbinom 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 {n-m}{i-m} ]
[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}^{n-k}{frac {(-1)^{r}(n 1)}{k r 1}}{binom {n-k}{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 {n-i }{i}=1 sum_{i=1}^{infty} binom {n-i}{i-1} sum_{i=1}^{infty} binom {n-i}{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{k-i}=binom {n m}k ]
三阶求和公式 主条目：李善兰恒等式
[{binom {n k}k}^2=sum_{j=0}^k {binom kj}^2 binom {n 2k-j}{2k} ]
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/168057.html原文链接：https://javaforall.cn
