排列组合分析
本文介绍最简单的数数规则，这类的概率问题可难也可简单。我记得上高中的时候比较麻烦的一个问题是两盒火柴的问题，大意如下：两个火柴盒里面放火柴，然后随机抽取，问第n次以后恰好第一个盒子的火柴被抽光的概率。这类的问题需要掌握一些基本的规则，按照规则逐步计算会容易的多。
计数基本法则 如果一共有r个试验，试验1有n1中结果，对于试验1的每一种可能，试验2都有n2中结果，对于前两个试验的每一种可能的结果，试验3都有n3种结果，依次类推，这r个试验一共有n1n2…nr种结果。
排列 假设有n个互不相同的元素，则一共有n!个排列结果。如果这n个元素，其中n1个彼此相同，另n2个彼此相同，依次类推，nr个也彼此相同，那么一共排列的个数为：
n!n1!n2!…nr!组合 一般来说，如果考虑顺序，从n个元素中取出r个排成一组，一共有n(n−1)…(n−r+1)种不同的方式，而每个包含r个元素的小组都被重复计算了r!次。所以从n个元素中取出r个组成不同组的数目为：
n(n−1)…(n−r+1)r!=n!(n−r)!r!因此，如果不考虑顺序， (nr)表示从n个元素中取出r个元素所组成的不同组的数目。
假设在一排n个天线中，有m个是失效的，另n−m个时有效的。假设所有有效天线不可区分，所有失效的天线之间也不可区分。为有多少中线性排列方式，使得任何两个失效的天线都不相邻？
把n−m个有效天线排一排。既然不允许连续两个失效天线在一起，那么这两个有效天线之间必然至多放置 一个失效的。即在n−m+1的位置中选择m个来放置，因此有(n−m+1m)种放置方法。
一个非常有用的组合恒等式：
(nr)=(n−1r−1)+(n−1r)这个式子的证明可以从分析的角度来证明，也可以从组合的角度来证明。当然，从组合的角度来证明更能显示出这个式子的意义。设想从n个元素中取r个，一共有(nr)种取法。从另一个角度来考虑，不妨假设这n个元素里有一个特殊的，记为元素1，那么取r个元素就有两种结果：取元素1或者不取1。取元素1时，一共有(n−1r−1)中方法；不取元素1时，一共有(n−1r)。两者之和就是从n个元素里取r个的方法直和，而从n个元素中取r个共有(nr)。
(nr)经常成为二项式系数，因为他们是二项式定理中重要的系数。接下来用两种方法证明二项式定理
首先我们用数学归纳法来证明。
当n=1时，x+y=(10)x0y1+(11)x1y0=y+x 假设式 (4) 对于n−1成立,那么对于n:
(x+y)n=(x+y)n−1(x+y)=n−1∑i=0(n−1i)xiyn−1−i(x+y)=n−1∑i=0(n−1i)xi+1yn−1−i+n−1∑i=0(n−1i)xiyn−i对于上式右端第一项令k=1+i，右端第二项令i=k，则：
(x+y)n=n−1∑i=0(n−1i)xi+1yn−1−i+n−1∑i=0(n−1i)xiyn−i=n∑k=1(n−1k−1)xkyn−k+n−1∑k=0(n−1k)xkyn−k=xn+n−1∑k=1(n−1k−1)xkyn−k+n−1∑k=1(n−1k)xkyn−k+yn=xn+n−1∑k=1((n−1k−1)+(n−1k))xkyn−k+yn=xn+n−1∑k=1(nk)xkyn−k+yn=n∑k=0(nk)xkyn−k接下来给出另外一种证明方法。考虑乘积：
(x1+y1)…(xn+yn)它展开后包括2n个求和项，每一项都是n个因子的乘积，而且每一项都包含因子xi或者yi，i=1,…,n，例如： (x1+y1)(x2+y2)=x1x2+x1y2+y1x2+y1y2
一个含有n个元素的集合一共有多少子集？
第一种解法：含有k个元素的集合一共有(nk)个，因此所求答案是：n∑k=0(nk)=(1+1)n=2n