1.11 排列和组合

对某些计算，掌握试验结果的计数方法是有用的，如计数法则、排列和组合.

第一个定义是计数法则.计数法则是组合各项任务时的计数方法.例如，假设你拥有10件衬衫、3条牛仔裤、5双袜子、4件大衣和2顶帽子.从每类衣服中选择一件，能有多少种穿衣搭配？答案是有10×3×5×4×2=1200种不同的搭配.[6]

定理1.7 计数法则（counting rule）.如果一项工作包含K个不同任务，其中第k项任务有nk种实现方法，那么整个工作有n1n2···nK种实现方法.

计数法则虽然直观上很简单，但在很多建模中都很有用.

第二个定义是排列.排列（permutation）是重新排序.假设你在一个有30个学生的班级.有多少种方法安排学生的顺序？每一种安排方式都被称为一个“排列”.为计算排列数，观察到30个学生均可在第一个位置.在此条件下，有29个学生可以安排在第二个位置.在上述两个条件下，有28个学生可以排在第三个位置，以此类推.排列的总数为

30×29×···×1=30！

其中，符号！表示阶乘.（详见附录A.3.）

一般的结论如下.

定理1.8 N个元素的排列数为N！.

假设从一个30人的班级中，选出一个有序的由5名学生组成的小组参加比赛.能选出多少种有序的小组？计算方法与上面一样，但是第五个位置被填满就停止.因此，这个数字是

一般的结论如下.

定理1.9 从N个元素中一次选出K个的排列数为

第三个定义是组合.组合（combination）不考虑元素的顺序.例如，重新考虑选出5名学生的例子，现假设学生是无序的.问题变为：从一个有30名学生的班级中，能选出多少种不考虑顺序的小组？一般地，从N个元素中选出一个含有K个元素的组共有多少种方法？我们称其为“组合数”.

极端情况很容易处理.如果K=1，则有N种组合（每个学生是一组）.如果K=N，则有一种组合（整个班级是一组）.要计算一般的答案，注意，考虑顺序的组数是排列数P（N , K）.含有K个元素的一个组，考虑顺序共有K！种情况（等于组中K个元素的排列数）.因此，不考虑顺序的组的数量为P（N , K）/K！.我们得到下述定理.

定理1.10 从N个元素中一次选出K个的组合（combination）数为

符号表示“从N个中选出K个”，是组合中常用的标记.它们也被称为二项式系数（binomial coefficient），因为它们是二项式展开的系数.

定理1.11 二项式定理（binomial theorem）.对任意的整数N≥0，都有

二项式定理的证明见1.15节.

本节介绍的排列法和组合法在某些计数应用中很有用，但对概率的一般理解，可能不是必需的.我的观点是，应该理解这些工具的用法，在需要时可以检索这些工具，而不是死记硬背.