扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
下载作业帮安装包
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
一个数由4个10,3个1,2个0.01和8个0.001组成,这个数是?
作业帮用户
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
一个数由4个10,3个1,2个0.01和8个0.001组成,这个数是43.028
为您推荐：
其他类似问题
扫描下载二维码 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
四年级数学思考题
下载积分：800
内容提示：四年级数学思考题
文档格式：DOC|
浏览次数：93|
上传日期： 15:59:28|
文档星级：
全文阅读已结束，如果下载本文需要使用
 800 积分
下载此文档
该用户还上传了这些文档
四年级数学思考题
关注微信公众号第 4 章　组合与概率
第 4 章　组合与概率
在计算机科学中，我们常需要为事物计数，并度量事件的可能性。计数属于数学中的组合学分支，而度量事件的可能性则属于概率论的范畴。本章要介绍这两个领域的基本原理。我们会了解到一些问题的答案，诸如程序中有多少条执行通路（execution path），或给定通路出现的可能性有多大等。
4.1　本章主要内容
本章给出了一系列越来越复杂的情况，每种情况都通过一个简单的范例问题说明，借此对组合（或“计数”）加以研究，而且会为每个问题推导出用于确定可能结果数量的公式。要研究的问题包括以下几个。
为分配计数（4.2节）。范例问题是：用k 种颜色为n 所房屋粉刷共有多少种不同方式。
为排列计数（4.3节）。范例问题是：确定n 个不同项能构成多少种不同的次序。
为有序选择计数（4.4节），也就是从n 个不同事物中选出k 个，并按次序排列这k 个事物。范例问题是：计算赛马比赛中不同马匹获得前三名的排列方法数。
为n 个事物中的m 个的组合计数（4.5节），也就是从n 个不同对象中选择m 个，而不考虑被选取对象的次序。范例问题是：为可能的扑克牌型计数。
为具有某些重复项的排列计数（4.6节）。范例问题是：计算某些字母多次出现的单词的变位词的数量。
为分发容器中对象（可能具有重复对象）的方法计数（4.7节）。范例问题是：为给小朋友分发水果的方法计数。
本章的后半部分要讨论的是概率论，涵盖以下主题。
基本概念：概率空间、实验、事件、事件概率。
条件概率与事件独立性。这些概念可帮助我们了解，对一次实验结果（比如纸牌的牌面图案）的观察会怎样影响未来事件的概率。
概率推理和方法。通过这些推理和方法，可从与事件的概率及条件概率相关的有限数据中，估算出事件组合的概率。
我们还将讨论概率论在计算机领域的一些应用，包括根据数据进行或然性推理的系统，以及一类“有很大概率”有效但不保证一直有效的算法。
4.2　为分配计数
一种简单却极重要的计数问题是处理一组项，为每一项指定某一组固定值中的某个值。我们需要确定可能有多少种将值分配给项的方式。
图4-1展示了一个典型的例子，其中有并排4所房屋，而且可将每所房屋粉刷成红、绿、蓝这三种颜色中的一种。在本例中，房屋就是之前所提到的“项”，而颜色就是“值”。图4-1展示了一种可能的颜色分配方式，其中第一所房屋被刷成红色，第二所和第四所被刷成蓝色，而第三所被刷成绿色。
图 4-1　房屋颜色分配的一种方式
要回答“有多少种不同分配方式”，首先需要定义我们所说的“分配”具有何种含义。在本例中，一种分配方式就是一个具有4个值的表，其中每个值都是从红、绿、蓝这3种颜色中任选其一。接下来要分别用字母R、G 和B 来表示这3种颜色。而当且仅当两个这样的表至少有一个位置不同时，我们称这两个表是不同的。
在这个房屋与颜色的例子中，可以为第一所房屋任选三种颜色之一。不管为第一所房屋选择了什么颜色，在粉刷第二所房屋时还是有这三种选择。因此粉刷前两所房屋的方式有9种，对应着9个不同的字母对，每个字母都是R、G 和B 这三者之一。类似地，对前两所房屋所具有的9种分配方式的每一种而言，都可以为第三所房屋在三种颜色中任选其一。这样一来，前三所房屋的粉刷方式就达到了9×3=27种。最后，这27种分配方式中对应的第四所房屋又都能在三种颜色中任选其一，因此总共有27×3=81种粉刷房屋的方式。
4.2.1　为分配计数的规则
可以对以上示例加以扩展。在一般情形下，有一列n个“项”，比如示例4.1中的房屋；还有一组k个“值”，如示例4.1中的颜色，可以给某个项指定这些值中的任一种。一种分配就是一个含有n个值的表(v1,v2,…,vn)。v1,v2,…,vn中的每一个都是从这k个值中任选其一。这种分配指定了vi 从v1到第i 项的值，其中i=1,2,…,n。
当有n个项，而且可以为每一项指定k个值之一时，就会有kn 种不同的分配。例如，在示例4.1中，一共有n=4项，也就是有4所房屋，而且有k=3个值，也就是有3种颜色。我们就可以计算出总共有81种不同的分配。请注意，就是34=81种。可以通过对n 的归纳证明这一一般规则。
命题 S(n)。为n个项中每一项分配k个值中的任一个，共有kn 种方式。
依据。依据为n=1的情况。如果只有一项，可以为它任选k个值中的一个。因为k1=k，所以依据得证。
归纳。假设命题S(n)为真，并考虑S(n+1)，也就是为n+1项分别分配k个值之一，共有kn+1种方式。可以将这种分配分解为给第一项选择值，以及针对第一个值的每种选择，为剩下的n项分配值。对每种这样的选择而言，根据归纳假设，剩下的n项有kn 种分配值的方式。所以总分配方式共有k×kn 种，也就是有kn+1种。因此我们证明了S(n+1)，完成了归纳步骤。
图4-2表示了当n+1=4且k=3时，即在示例4.1这个讨论4所房屋和3种颜色的具体例子中，对第一个值的选择以及相应的剩余项分配方式的选择。也就是说，在归纳假设中假定选择3种颜色之一粉刷3所房屋共有27种分配方式。
图 4-2　用3种颜色粉刷4所房屋的分配方式数
4.2.2　为位串计数
在计算机系统中，我们常遇到由0和1组成的串，而这些串往往用作对象的名称。例如，我们可能购买具有“64MB主内存”的计算机。每一个字节都有自己的名称，而这个名称是长度为26位的位序列，每一位要么是0，要么是1。这种由0和1组成的表示名称的串就叫作位串。
为什么对64MB的内存来说是26位呢？答案就源自分配计数问题。当我们计算长度为n的位串的数量时，可以将串中的位置视作“项”，而这些位置可能存放0或1这两个值中的一个。因为有两个值，所以有k=2，而为n个项分配二值之一的分配方式共有2n种。
如果n=26，即考虑长度为26的位串，就可能有226种位串。226的精确值为67 108 864。而按照计算机的语法，这个数字会被视为“6 400万”，虽然真实的数字显然要比这个值大上约5%。接下来的附注栏简要介绍了该主题，并试着解释了为2的乘方命名时涉及的一般规则。
K、M和2的乘方
将2的乘方转换成10的乘方有个实用的技巧。我们可以注意到，210，也就是1024，与1000是非常接近的。因此，230，也就是(210)3，或者说大概是10003，即10亿。那么，232=4×230，也就是约40亿。其实，计算机科学家通常都会认可210正好是1000的假设，并将210说成是1K，其中K表示kilo（千）。例如，我们可将215转换成32K，因为
215=25×210=32ד1000”
而我们将实际值为1 048 576的 220 称为1M，或者是1兆，而不是称为1000K或1024K。对 220到 229 这几个2的乘方数，我们会提取出 220 这个因子。因此， 226 就是 26×220 ，或者说是64兆。这正是 226 字节被称为64兆字节或64 MB的原因。
下表给出了多项10的乘方，以及与其近似相等的2的乘方。
103 或 210
106 或 220
109 或 230
1012 或 240
1015 或 250
本表格表明对超过 229 的2的乘方，我们分别会提取出 230 、 240 或是可以达到的2的任意整 十次方作为因子。不管用什么单位度量，剩下的2的乘方会在命名时加上giga-、tera-或peta-这 些前缀。例如， 243 字节就是8TB。
4.2.3　习题
1. 在下列情形中，分别有多少种粉刷方式?
(a) 3所房屋，每一所可从4种颜色中任选一种。
(b) 5所房屋，每一所可从5种颜色中任选一种。
(c) 2所房屋，每一所可从10种颜色中任选一种。
2. 假设计算机密码由8到10位字母和（或）数字组成。可能有多少种不同的密码？请记住，大写字母和小写字母是不同的。
3. * 考虑如图4-3所示的f函数。f可以返回多少种不同的值？
int f(int x)
if (x%2 == 0) n *= 2;
if (x%3 == 0) n *= 3;
if (x%5 == 0) n *= 5;
if (x%7 == 0) n *= 7;
if (x%11 == 0) n *= 11;
if (x%13 == 0) n *= 13;
if (x%17 == 0) n *= 17;
if (x%19 == 0) n *= 19;
图 4-3　f函数
4. 在“好莱坞广场”游戏中，X和O可能以任意组合被放置在井字棋棋盘（一个3×3的矩阵）9个格子的任意一个中（即与普通井字棋玩法不同的是，这里的X和O不必要交替摆放，所以，打个比方，所有的格子都可以放上X）。方阵也可能为空，也就是说，既不含X，也没有O。那么有多少种不同的摆放方法呢？
5. 用10个数字可以组成多少种长度为n的串？其中某个数字可能出现任意次，也可能根本不出现。
6. 用26个小写字母可以组成多少种长度为n的串？其中某个字母可以出现任意次，也可能根本不出现。
7. 根据上文附注栏中所述的规则，将以下内容转换成K、M、G、T或P：(a) 213 (b) 217 (c) 224 (d) 238 (e) 245 (f) 259。
8. * 将以下10的乘方转换成近似的2的乘方：(a) 1012 (b) 1018 (c) 1099 。
4.3　为排列计数
本节中我们将解决另一个基础的计数问题：将给定的n个不同对象排成一列，可以有多少种不同的排列方式？这种排序称为这些对象的排列。我们将用Π(n)表示n个对象的排列数。
关于为排列计数在计算机科学中的重要性，我们来举例说明。假设要为给定的n个对象a1、a2、…、an排序。如果对这些对象一无所知，那么任何次序都可能是正确的排序次序，因此排序可能的结果数就是Π(n)，也就是n个对象的排列数。我们很快就会看到，这一结果有助于证实：通用的排序算法所需的时间与n logn成正比，并因此可证实3.10节中运行时间为O(n logn)的归并排序算法会快上某个常数因子倍。
排列计数规则还有很多其他应用。例如，我们将在后面的小节中看到的，它在组合与概率这样更为复杂的计数问题中也分量十足。
为了直观，我们列举一下微量对象的排列。首先，显然有Π(1)=1。也就是说，如果只有一个对象A，就只有一种次序A。
然后考虑有两个对象A 和B 的情况。可以从两个对象中任选其一排列在第一位，而将另一个对象排列在第二位，因此有两种次序：AB 和BA。所以Π(2)=2×1=2 。
接着看看有3个对象A、B 和C 的情况。可以从三者中任选其一排在首位。先考虑选择A 排在第一位的情况，这时候剩下B 和C 这两个对象，它们可以按两个对象的两种次序之一分布，从而完成这一排列。因此可以看出，由A 开头的排列有两种，即ABC 和ACB。
类似地，如果以B 开头，也有两种方式完成这一序列，对应为剩下的对象A 和C 排序的两种方式，因此有序列BAC 和BCA。最后，如果以C 开头，就可以用两种方式为剩下的对象A 和B 排序，从而得到序列CAB 和CBA。ABC、ACB、BAC、BCA、CAB 和CBA 这6个序列就是3个元素可能排成的所有次序了。也就是说，，Π(3)=3×2×1=6。
接下来考虑一下4个对象A、B、C 和D 可以形成多少排列。如果选择A 排在首位，那么跟在A之后的对象B、C 和D 可以按照6种次序中的任意一种排列。类似地，如果将B 排在第一位，那么剩下的A、C 和D 也能按6种次序排列。现在一般模式应该明了了。可以从4个元素中任选一个排在第一位，而对每种选择，都可以按照Π(3)=6种可能方式中的任意一种排列剩余元素。请注意，3个对象的排列数并不取决于这3个元素到底是什么。由此可以得出结论：4个对象的排列数等于4乘以3个对象的排列数。
一般而言，对任意n≥1，有Π(n+1)=(n+1)Π(n)　　　　　　(4.1)
也就是说，要为n+1个对象的排列计数，可以从n+1个对象中任选一个排在首位。然后剩下的n个对象可以有Π(n)种排列方式，如图4-4所示。在我们的例子中，n+1=4，于是有Π(4)=4×Π(3)=4×6=24 。
图 4-4　n+1个对象的排列
4.3.1　排列公式
等式(4.1)就是2.5节介绍的阶乘函数定义中的归纳步骤。因此不用为Π(n)等于n!感到惊讶。我们可以通过简单的归纳证明这种等价性。
命题 S(n)。对所有的n≥1，有Π(n)=n!。
依据。对n=1，S(1)表示1个对象有1种排列。我们在示例4.2中已经看出这一点了。
归纳。假设Π(n)=n!。那么要证明的S(n+1)就是Π(n+1)=(n+1)!。由等式(4.1)，有
Π(n+1)=(n+1)×Π(n)
而根据归纳假设，Π(n)=n!。因此，Π(n+1)=(n+1)×n!。因为
n!=n×(n-1)×…×1
所以一定有(n+1)×n!=(n+1)×n×(n-1)×…×1。而后者的积就是(n+1)!，这就证明了S(n+1)为真。
根据公式Π(n)=n!，可以得出结论：4个对象的排列数是4!=4×3×2×1=24，正如我们在上面所见的。再举个例子，7个对象的排列数就是7!=5040。
4.3.2　排序要花多久
该排列计数公式有个有趣的用途，就是可用来证明，要为n个元素排序，排序算法至少会花上与n logn成正比的某段时间，除非在排序过程中利用到这些元素的某些特殊属性。例如，在后文附注栏有关特例排序算法的介绍中，可以注意到，如果编写只处理较小整数的排序算法，就可以使运行时间比与n logn成正比的值更少。
不过，如果某个排序算法可以处理任意种类的数据，那么只要这些数据可以通过某种“小于”关系进行比较，该算法确定合适次序的唯一方式就是考量两个元素中的一个是否小于另一个。如果某种排序算法对待排序元素的唯一操作是比较二者以确定它们的相对次序，那么这种算法就可称为通用排序算法（general-purpose sorting algorithm）。例如，第2章中介绍的选择排序和归并排序都是这样作出决定的。即便编写的程序是用来处理整数数据的，也可以将其编写得更具一般性，只要将图2-2第(4)行中
if (A[j] & A[small])
这样的比较替换成诸如
if (lessThan(A[j], A[small]))
这类调用布尔值函数的测试即可。
假设有n个不同的元素有待排序。答案（也就是正确的排序次序）可能是这些元素形成的n!种排列中的任意一种。如果用于为任意类型的元素排序的算法能正常工作，它就一定能区分这n!种不同的可能答案。
考虑该算法进行的第一次元素比较，假设是
lessThan(X,Y)
对这n!种可能的排序次序而言，X 要么小于Y，要么不小于Y。因此，这n!种可能的次序会被划分为两组，分别是第一次测试的答案为“是”的组，以及答案为“否”的组。
这两组中的一组必须至少具有n!/2个成员，因为如果两个组的成员都不足n!/2个，总的次序数就少于n!/2+n!/2个，也就是少于n!种次序。而这一次序数量的上限就限制了我们刚好有n!种次序。
现在考虑第二个测试，假设对X 和Y 进行比较的结果是得出如下结论：两组可能的次序中较大的那组会剩下（如果这两组一样大则任取一组）。也就是说，至少会剩余n!/2种次序必须由算法来区分。第二次比较同样有两种可能的结果，而且剩余的次序中至少有一半会与这些结果之一相同。因此，我们会发现，至少有n!/4种次序与前两次测试的结果一致。
可以重复这一论证，直到算法确定正确的排序次序为止。在每一步中，只要将重点放在含有较多一致可能次序的结果上，就至少会留下一半上一步中得到的可能次序。因此，可以看到这样一系列的测试和结果：在第i次测试后，至少有n!/2i种次序与这些结果相一致。
因为直到每个测试和结果序列最多与一个排序次序一致才会完成排序，所以在完成排序前所进行测试的次数t 要满足
n!/2t≤1　　　　　　(4.2)
如果对(4.2)式的两边同时取以2为底的对数，就得到log2n!-t≤0，也就是
t≥log2(n!)
我们将看到log2(n!)大约是n log2n。不过首先要看一个分割可能次序的示例。
考虑一下图2-2所示的选择排序算法在为给定的3个元素（a,b,c）排序时是如何作出判定的。第一次比较发生在a 和b 之间，如图4-5中的顶端所示，其中方框中表示了进行任何测试前，6种可能的次序全部是一致的。在测试后，abc、acb 和cab 这些次序与结果为“是”（即a& b）的情况一致，而bac、bca 和cab 这些次序与相反的结果（也就是b>a）一致。我们再次在方框中展示了每种情况中的一致序（consistentorder）。
在图2-2所示的算法中，较小元素的下标成了变量small的值。因此，接下来要将c 与a 和b 中的较小者进行比较。请注意，接下来要进行何种测试取决于上一次测试的结果。
在进行第二次判定后，3个元素中最小的那个会被移动到数组的第一个位置，而第三次比较则会确定剩下的两个元素中哪个更大。第三次比较是该算法在为3个元素排序时所要进行的最后一次比较。正如我们在图4-5的底部看到的，有时候判定的结果是确定的。例如，如果已经得到a& b而且c>b，那么c 就是最小的元素，而且最后一次对a 和b 的比较会得出a更小的结论。
图 4-5　对3个元素进行选择排序的判定树
在本示例中，所有路径都包含3次判定，而且最后至多存在一种一致序，就是正确的排序次序。不含一致序的两条路径从未出现。(4.2)式说明测试次数t一定至少为log23!，即log26。由于6大于22且小于23，所以可知log26大于2小于3。所以，为3个元素排序的任意算法至少有某个结果序列必须进行3次测试。因为选择排序只需为3个元素进行3次测试，所以处理3个元素时，它最不济也至少与其他算法一样好。当然，随着元素数量不断变多，选择排序就不那么好了，因为它是种O(n2)的排序算法，而且还存在更佳的算法，比如归并排序。
现在必须要估算log2n!有多大。因为n!是从1到n这n个整数的积，它肯定要比从n/2到n这个整数的积大。这个整数的积又至少与n/2个n/2的积，也就是(n/2)n/2一样大。因此，log2n!至少是log2((n/2)n/2)，即，也就是
对较大的n来说，这一公式约等于(n log2n)/2。
更细致的分析将表明常数因子1/2在这里并非必要。也就是说，log2n!非常接近n log2n，而非更接近它的一半。
线性时间的专用排序算法
如果对排序算法可以处理的输入加以限制，就可以在一个步骤中将可能的次序分为2个以上的部分，因此会让运行时间少于与n logn成正比的时间。下面讲一个简单例子，如果输入是n个从0到2n-1之间的不同整数，它就能起作用。
for (i = 0; i
printf("%d\n", i);
假设输入为长度为n 的数组a。在第(1)行和第(2)行，我们将长度为2n 的数组count初始化为0。接着，在第(3)行和第(4)行中，若x 为第i 个输入元素a[i]的值，则为x的计数加上1。在最后3行代码中，要打印出count[i]为正的各个整数i。因此，要打印那些在输入中至少出现过一次的元素，而之前假设了输入中各元素都是不同的，所以这段代码会将所有的输入元素按照从小到大的顺序打印出来。
分析该算法运行时间很容易。第(1)行和第(2)行是一个会迭代2n次的循环，而且其循环体的运行时间为O(1)。因此，该循环的运行时间为O(n)。同理，第(3)行和第(4)行的循环运行时间也是O(n)，只不过它的迭代次数是n。最后，第(5)行至第(7)行所示循环的循环体运行时间为O(n)，而它会迭代2n次。因此，这3个循环的运行时间均为O(n)，而整个排序算法的运行时间同样是O(n)。请注意，如果给定的输入没有为该算法进行过处理，比如输入中含有超出从0到2n-1范围的整数，那么上面的程序就无法正确排序。
我们只是证实了任意通用排序算法都一定有某些能让它们进行n log2n或更多次比较的输入。因此，任意通用排序算法在最坏的情况下肯定至少要花上与n logn成正比的时间。其实，可以证明，这一点同样适用于“平均的”输入。也就是说，通用排序算法处理所有输入平均所花的时间一定至少与n logn成正比。因此，归并排序基本上就是我们能做的最佳算法了，因为它处理所有输入都有着这样的大O运行时间。
4.3.3　习题
1. 假设已经为棒球队选择了9名队员。
(a) 可能存在多少种击球次序？
(b) 如果投手必须最后击球，那么可能有多少击球次序？
2. 如果要为4个元素排序，那么图2-2中的选择排序算法要进行多少次比较？这是不是可以达到的最优数字？给出该情况下判定树（具有如图4-5所示样式）最上面的3层。
3. 2.8节介绍的归并排序算法在处理4个元素时要进行多少次比较？这是否为可达到的最优数字？给出该情况下判定树（具有如图4-5所示样式）最上面的3层。
4. * 将n个值分配给n个项的数目多，还是n+1个项的排列数多？请注意：对不同的n来说，答案可能不同。
5. * 将n/2个值分配给n个项的数目是否多于n个项的排列数？
6. ** 说明如何在O(n)时间内为范围在0到n2-1之间的n个整数排序。
4.4　有序选择
有时候我们会希望只从集合中选出某些项，并为它们排定顺序。这里将4.3节中介绍过的为排列计数的函数Π(n)一般化为双参数的函数Π(n,m)，用该函数表示从n个项中选出m项排定次序的方法数，不过对未选定的项来说没有次序可言。因此Π(n)=Π(n,n)。
赛马比赛会为前三名完成比赛的赛马颁奖。假设有10匹马参赛，那么冠亚季军的排列情况共有多少种呢？
显然，10匹马中的任意一匹都可能赢得比赛。如果给定了获得冠军的马匹，那么剩下的9匹马可以任意排序。因此前两名马匹的选择共有10×9=90种。对每种选择而言，都会剩下8匹赛马，其中任意一匹都可能获得季军。因此，冠亚季军的选择方式共有90×8=720种。图4-6展示了所有可能的选择，重点突出了首先选择3号之后选择1号的情况。
图 4-6　从10项有序地选出3项的情况
4.4.1　无放回选择的一般规则
现在来推导一下Π(n,m)的公式。顺着示例4.5的思路，可知第一次选择时有n种选择。不管第一次作出了怎样的选择，都会剩下n-1个元素有待选择。因此，第二次选择有n-1种不同的方式。前两次选择总共有n(n-1)种方式。类似地，进行第三次选择时还剩n-2个未选取的项，所以第三次选择共有n-2种不同的方式。因此，前三次选择总共可以有n(n-1)(n-2)种方式。
继续用这种方式处理，直到作出m次选择。每次选择都比之前一次的选择少一项。结论就是，从n个项中不放回但有次序地选出m个项，总共有
Π(n,m)=n(n-1)(n-2)…(n-m+1)　　　　　　(4.3)
种不同的方式。也就是说，表达式(4.3)是从n开始依次倒数的m个整数的积。
还可以将(4.3)式写为n!/(n-m)!。也就是
分母是从1到n-m这些整数的积。而分子则是从1到n这些整数的积。因为分子和分母中后n-m个因子(n-m)(n-m-1)…(1)是相同的，所以将这些项约去，就得到
这一公式与(4.3)式是相同的，这样就证实了Π(n,m)=n!/(n-m)!。
考虑一下示例4.5中的情况，其中n=10且m=3。不难看出，Π(10,3)=10×9×8=720。(4.3)式表示Π(10,3)=10!/7!，或者说是
从1到7这些因数同时出现在分子和分母中，因此要约去这些因数。结果就得到8、9、10这三个数字的积，就是10×9×8，正如我们在示例4.5中看到的那样。
有放回选择和无放回选择
示例4.5中考虑的问题与4.2节考虑的分配问题只有细微的差别。如果用房屋和颜色来表示，就可以将选出前三名完成比赛的赛马视为将10匹马（颜色）分配给三个完赛排位（房屋）。唯一的区别是，将多所房屋粉刷成相同颜色是可以的，而说一匹赛马同时获得冠军和季军则很荒唐。因此，用10种颜色之一粉刷3所房屋的方法共有103或者说是10×10×10种，而从10匹赛马中选择前三名完成比赛的赛马则有10×9×8种方法。
有时候我们会将4.2节进行的这种选择称为有放回选择。也就是说，当为一所房屋选择一种颜色（比如说是红色）后，会将红色“放回”可供选择的颜色池中，然后可以继续为其他房屋再次选择红色。
另一方面，我们在示例4.5中讨论的有序选择被称为无放回选择。这种情况下，如果赛马“硬面包”被选作冠军，那么它就不能被放回含有亚军和季军的马匹池了。类似地，如果赛马“秘书处”被选为第二名，那么它也就不可能再成为获得季军的马匹了。
4.4.2　习题
1. 从26个字母中选出m个字母组成序列，如果不允许同一字母出现一次以上，那么有多少种不同的组合方式？分别计算m=3及m=5的情况。
2. 在一个有200名学生的班级中，我们希望选出一位会长、一位副会长、一位秘书和一位财务主管。选择这4位干部的方式共有多少种？
3. 计算如下阶乘之商：(a)100!/97!(b)200!/195!。
4. “珠玑妙算”（Mastermind）这个游戏要求玩家选择一个由一列4个珠子组成的“密码”，每个珠子都可能是红、绿、蓝、黄、白和黑这6种颜色中的一种。
(a) 总共有多少不同的密码？
(b*) 有两个或多个珠子颜色相同的密码有多少种？提示：这个量是(a)小题的答案与另一个易于计算的量之间的差。
(c) 不含红色珠子的密码有多少种？
(d*) 不含红色珠子而且至少有两个珠子颜色相同的密码有多少种？
5. * 通过对n 的归纳证明，对1和n 之间的任意m，有Π(n,m)=n!/(n-m)!。
6. * 通过对a-b 的归纳证明，a!/b!=a(a-1)(a-2)…(b+1)。
请注意，一般而言，只要b& a，a!/b!就是从b+1到a 这些整数的积。通过计算
a×(a-1)×…×(b+1)
来计算阶乘之商，要比分别求出每个阶乘的值然后相除更容易，特别是在b不比a 小很多的情况下。
4.5　无序选择
在很多情况下，我们希望计算出从一组项中进行选择到底有多少种方法，而其中所选项的顺序倒是无关紧要。按照4.4节中赛马结果示例的说法，我们可能想知道前三名完成比赛的赛马是哪三匹，但不关心到底哪匹马赢得了哪个名次。换句话说，就是想知道从n匹赛马中选出3匹作为前三名完成比赛的马匹，方法有多少种。
再次假设n=10。我们从示例4.5中得知，选择3匹赛马，假设说是A、B和C，分别作为冠亚季军的方式共有720种。然而，我们现在不关心这3匹马完成比赛的具体次序，只是想知道A、B和C这3匹马以某种次序获得了前三名。因此，我们将通过6种不同的方式得到答案“A、B和C是最好的3匹赛马”，分别对应3匹马在前三名中6种不同的排位。可知刚好存在6种方法，因为给3个项排序的方法为Π(3)=3!=6种。如果还有疑问的话，可以参考图4-7所示的这6种方法。
图 4-7　3匹马完成比赛的6种顺序
对A、B 和C 这3匹马来说成立的情况，对任意一组3匹马来说都成立。在为从10匹马中有序选择出3匹马的情况计数时，每一个3匹马构成的组都会刚好按照它们可能形成的所有次序出现6次。因此，如果只需要计算可能为前三名的3匹马的组合数，就还要在Π(10，3)的基础上除以6。因此，从10匹马中选出3匹作为前三名的马共有720/6=120种不同组合。
再来考虑一下扑克牌型的数量。在扑克牌游戏中，每名玩家都会分到从52张牌中发出的5张。这里不用考虑分到的5张牌究竟是什么顺序，只关心拿到的这5张牌到底是哪5张。要计算分到的5张牌可能有多少种情况，可以先从计算Π(52，5)开始，也就是从52个对象中有序选择5个对象的情况总数。这一数字是52!/(52-5)!，就是52!/47!，或者说是50×49×48=311 875 200。
不过，就像示例4.7中跑得最快的3匹马总共可能以3!=6种次序出现那样，任意一组5张牌都可能以Π(5)=5!=120种不同的次序出现。因此，要在不考虑选择次序的情况下考虑可能构成的牌型，就必须用有序选择的次数除以120。结果是共有311 875 200/120=2 598 960种不同的牌型。
4.5.1　为组合计数
现在要将示例4.7和示例4.8中介绍的情况一般化，以得出在不考虑选择顺序的情况下计算从n项中选出m项的方法数的公式。这一函数通常可写为，并说成是“n选m”或是“从n个元素中选取m个元素的组合数”。要计算，首先要计算Π(n,m)=n!/(n-m)!，也就是从n个事物中有序选择出m个的方法数。然后要根据选出的这m项来为这些有序选择分组。因为这m项可以有Π(m)=m!种不同的次序，所以这些分组中各含m!个成员。要得到无序选择的数目，就必须要用有序选择的数目除以m!，也就是
　　　　　　(4.4)
回顾一下示例4.8，它用到了公式(4.4)，其中n=52Π，m=5。于是有。如果将47!与52!中的后47个因数约去，并展开5!，就可以写为
进行简化，就得到 。
4.5.2　n 选m 的递归定义
如果递归地考虑从n项中选出m项的方法数，就可以得出计算的递归算法。
依据。对任意n≥1，有。也就是说，从n项中选择0项只有一种方式。此外，，也就是说，从n项中选择n项的唯一方法就是将它们都选上。
归纳。如果0& m& n，那么。也就是说，如果想从n项中选出m项，可以用以下两种方法中的任一种。
1. 不选取第一个元素，接着从剩下的n-1个元素中选取m个。这项表示的就是这种情况下可能的选择方法数。
2. 选取第一个元素，然后从剩下的n-1个元素中选取m-1个元素。这项表示的就是这种情况下可能的选择方法数。
顺便提一句，尽管归纳部分的概念应该很明确（先从全选或全不选的最简单情况开始，进而处理选择某些元素的更复杂的情况），不过还是要谨慎起见，说明是对什么量进行归纳。看待这一归纳的方式之一是，将其视为对m和n-m二者中较小的那个与n的积进行完全归纳。那么当该积为0，而且归纳是针对该积的较大值进行时，就会发生依据的情况。我们还必须为归纳过程核实，当0& m& n时，n×min(m,n-m)总大于(n-1)×min(m,n-m-1)以及(n-1)×min(m-1,n-m)。这一验证过程将留作本节的习题。
这种递归关系通常是用帕斯卡三角形（Pascal's triangle）1表示的，如图4-8所示，其中两条边全部由1构成（表示依据），而三角形中每个内部条目都是它左上角和右上角相邻条目之和。那么将作为第(n+1)行的第(m+1)个条目被读取。
1又称杨辉三角或贾宪三角。——译者注
图 4-8　帕斯卡三角形的前几行
考虑一下n=4且m=2的情况。我们在图4-8第5行的第3个条目处找到了 的值。该条目为6，而很容易验证。
通过公式(4.4)或是上述递归这两种方法计算，计算出的自然是相同的值。可以通过诉诸物理推理（physical reasoning）来证实这一点。两种方法计算的都是从n 项中无序选择m 项的方法数，所以一定会得出相同的值。不过，还可以通过对n 的归纳证明这两种方式的等价性。在这里将该证明过程留作本节的习题。
4.5.3　计算的算法的运行时间
正如在示例4.9中所见，当我们使用公式(4.4)计算时，可以约去分母中的(n-m)!和分子中n!的后n-m个因数，将表示为
　　　　　　(4.5)
如果m 比n 小，那么使用上述公式进行计算要比用公式(4.4)计算更快。大体上讲，图4-9中的C语言代码段就是用来完成这一工作的。
第(1)行将c 初始化为1，c 就成为了结果——。第(2)行和第(3)行会给c 乘上从n-m+1到n的各个整数。然后，第(4)行和第(5)行会依次从c 除去从2到m 的各个整数。因此，图4-9就实现了(4.5)式中的公式。
for (i = i & n-m; i--)
for (i = 2; i &= i++)
图 4-9　计算的代码
要计算图4-9的运行时间，只要注意到第(2)～(3)行及第(4)～(5)行这两个循环，每个循环都会迭代m次，而且循环体的运行时间都是O(1)。因此，运行时间是O(m)。
在m接近n而n-m很小的情况下，可以交换m和n-m的角色。也就是说，可以约去n!和m!的因数，得到n(n-1)…(m+1)，并将其除以(n-m)!。该方法给出了(4.5)所示公式的另一种形式，即
　　　　　　(4.6)
同样，存在与图4-9类似的代码段来实现公式(4.6)，而且所花的时间为O(n-m)。因为要定义就一定有n-m和m不大于n，所以不管是哪种方式，O(n)都是运行时间的边界。此外，在m接近0或者接近n 时，两种方法中更优方法的运行时间都要大大小于O(n)。
不过，图4-9有个重大缺陷。它先要计算若干整数的积，然后再将其除以相同数量的整数。因为普通的计算机运算只能处理有限大小的整数（通常，一个整数最大可以达到约20亿），所以图4-9第(3)行计算中间结果的过程可能有溢出整数大小限制的风险。即使是在的值足够小，可以在某计算机中表示出来的情况下，也还是可能出现这种情况。
更好的方式是让乘法和除法交替进行。首先乘上n，然后除以m。乘上n-1，再除以m-1，以此类推。这种方法的问题在于，我们没理由相信每一阶段的计算结果都是整数。例如，在示例4.9中，首先要乘上52并除以5，这个结果就已然不是整数了。因此，在进行任何计算前都需要转换为浮点数。在这里将这一修改留作本节的习题。
让一定得出整数的公式
要看出为什么(4.4)、(4.5)和(4.6)这几个式子中多个因数的商一定是整数可能不容易。唯一的简单论证就是诉诸物理推理。这些公式都是计算从n个事物中选取m个的方法数，而这个数字一定是某个整数。
不借助这些公式的物理意义，而从整数的属性来论证这一事实，要难上很多。其实可以通过仔细分析分子和分母中各质数因子数来证明这一事实。拿示例4.9中的表达式当例子。其中分母中有5这个因数，而分子中有5个因数，由于这些因数是连续的，可知其中必有一个能被5整除，而它正好是中间的那个因数——50。因此，分母中的5肯定会被约去。
现在来考虑计算的递归算法。可以通过图4-10所示的简单递归函数来实现这一算法。
图4-10中的函数效率不高，因为它调用choose的次数会呈指数级增长。原因就在于当使用n作为首个参数调用该函数时，往往会在第(6)行用n-1作为首个参数进行两次递归调用。因此，可以预见，当n 增加1时，调用的次数就会翻倍。而且递归调用的确切次数是很难计算的。原因在于第(4)行和第(5)行的依据情况不仅适用于n=1的情况，而对更大的n，会提供值为0或n 的m。
下面要证明一个简单但稍显悲观的上界。设T (n)是当首个参数为n 时图4-10所示程序段的运行时间。可以直接证明T(n)是O(2n)。假设a是第(1)行到第(5)行，加上第(6)行涉及调用与返回的部分（不含递归调用本身所花的时间）的总运行时间。然后就可以通过对n 的归纳证明下列命题。
/* 对0 &= m &= n，计算从n 个元素中选择m 个的方法数 */
int choose(int n, int m)
if (m & 0 || m & n) {/* 错误的条件 */
printf("invalid input\n");
else if (m == 0 || m == n) /* 依据情况 */
else /* 归纳 */
return (choose(n-1, m-1) + choose(n-1, m));
图 4-10　计算的递归函数
命题 S(n)。如果用第一个参数n以及在0和n之间的第二个参数m调用choose，那么该调用的运行时间T(n)至多为a(2n-1)。
依据。 n=1。那么一定有m=0或m=1=n。因此，依据情况适用于第(4)行和第(5)行，而且没有进行递归调用。第(1)行到第(5)行的时间都包含在a中，因为S(1)是说T(1)至多为a(21-1)=a。
归纳。假设S(n)成立，也就是有T(n)≤a(2n+1)。要证明S(n+1)成立，假设要以n+1为首个参数调用choose。那么图4-10所示程序段花的时间就是a加上第(6)行两次递归调用的时间。根据归纳假设，每次调用花费的时间至多为(2n-1)。因此，消耗的总时间最多是：
a+2a(2n-1)=a(1+2n+1-2)=a(2n+1-1)
这一计算过程就证明了S(n+1)成立，并证明了归纳步骤。
因此证明了T(n)≤a(2n-1)。舍去常数因子及低阶项，就可以得出T(n)是O(2n)的结论。
奇怪的是，尽管在第3章的分析中，很容易就证明了运行时间的平滑紧上界，但T(n)上的边界O(2n)虽平滑却不紧凑。合适的平滑紧上界要稍小一些——。要证明这一事实相当困难，不过在这里要留一个更为简单的事实作为习题来证明，就是图4-10所示程序段的运行时间与它返回的值成比例。要看到图4-10中的递归算法，效率要比图4-9中的算法低得多。这是一个递归严重不靠谱的例子。
4.5.4　函数的图像
对某个固定的值n 而言，m 的函数有着不少有意思的属性。对于值比较大的n 来说，如图4-11所示，其图像为一条钟形的曲线。我们很容易看出函数图像是关于中点n/2所在轴线对称的，运用声明的公式(4.4)很容易证实这一点。
最大高度处于中心位置，也就是，大约是。例如，若n=10，这一公式可以得出258.37，而。
该曲线的“厚部”是中点两边各约的范围。例如，如果n=10 000，那么对处在之间的m，就接近最大值。而对这个范围之外的m来说，的值会下降得特别迅速。
图 4-11　n 为固定值的函数
4.5.5　二项式系数
函数除了可以用来计数外，还能提供二项式系数。在展开二项式的乘方（比如(x+y)n）时，就会看到这些数字。
在展开(x+y)n时，会得到2n个项，其中每一项都是xmyn-m这样的形式（m是0到n之间的某个整数）。也就是说，对每个因式x+y，都可能从x 和y 中任选其一作为某个特定项的因子。展开式中xmyn-m的系数是由m个x 和其余n+m个y 组成的项的数量。
考虑一下n=4的情况，也就是看看(x+y)(x+y)(x+y)(x+y)的积。
总共有16项，其中只有1项是x4y0（也就是x4）。如果从4个因式中都选出x，就能得到这一项。另一方面，有4项是x3y，对应的情况是从4个因式的任意一个中选出y，再从其余3个因式中选出x。对称地，有1项是y4，有4项是xy3。
那么有多少项是x2y2呢？如果从两个因式中选取x并从其余两个中选取y，就能得到这样一项。因此，必须要计算从4个因式中选择两个因子的方法数。因为选择两个因子的顺序是不产生影响的，所以这个数字就是。因此，有6项是x2y2。完整的展开式就是
(x+y)4=x4+4x3y+6x2y2+4xy3+y4
请注意等式右侧各项的系数，(1,4,6,4,1)，正好就是图4-8中帕斯卡三角形的一行。我们会看到，这并非巧合。
示例4.11中用于计算x2y2系数的概念可以推广开来。(x+y)n展开式中的项xmyn-m的系数为。原因在于，只要从n个因式中选出m个x并选出n-m个y，就可以得到xmyn-m这一项。从n个因式中选出m个因子的方式有种。
在二项式系数和函数之间还有一种有趣的关系。我们已经看出
令x=y=1，那么有(x+y)n=2n。x和y的所有乘方都是1，所以上述等式就成了
换句话说，对某个特定的n而言，所有二项式系数的和就是2n。特别要说的是，每个系数都小于2n。图4-11就暗示了，对接近n/2的m来说，和2n 特别接近。由于在图4-11中曲线下方的区域表示2n，因此能看出为什么只有接近中点的一些值会比较大。
4.5.6　习题
1. 计算以下各值：(a) ；(b) ；(c) ；(d) 。
2. 从26个小写字母中选出5个不同字母的方法共有多少种？
3. 如下系数各为多少?
(a) (x+y)7的展开式中x3y4的系数；
(b) (x+y)8的展开式中x5y3的系数。
4. * 在Real Security公司，计算机密码必须由4位数字（10选4）和6个字母（52选6）组成，字母和数字都可以重复。总共可能有多少种不同的密码组合？提示：首先考虑选择4个存放数字的位置共有多少种方法。
5. * 5个字母组成的双元音序列有多少种？
6. 重新编写图4-9所示的程序片段，从而利用n-m小于n的情况。
7. 重新编写图4-9所示的程序片段，并将其转换成浮点数乘除交替的算法。
8. 证明：如果0≤m≤n，那么。
(a) 借助的含义。
(b) 利用(4.4)式。
9. * 通过对n的归纳，证明的递归定义正确地定义了等于n!/((n-m)!×m!)。
10. ** 通过对n的归纳，证明图4-10中递归函数choose(n,m)的运行时间最多是，其中c为某个常数。
11. * 证明：当0& m& n时，n×min(m,n-m)　总是大于(n-1)×min(m,n-m-1)　和(n-1)×min(m-1,n-m)。
4.6　相同项的次序
在本节中，要处理的是这样一些选择问题，其中含有一些相同项，但不同项出现的次序很重要。而在接下来的4.7节中，则要解决一类类似的选择问题，即有一些相同项，而且项的次序无关紧要。
构词（anagram）猜谜游戏会给出一列字母，让玩家重新排列字母以构成单词。如果拥有含规范单词的字典，并能生成所有可能的字母序列，就可以通过计算机解决该问题。第10章会介绍判定给定字母序列是否处于字典中的有效方法。不过现在要考虑的是组合问题，可能首先要确定有多少单词需要用字典验证其确实存在。
对有些构词来说，计数很简单。假设有abenst 6个字母，可能会有Π(6)=6!=720种不同的次序，其中之一便是absent，也就是该谜题的“解答”。
不过，构词游戏通常会含有重复的字母。考虑一下谜题eilltt。这些字母就不能构成720种不同的序列。例如，交换两个字母t的位置似乎并不能让单词发生变化。
假设对两个t和两个l加以标记以区分这些字母，分别将其记为t1、t2、l1和l2。被标记的字母可能有720种次序。然而，这些标记过的l仅在位置上有区别，诸如l2it2t1l1e和l1it2t1l2e就并不是真的有区别。因为所有720种次序可以平分为两组，这两组的区别只在于l的下标，所以可以证明：如果将字母串的数量除以2，这些l其实都是相同的。
类似地，在字符串中只有字母t带标记时，可以将只有t的下标不同的字符串配对。例如，lit1t2le和lit2t1le就是一对。因此，如果再将数目除以2，就可以得到将t和l的标记删除后不同构词串的数量。该数字为360/2=180。即使用eilltt共有180种不同的构词方法。
我们可以将图4-12中的概念一般化为有n个项而且这些项被分为k 组的情形。各组中的成员都是相同的，而不同组的成员则是不同的。在这里假设mi 是第i 组中的成员项，其中i =1,2,…,k。
重新考虑示例4.12中用eilltt构词的问题。其中共有6项，也就是说n=6。而分组的数量k 为4，因为有4个不同的字母。这4组中有两组含有一个成员（e 和 i），而另两组则含两个成员。因此可以取i1=i2=1，i3=i4=2。
如果为这些项加上标记，以使同一组中的成员有所不同，那么会有n!种不同的次序。不过，若第一组中有i1个成员，那么这些标记过的项可能会以i1!种不同的次序出现。因此，在从第一组的项上移除标记时，我们要将这些次序分成大小同为i1!的集合。因此必须将次序数除以i1!，从而得到从第1组删除标记后的次序数。
类似地，依次从各组中删除标记需要将不同次序的数量除以i2!、除以i3!，等等。对那些值为1的ij!来说，就是除以1!=1，因此没有任何影响。不过，对那些所含项数大于1的分组来说，我们必须除以分组大小的阶乘，这就是示例4.12中的情况。有两组中包含1个以上的元素，而每组的大小都是2，所以就要除以2!两次。可以通过对k的归纳证明该一般规则。
命题 S(k)。如果有n个项，并且分别被分为大小为i1、i2、…、ik的k个组，同一组中的项是相同的，而不同组中的项是不同的，那么这n个项能形成的不同次序的数目为
　　　　　　(4.7)
依据。如果k=1，那么只有一组无区别的项，不管n有多大都只有一种次序。如果k=1，那么i1一定为n，而(4.7)式就变成了n!/n!，也就是1。因此，S(1)成立。
归纳。假设S(k)为真，并考虑有k+1个分组时的情况。设最后一组中有m=ik+1个成员。这些项将会出现在m个位置，而且可以有种不同的方式来选择这些位置。一旦选定了m个位置，把最后一组中的哪一项放在这些位置都没关系了，因为这些项都是没有区别的。
在为最后一组选择了位置后，还剩n-m个位置来容纳其余k个组。归纳假设适用，并且表明最后一组的每种位置选择都对应着其余位置中其余元素的种不同次序。该式与(4.7)式相比，只是将(4.7)式中n的位置替换成了n-m，因为只剩n-m项有待放置了。因此k+1组项的次序总数为
　　　　　　(4.8)
如果将(4.8)中的替换成等价的n!((n-m)!m!)，就得到
　　　　　　(4.9)
可以从(4.8)式的分子和分母中约去(n-m)!。此外，请记住m是ik+1，是第k+1组中的成员的数目。因此可得到次序数为
这正是S(k+1)所给出的式子。
一位探险家带了两个星期的口粮，其中包括4罐金枪鱼、7罐午餐肉以及3罐黄豆罐头。如果他每天打开一罐罐头，那么他消耗这些口粮的次序共有多少种？这里的14项分成了分别具有4、7和3个相同项的3组。按照(4.7)式，其中n=14，k=3，i1=4，i2=7，i3=3。因此他消耗口粮的次序数为
先从分母中的7!开始，可以约去分子14!中最后7个因数。因此就得到
继续约去分子和分母中的因数，就可以得到结果为120 120。也就是说，消耗这些口粮的方法有逾10万种。可惜每一种听起来都让人没什么胃口。
1. 计算以下单词的字母构词的数量：(a) error；(b) street；(c) allele；(d) Mississippi。
2. 将下列水果排成一线共有多少种方法？
(a) 3个苹果、4个梨和5根香蕉；
(b) 2个苹果、6个梨、3根香蕉和2颗李子。
3. * 将白王、黑王、2个白骑士和1个黑车摆在棋盘上，共有多少种摆法？
4. * 100个人参与到一场彩票游戏中。其中一人可赢得千元大奖，还有5人可以得到50美元储蓄基金的安慰奖。那么总共可能有多少种不同的获奖结果？
5. 写一个简单的公式，用来计算放置n对两两相等的2n个对象的次序数。
4.7　将对象分装入箱
我们要介绍的下一类计数问题涉及对盛装若干对象之容器的选择。这些对象可能相同，也可能不同，不过容器是有区别的。我们必须计算这些装满容器的方法数。
有凯西、彼得和苏姗3个孩子，我们要将4个苹果分给他们，而不把苹果切开。那么共有多少种分配苹果的方式？
这里的方法数比较少，因此可以直接将其枚举出来。凯西可能得到从0至4个不等的苹果，而不管余下几个苹果，分给彼得和苏姗的方式都只有少数几种。如果设(i,j,k)表示凯西得到i 个苹果、彼得得到j 个苹果而苏姗得到k 个苹果的情况，那么图4-12就展示了全部15种可能的分配方式。每一行对应着分给凯西的苹果数。
(0，0，4)　　(0，1，3)　　(0，2，2)　　(0，3，1)　　(0，4，0)(1，0，3)　　(1，1，2)　　(1，2，1)　　(1，3，0)(2，0，2)　　(2，1，1)　　(2，2，0)(3，0，1)　　(3，1，0)(4，0，0)
图 4-12　把4个苹果分给3个孩子共有15种方式
为将相同对象分装入箱计数的方法有个诀窍。假设用4个字母A来表示4个苹果，并用两个*来分隔属于不同孩子的苹果。两个*之间的A的数量就表示彼得分到的苹果数，而第二个*之后的A的数量则表示属于苏姗的苹果数。例如，AA*A*A表示（2,1,1）的分配方式，其中凯西分到2个苹果，其余两个孩子各分到1个。而序列AAA*A*则表示（3,1,0）的分配方式，其中凯西得到3个，彼得得到1个，苏姗一个都没有。
因此，每种分发苹果的方式都与由4个A和2个*组成的唯一字符串相关。那么有多少这样的字符串呢？考虑一下组成这种字符串的6个位置。其中任选4个位置用来存放A，另外两个位置用来存放*。正如我们在4.5节中了解到的，从6项中选择4项共有种方法。因为，所以又一次得出了将4个苹果分给3个孩子的方法共有15种的结论。
4.7.1　装箱问题的一般规则
我们可以按照下列方式将示例4.15介绍的问题一般化。假设给定n个容器，它们对应示例中的3个孩子。同时假设要将m个相同的对象随意地放进这些容器中。那么有多少种分装入箱的方式呢？
这里可以再次考虑A和*组成的字符串。A表示对象，而*表示容器间的边界。如果有n个对象，就有n个A，而如果有m个容器，那么就需要m-1个*来表示分隔不同容器的边界。因此，字符串的长度为n+m-1。
我们可以从这些位置中任选n个存放A，剩下的就是存放*的。因此共有种由A和 *组成的字符串，那么将对象分装入箱的方式也有这么多种。在示例4.15中，有n=4且m=3，所以就可以得到共有种分配方式的结论。
在掷骰子游戏中，要掷出3个骰子，其中每个骰子的6个面上都标记了从1到6这6个数字。玩家可以为某个数字赌上1美元。如果这个数字不出现，钱就输掉了。如果该数字出现一次或多次，那么该玩家就可以得到与该数字出现次数等额的美元。
我们可能想要为“结果”计数，不过一开始在“结果”是什么的问题上可能有些疑问。如果将骰子不同的面涂上不同颜色以方便区别，就可将其视为4.2节中那样的计数问题，其中3颗骰子中的每一颗都能分配6个数字中的一个。我们知道，进行这样的分配共有63=216种方式。
不过，骰子通常是没有区别的，这些数字出现的顺序也是无关紧要的，只有每个数字出现的次数决定了哪个玩家会赢钱，会赢多少钱。例如，掷骰子的结果可能是有两颗是1，而第三颗是6。而6可能出现在第1颗、第2颗或第3颗骰子上，不过出现在哪颗骰子上都是没关系的。
因此，可以把这一问题视为将相同对象分装入箱的问题。“容器”就是1到6这几个数字，而“对象”就是3个骰子。一颗骰子会被“分装”到对应该骰子掷出数字的那个容器。因此，掷骰子游戏总共有种不同的结果。
4.7.2　分装有区别的对象
我们可以将之前的公式扩展一下，以便处理将可分为k类的n个对象装入m个容器的问题。同一类中的对象是没有区别的，但不同类的对象是不同的。这里用符号ai 表示第i 类中的成员。因此可以构成由下列对象组成的字符串。
1. 对每个类i，与类中所含成员数量等量的ai；
2. 用来表示m个容器间的边界的m-1个*。
因此这些字符串的长度是n+m-1，请注意，这些*构成了第k+1个类，而该类包含了m个成员。
我们在4.6节中已经了解过如何为这样的字符串计数。字符串的个数为
其中ij 表示的是第j 类中的成员数。
假设有三个苹果、两个梨和一根香蕉要分给凯西、彼得和苏姗。那么“容器”的数量，也就是孩子的数量m=3。共有k=3组，分别有i1=3、i2=2和i3=1个成员。因为总共有6个对象，所以n=6，因此该问题中的字符串的长度为n+m-1=8。这些字符串由3个表示苹果的A、两个表示梨的P、一个表示香蕉的B，以及两个表示边界的*组成。因此，由分发方法数的计算公式可得到共有
种将这些水果分发给凯西、彼得和苏姗的方式。
计数问题的对比
在本节及之前的4.1到4.5节中，我们已经考虑了6种不同的计数问题。每种问题都可视作为特定的位置分配对象。例如，4.2节介绍的分配问题可以视为给定了n个位置（对应房屋），以及不限量的具有k个不同类型（对应颜色）之一的对象。我们可以顺着3个方向为这些问题分类。
1. 它们是否会放置所有给定的对象？
2. 分配对象的次序是否重要？
3. 所有对象都是不同的，还是说某些对象没有区别？
下表表示了之前各节提到的问题之间的区别。
是否必须使用所有对象
次序是否重要
是否有相同的对象
给孩子分苹果
4.2节和4.4节中的问题在上表中体现不出什么区别。它们的区别在于是否放回，正如之前4.4.1节附注栏“有放回选择和无放回选择”中讨论的那样。也就是说，在4.2节中，每种“颜色”都是不限量供应的，可以多次选择同一颜色。而在4.4节中，一匹被选定的“赛马”不能在同一系列的选择中再被选中了。
4.7.3　习题
1. 进行下列分配任务分别有多少种方法?
(a) 6个苹果分给4个孩子；
(b) 4个苹果分给6个孩子；
(c) 6个苹果和3个梨分给5个孩子；
(d) 2个苹果、5个梨和6根香蕉分给3个孩子。
2. 下列情况分别有多少种结果？
(a) 掷4颗无区别的骰子；
(b) 掷5颗无区别的骰子。
3. * 将7个苹果分给3个孩子，并保证每个孩子至少得到一个苹果，共有多少种分发方法？
4. * 假设从国际象棋棋盘的左下角开始向右上角移动，每次向上或向右移动一格，完成这一移动的方式共有多少种？
5. * 将习题(4)一般化。如果有一个由n个方格乘上m个方格组成的矩形，并可以从一个方格向上或向右移动到另一个方格，那么从左下角移动到右上角总共有多少种方法？
4.8　计数规则的组合
组合这一主题能带来无数的挑战，而且很少像本章之前所讨论的那样简单。不过，我们目前所了解到的规则都是最基础，它们都很有价值，能以各种方式结合起来为更加复杂的结构计数。在本节中，我们将了解到3种实用的计数“诀窍”。
1. 将计数表示为一系列选择；
2. 将计数表示为计数的差；
3. 将计数表示为子情况的计数之和。
4.8.1　将计数分解为一系列选择
在为某类分配计数时，有一种实用的方法可以采用，就是将这些待计数的事物描述为一系列的选择，其中每次选择都会细化该类中某个特定成员的描述。在本节中，我们会给出一系列表示某些可能性的示例。
考虑一下扑克牌型中“对子”（one-pair）的数量。该牌型由一对具有某个秩2的牌，加上3张具有不同秩（而且与之前一对的秩不同）的牌组成。我们可以通过如下步骤描述所有的“对子”牌型。
213个秩分别为A、K、Q、J，以及2到10。
1. 为成对的牌选择秩；
2. 从其余12种秩中为其余3张牌选择3个不同的秩；
3. 为成对的牌选择花色；
4. 为其他3张牌选择花色。
如果将这些数字相乘，将得到“对子”牌型的数量。请注意，牌型中各张牌出现的顺序是无关紧要的，正如之前在示例4.8中讨论过的，而且我们从未尝试过指定次序。
现在，要依次接受这些因素。为成对的那两张牌选择秩的方式有13种。不管选择了哪个秩，都会余下12种。接下来必须从这些秩中选择3个组成剩下的牌型。就像4.5节中讨论过的，这也是一种次序不重要的选择，执行这种选择的方式共有种。
现在必须为这对牌选择花色。共有4种花色，而且我们必须从中选择两种。这次又是无序的选择，可以有种方式。最后，为剩下的3张牌选择花色。每张牌都有4种花色可选，所以又是4.2节中那样的分配问题，进行分配的方式共有43=64种。
因此，“对子”牌型的总数量为13×220×6×64=1 098 240 种，这一数字在2 598 960种扑克牌型中占了40%以上。
4.8.2　用计数的差来计算计数
另一种实用技巧是，将要计数的内容表示为某个更具一般性的排列类C与C中不满足计数条件的那些事物之间的差。
还有很多种扑克牌型（两对、三条、铁支和葫芦）可以按照类似示例4.18的方法计数。不过，还有一些其他牌型需要不同的方法来计数。
先来考虑一下同花顺的情况，也就是5张花色相同（同花）而且秩连续（顺子）的牌型。首先，每个顺子都是从A到10这10个秩之一开始的。也就是说，顺子可能是A-2-3-4-5，2-3-4-5-6，3-4-5-6-7，等等，最大的可能是10-J-Q-K-A。一旦秩确定，就只需要指定一种花色来指定该同花顺了。因此，为同花顺计数包含以下两步：
1. 选择顺子的最低秩（10种选择）；
2. 选择花色（4种选择）。
因此，总共有10×4=40种同花顺牌型。
现在来为顺子牌型计数，也就是那些秩连续但又不是同花顺的牌型。先要计算所有具有连续秩的牌型的数量，不考虑它们的花色是否相同，然后再减去40种同花顺牌型。要为秩连续的牌型计数，可以按以下两步进行：
1. 选择最低的秩（10种选择）；
2. 为每个秩指定一种花色（如4.2节介绍的，有45=1024种选择）。
因此，顺子和同花顺牌型的总数是10×1 024=10 240种。减去40种同花顺牌型后，就得出顺子牌型共有10 240-40=10 200种。
接下来，考虑一下同花牌型的数目。这里还是要先将同花顺牌型考虑在内，然后再减去那40种同花顺牌型。可以通过如下方式定义同花牌型。
1. 选择花色（4种选择）；
2. 从13个秩中任选5个，如4.5节介绍的，共有种方式。
于是可以得出同花牌型共有4×1 287-40=5 108种。·
4.8.3　将计数表示为子情况的和
在面对一些很难直接解决的问题时，就要用到第三种“诀窍”了。可以把为某个类C 计数的问题分解成两个或多个单独的问题，而类C 中的各个成员刚好都能被子问题之一涵盖。
假设要抛10次硬币，那么8个或8个以上硬币人头面朝上的序列有多少种？如果想知道有多少序列刚好有8个硬币人头面朝上，可以用4.5节介绍的方法来解决。共有种这样的序列。
要解决为8个或8个以上硬币人头面朝上的序列计数的问题，可以将其分解为3个子问题，即分别为刚好有8个硬币人头面朝上、刚好有9个硬币人头面朝上以及10个硬币全部人头面朝上的情况计数。我们已经解决了第一个问题。而9个硬币人头面朝上的序列共有种，10个硬币全是人头面朝上的序列共有种。因此，有8个或8个以上硬币人头面朝上的序列共有45+10+1=56种。
再来考虑一下示例4.16中解决的为掷骰子游戏的结果计数的问题。另一种方法就是根据所出现的不同数字是3个、2个或1个，将该问题分成3个子问题。
(a) 可以用4.5节介绍的技巧计算3个数字皆不同的结果的数量。也就是从一颗骰子6个可能的数字中选出3个，总共有种不同的方法。
(b) 接着，要计算两颗骰子是一个数，而另一颗是另一个数的情况有多少种。出现两次的数字有6种选择，每种情况下对应的出现一次的数字有5种选择。所以两颗骰子是一个数而另一颗是另一个数的结果共有6×5=30种。
(c) 3颗骰子数字全相同的情况共有6种。
因此，可能的结果共有20+30+6=56种，这与示例4.16中得到的结论是一样的。
4.8.4　习题
1. * 为以下扑克牌型计数：
(a) 两对；
(b) 三条；
(c) 葫芦（三条加一对）；
(d) 铁支（四条）。
请注意，在为某种牌型计数时不要将那些更佳的牌型计算在内了。例如，在情况(a)中，要确定两对是不同的，不然就是拿到了铁支牌型，而且要保证第5张牌和这两对的秩不一样，否则就是拿到了葫芦牌型。
2. * 黑杰克由两张牌组成，其中一张是A，而另一张是10分牌，就是10、J、Q或K中的一种。
(a) 在一摞52张扑克牌中，有多少种不同的黑杰克？
(b) 在黑杰克游戏中，有一张牌是暗牌，而另一张是明牌。因此，两张牌的次序是有影响的。在这种情况下，有多少种不同的黑杰克？
(c) 在皮诺奇勒牌游戏中，只使用秩为9、10、J、Q、K和A的牌各8张（每种花色各有两张同秩的牌），而不使用其他扑克牌。假设次序无关紧要，共有多少种黑杰克？
3. “什么都不是”（即不是对子或更好）的牌型共有多少种？大家可能要利用示例4.18和示例4.19的结果以及习题(1)的解答。
4. 如果依次抛12枚硬币，那么下列情况各有多少种？
(a) 至少有9枚硬币人头面朝上；
(b) 至多有4枚硬币人头面朝上；
(c) 有5到7枚硬币人头面朝上；
(d) 不到2枚或多于10枚硬币人头面朝上。
5. * 至少有一个数字为1的掷骰子结果共有多少种？
6. * 使用单词little的字母构词，其中两个t不相邻的情况共有多少种？
7. ** 桥牌牌型由52张扑克牌中的13张构成，我们通常会通过“分布”为牌型分类，也就是说，会按照花色为手牌分组。例如，牌型4-3-3-3的分布表示有4张牌是某种花色，而另外3种花色的牌各有3张。牌型5-4-3-1的分布表示各花色的牌分别有5张、4张、3张和1张。为具有如下分布的牌型计数：(a)4-3-3-3；(b)5-4-3-1；(c)4-4-3-2；(d)9-2-2-0。
4.9　概率论简介
概率论在计算机科学领域具有很多用途，其中一种重要应用就是估算平均输入或典型输入情况下的程序运行时间。这种估算对那些最坏情况运行时间远大于平均运行时间的算法来说非常重要。我们很快就会看到这种估算的示例。
概率的另一种用途是在具有不确定性的情况下设计制定决策的算法。例如，可以使用概率论，设计根据可用信息制定最佳医疗诊断的算法，或设计在未来预期需求的基础上分配资源的算法。
4.9.1　概率空间
概率空间是指点的有限集，这些点分别表示某一实验的某种可能结果。每个点x 都与某个称作x 的概率的正实数相关联，而所有点对应概率的和为1。还有无限多个点的概率空间这样的说法，不过这种概念在计算机科学领域鲜有应用，所以这里不需要考虑这些。
通常，概率空间中的点都是等可能的。除非特别声明，否则可以假设概率空间中若干点表示的概率都是相等的。因此，如果概率空间中有n个点，则每个点的概率都是1/n。
图4-13所示为具有6个点的概率空间。这些点分别被标记为从1到6这6个数字中的一个，而且可将该空间视为表示掷一次骰子这项“实验”的结果。也就是说，骰子6个面中某个面上的数字会出现在最上方，而每个数字出现的概率都是均等的，即都是1/6。
图 4-13　具有6个点的概率空间
概率空间中这些点的任意子集都可称为事件。某个事件E 的概率——记为PROB(E )——就是E 中各点概率之和。如果这些点都是等可能的，就可以用E中点的数目除以整个概率空间中点的数目来计算E的概率。
4.9.2　概率的计算
通常情况下，计算某个事件的概率会涉及组合。我们必须计算事件中点的数量，以及整个概率空间中点的数量。当点是等可能时，这两个计数的比就是该事件的概率。接下来要介绍一系列示例，展示按这种方式计算概率的过程。
无限的概率空间
在某些情况下，可以想象一个具有无数个点的概率空间，其中任何给定的点的概率都可能是无穷的，从而只能将有限的概率与某些点的集合关联起来。举个简单的例子，下图中的正方形表示某个概率空间，而该概率空间中的点是该正方形所在平面上的所有点。
可以假设正方形中任何点被选中的可能性都是相等的，并将这种“实验”视作往该正方形中投掷飞镖，飞镖飞到正方形上任何位置的可能性都是相同的，但肯定不会飞到正方形之外。虽然任何一点被击中的概率都是无穷的，但是该正方形中某个区域的概率等于该区域的面积与整个正方形的面积之比。因此，我们可以计算某些事件的概率。
例如，上图的概率空间中含有一个椭圆形组成的事件E。假设该椭圆区域的面积是整个正方形面积的29%，那么PROB(E )就是0.29。也就是说，如果随机地向该正方形投出飞镖，那么29%的情况下飞镖会落在这个椭圆中。
图4-14展示了表示掷两颗骰子的概率空间。也就是说，进行的实验是按顺序抛出两颗骰子，并观察它们朝上那面的数字。假设掷骰子的过程是公平的，就有36个等可能的点，或者说是实验结果，所以每个点的概率都是1/36。每个点对应着每颗骰子从6个值中任选其一的分配。例如，（2,3）就表示第一颗骰子为2点，而第二颗骰子为3点的情况。而（3,2）则表示第一颗骰子是3，第二颗是2的情况。
被圈出来的区域表示“吃憋”的事件，也就是两颗骰子的总点数为7或11的情况。这个事件共含有8个点，其中6个是总点数为7的情况，而有两个是总点数为11的情况。投出“吃憋”情况的概率就是8/36，约为22%。
图 4-14　掷两颗骰子的概率空间中的“吃憋”事件
再来计算一下扑克牌出现对子牌型的概率。我们在示例4.8中已了解到总共有2 598 960种不同的扑克牌型。考虑该公平处理扑克牌型的实验，也就是说，所有牌型出现的可能性都相等。因此，该实验的概率空间总共有2 598 960个点。我们还从示例4.18中得知，这些表示牌型的点中有1 098 240个被分类为对子牌型。假设所有牌型被处理的可能都是均等的，那么“对子”事件的概率就是1 098 240/2 598 960，大约是42%。
在基诺游戏中，会随机从1到80这些数字中选出20个。而且选取这些数字之前，玩家可以猜测一些数字。这里要专门讲讲这个玩家要猜测5个数字的“5点游戏”。所猜数字与选中的20个数字中有3个、4个或5个吻合的话，玩家就中奖了，而且猜中的数字越多，得到的奖金越丰厚。我们要计算的是玩家在该游戏中正好猜中3个数字的概率。正好猜中4个或5个数字的概率的计算将留作本节的习题。
首先，合适的概率空间包含了表示从1到80中任选20个数字所有可能情况的点。这样的选择总共有
种，这个数字奇大无比，好在不需要把它写出来。
结果何时是随机的？
在示例中已经假设过某些实验具有“随机的”结果，也就是说，所有可能出现的结果的可能性都是相等的。在一些情况下，这种假设的合理性源自物理学。例如，在投掷公平（未加重）的骰子时，我们假设在物理上不可能控制骰子的某个面比其他面更可能朝上。这在实践中是种有效的假设。同样，我们可以假设公平洗牌的牌堆不会影响结果，而且任何一张牌出现在牌堆中任意位置的可能性都是相同的。
在其他情况下，我们发现一些貌似随机的事物实际上根本不随机，只不过是某个过程原则上可预知但在实践中不可预知的结果。例如，基诺游戏中选出的数字可能是由计算机执行某个特殊算法生成的，而如果没法接触到计算机使用的这些秘密信息，就不可能预测结果。
计算机生成的“随机”序列都是某种被称为随机数生成器的特殊算法的结果。设计这样的算法需要一些专门的数学知识，而这些知识超出了本书的范畴。不过，我们会介绍一种实践中相当好用的随机数生成器——线性同余生成器。
指定常数a≥2，b≥1，x0≥0，而且a modm>max(a,b,x0)，便可以通过使用公式
xn+1=(axn+b)modm
生成一列数字x0，x1，x2…。如果选择的a、b、m和x0很合适，那么得到的数字序列就会显得相当随机，即便它们是通过特定算法由“种子”x0计算得出的。
随机数生成器生成的序列有很多用途。例如，可以根据上述序列选取基诺游戏中的开奖号码，用上述序列中的每个数除以80，取余数，并加上1，得到1到80间的某个“随机”数。不断 这样处理，除去重复的数字，直到选出20个数字。只要没人知道生成算法和种子，这一游戏就 可视为是公平的。
现在要计数的情况是从80个数字中选出20个，其中含有玩家所选择5个数字中的3个，以及玩家没有选择的75个数字中的17个。从5个数字中选出3个共有种方式，而从剩下的75个数字中选取17个的方式共有种。
因此，玩家在5个数字中猜中3个的结果数与总选择数的比就是
如果将上下都乘上，上式就成了
可以看到分子和分母中的阶乘项很接近，几乎可以约去。例如，分子中的75!和分母中的80!就可以用分母中80到76这5个数的乘积代替，所以可以简化为
这样就可以对可控数字加以计算了，结果是0.084。也就是说，玩家在5个数字中猜中3个的概率大约为8.4%。
4.9.3　基本关系
本节要审视概率的一些重要属性。首先，如果p 是任一事件的概率，那么
也就是说，任何事件都是由0个或更多个点组成，所以它的概率不可能为负值。而且，没有任何事件会由比整个概率空间还多的点构成，所以它的概率不会超过1。
其次，设E 是某个概率空间P 中的事件。那么事件E 的互补事件E 就是P 中不属于事件E 的点的集合。不难看出
PROB(E ) + PROB() = 1
或者换句话说，PROB() = 1 - PROB(E )。原因在于，P 中的每个点，要么在E 中，要么在中，不可能同时在二者之中。
4.9.4　习题
1. 使用图4-14中展示的掷两颗公平骰子的概率空间，给出以下事件的概率。
(a) 掷出的点数为6（即两颗骰子点数之和是6）；
(b) 掷出的点数为10；
(c) 掷出的点数为奇数；
(d) 掷出的点数在5到9之间。
2. * 计算以下事件的概率。概率空间是从普通的52张扑克牌堆中按次序取两张牌的所有情况。
(a) 至少有一张牌是A；
(b) 两张牌的秩相同；
(c) 两张牌花色相同；
(d) 两张牌的秩和花色都相同；
(e) 两张牌要么秩相同要么花色相同；
(f) 第一张牌的秩高于第二张牌的秩。
3. * 将飞镖掷向墙上一英尺见方的区域，击中该方形区域中任何一点的可能性都是相同的。那么在投掷飞镖时
(a) 离中心3英寸以内的概率是多少？
(b) 离边缘3英寸以内的概率是多少？
请注意，在该习题中，概率空间是一个一英尺见方的无限区域，其中所有点都是等可能性的。
4. 计算玩家在基诺5点游戏中猜中如下数字的概率。
(a) 猜中5个数字中的4个；
(b) 猜中全部5个数字。
5. 编写C语言程序实现线性同余随机数生成器。绘制它生成的前100个数字最低有效位各数字出现频率的直方图。该直方图应该具有什么属性？
4.10　条件概率
在本节中，我们将指定数项公式和策略，用来考虑若干事件概率之间的关系。其中一项重要的结论就是独立实验的概念。在独立实验中，一项实验的结果不影响其他实验的结果。我们还将运用一些技巧来计算某些复杂情形下的概率。
这些结论都依赖于“条件概率”的概念。不严谨地说，如果进行一次实验，而且得知事件E 已经发生，那么表示这种结果的点也有可能出现在另一事件F 中。图4-15就展示了这种情况。E 条件下F 的概率就是E 发生前提下F 也发生的概率。
图 4-15　E 条件下F 的概率是结果在A 中的概率除以结果在A 或在B 中的概率
正式地讲，如果E 和F 是某个概率空间中的两个事件，那么E 条件下F 的概率，记作PROB(F |E )，就是同时出现在E 和F 中的所有点的概率之和除以出现在E 中各点的概率之和。在图4-15中，区域A 表示那些同时在E 和F 中的点，B 则表示在E 中而不在F 中的点。如果所有点都是等可能的，那么PROB(F |E )就是A 中点的数量除以A 和B 中点的数量之和。
考虑图4-14中表示掷两颗骰子的概率空间。设事件E 是第一颗骰子点数为1的6个点，F 是第二颗骰子点数为1的6个点，情形如图4-16所示。既在E 中又在F 中的点只有一个，即点(1，1)。在E 而不在F 中的点共有5个。因此，条件概率PROB(F |E )为1/6。也就是说，在确定第一颗骰子为1的条件下，第二颗骰子为1的概率是1/6。
大家可能会注意到，这一条件概率刚好等于F 本身的概率。也就是说，因为F 占有整个概率空间36个点中的6个点，所以PROB(F )=6/36=1/6。从直观上讲，第二颗骰子掷出1的概率，并不受第一颗骰子已经掷出1这一事实的影响。我们很快就将定义“独立实验”（比如依次掷骰子）的概念，其中一次实验的结果不会对其他实验的结果产生影响。在这样的情况下，如果E 和F 是表示两次实验结果的事件，就可以预期PROB(F |E )=PROB(F )。我们已经看过这一现象的一个例子了。
假设实验是从有52张扑克的牌堆中按次序取两张牌。在这一不放回选择（如4.4节所述）实验中，点的数目是52×51=2652。假设这种取牌是公平的，所以每个点的可能性都是相同的。
设事件E 是第一张牌为A的情况，F 是第二张牌为A的情况。那么E 中的点共有4×51=204个。也就是说，第一张牌是4张A中的某一张，而第二张牌可以是除去第一次选走的A之外的51张牌中的任意一张。因此，PROB(E )=204/。这一结果是符合大家的直觉的。所有13种秩都是等可能性的，所以可以预期第一张牌出现A的可能是1/13。
同样，事件F 中也有4×51=204个点。可以为第二张牌任选一种A，并在其余51张牌中任选其一作为第一张牌。第一张牌理论上讲要先取得，而这一事实是无关紧要的。因此A出现在第二张的情况共有204种。因此，与E 一样，PROB(F )=1/13。这个结果还是满足A是第二张牌的可能为1/13这一直观感受。
现在来计算PROB(F |E )。在E 的204个点中，第二张牌也为A（也就是点也在F 中）的情况有12个。也就是说，E 中的所有点都表示A为第一张牌的情况。选择A的方式共有4种，对应4种花色的选择。在每种选择中，第二张牌也为A的选择都有3种。因此，根据4.4节介绍的技巧，有序选择两张A的情况共有4×3=12种。
因此，条件概率PROB(F |E )是12/204，或者说是1/17。可以注意到，在本例中，E 条件下F 的概率与F 的概率并不相等。这也是符合直观感受的。当第一张牌取走一张A之后，第二张牌再取到A的概率就下降了。那时候，剩下的51张牌中只有3张A，而3/51=1/17。与之相对的是，如果不知道第一张牌是什么，那么第二张牌就可能是52张牌中4张A中的某一张。
4.10.1　独立实验
正如示例4.23、示例4.26和示例4.27中所介绍的，有时候建立的概率空间会表示两个或多个实验的结果。在最简单的情况下，该共同概率空间中的点是结果的表，每个表代表一项实验的结果。图4-16就给出了两项实验联合起来的概率空间。在实验结果间存在联系的情形中，共同空间中可能会丢失一些点。示例4.27就讨论了这样的情况，其中共同空间表示取两张牌且结果成对，其中不可能取到两张相同的牌。
实验X 独立于序列中前序实验的结果。从直观概念上讲这意味着X 的各种结果都不依赖于前序实验的结果。因此，示例4.26中我们指出掷第二颗骰子是独立于掷第一颗骰子的，而在示例4.27中，我们看到取第二张牌的实验并非独立于取第一张牌的实验，因为取出第一张牌后，就不可能再次取到这张牌了。
在定义独立性时，将着重于两项实验的关系。不过，因为任一实验本身也可能是一个若干实验构成的序列，所以这样的定义有效地涵盖了具有很多实验的情况。首先必须了解表示两项成功实验X1和X2的结果的概率空间。
图4-14展示了一个共同概率空间，其中实验X1是第一颗骰子，而实验X2是第二颗骰子。这里每一对结果都是用一个点表示的，而这些点的可能性是相等的，都等于1/36。
在示例4.27中，我们讨论过表示按次序选取两张牌、含52个点的概率空间。该空间由(C,D )这样的牌对组成，其中C 和D 分别是某张扑克牌，而且C≠D。这些点的可能也相同，都是1/2652。
在表示X1接着X2的结果的概率空间中，存在表示其中一项实验的结果的事件。也就是说，如果a 是实验X1可能出现的结果，就有一个事件是由所有表示第一项实验结果为a 的点组成的。这里将该事件称为Ea 。同样，如果b 是实验X2可能出现的结果，就有一个事件Fb是由所有表示第二项实验结果为b 的点组成的。
在图4-16中，E是E1，就是表示第一项实验结果为1的所有点。同样，F是事件F1，就是那些表示第二项实验结果为1的点。每一行对应着第一项实验6种可能结果中的一种，而每一列则对应第二项实验6种可能结果中的一种。
图 4-16　表示第一颗骰子或第二颗骰子点数为1的事件
严格地讲，如果对X1的所有结果a以及X2的所有结果b，有PROB(Fb|Ea)=PROB(Fb)，那么就说实验X2是独立于实验X1的。也就是说，不管实验X1的结果是怎样的，实验X2各结果的条件概率都是相同的，而且都等于实验X2在整个概率空间中的概率。
回到图4-16表示掷两颗骰子的概率空间，设a 和b 分别是1到6这些数字中的任意一个。用Ea表示第一颗骰子为a 的事件，Fb表示第二颗骰子是b 的事件。不难注意到，这些事件的概率均为1/6，它们各自排成一行或一列。对任意的a 和b 来说，PROB(Fb|Ea)也是1/6。我们在示例4.26中已经证实这一结论在a=b=1的情况下是成立的，不过同样的论证过程也适用于任意两个结果a和b，因为它们的事件只有一个点是相同的。因此，掷两次骰子是相互独立的。
另一方面，在以扑克牌为例的示例4.27中，就不存在这种独立性。因为，实验X1是第一张牌的选择，而实验X2是从剩下的牌中选择第二张牌。考虑诸如FA?这样的事件，也就是说，第二张牌为黑桃A的情况。很容易便能得出该事件的概率PROB(FAA?这)为1/52的结论。
再来考虑诸如E3?，也就是第一张牌为草花3的情况。同在E3?和FA?中的点只有一个，就是点(3?,A?)。而E3?中的点共有51个，也就是形如(3?,C)这样的点，其中C是除了草花3之外的任意一张牌。因此，条件概率PROB(FA?|E3?)是1/51，而不是1/52，因为这两项实验不是相互独立的。
可以考虑一个更极端的例子，就是第一张牌为黑桃A的事件EA?。因为EA?和FA?中没有相同的点，所以PROB(FA?|EA?)就是0，而不是1/52。
4.10.2　概率的分配律
有时候，如果先将概率空间划分为几个区域3，就会让概率的计算变得更加容易。也就是说，每个点都只出现在一个区域中。通常，概率空间表示一系列实验的结果，而表示事件的区域则对应其中某一实验可能出现的结果。
3“区域”指的就是“事件”，也就是概率空间的子集。不过，这里使用术语“区域”是为了强调这是将概率空间分为完全覆盖整个区域又不互相重叠的事件。
假设要计算被分为R1、R2、…、Rk 这k 个区域的某个具有n个点的概率空间中事件E 的概率。简单起见，假设所有点的概率都是相同的，尽管就算它们的概率不同也不影响结论的成立。设事件E 由m个点组成。设区域Ri 中有ri 个点（i=1、2、…、k）。最后，设E中处于区域Ri 中的点有ei 个。请注意，，而且。原因皆在于这些点都会在某个区域中而且只会在一个区域中。
我们知道PROB(E)=m/n，因为m/n 就是E 中的点所占的部分。如果用ei 的和替代m，就得到
接着，在上述和式中每一项的分子和分母中都引入因子ri 。结果就是
现在，请注意ri /n 就是PROB(Ri )，也就是说，ri /n是区域Ri 在整个概率空间中所占的部分。此外，ei /ri 就是PROB(E /Ri )，即事件Ri 条件下事件E 的概率。换句话说，ei /ri 是区域Ri 中也出现在E 中的点的比例。结果就得到以下事件E 概率的计算公式。
PROB(E ) = PROBPROB(Ri )　　　　　　(4.10)
非正式地讲，E 的概率是各区域的概率乘上E 在相应区域中的概率的总和。
图4-17表示了(4.10)式的应用方式。图中展示了被垂直划分为R1、R2和R3这3个区域的概率空间。其中事件E 是再度用线勾勒出的。设a 到f 分别是所示6个组中点的数目。
设n=a+b+c+d+e+f。那么有PROB(R1)=(a+b)/n、PROB(R2)=(c+d)/n，而且PROB(R3)=(e+f )/n。而事件E 在这3个区域的条件概率分别是PROB(E |R2)=a/(a+b)、PROB(E |R2)=c/(c+d)，而且PROB(E |R3)=e/(e+f )。现在来评估(4.10)式，就有
图 4-17　分为区域的概率空间
PROB(E )＝PROB(E |R1)PROB(R1)+PROB(E |R2)PROB(R2)+PROB(E |R3)PROB(R3)
如果将该式用a 到f 的参数表示，就是
PROB(E ) =
请注意，直接将标记有a、c、e的3块中点的数目与整个空间的大小相比，也能得到同样的结果。(a+c+e)/n这一分数正是上式给出的E的概率，这一结果证明了(4.10)式。
现在利用(4.10)式计算事件E“按次序取两张扑克牌均是A”的概率。概率空间是示例4.27中讨论过的那2652个点。这里要将该空间分为R1、R2两个区域。
R1：第一张牌为A的那些点。总共有4×51=204个这样的点，因为第一张牌为A的情况有4种，而每种情况下对应的第二张牌都有51种选择。
R2：剩下的2448个点。
这种情况下，(4.10)式就成了
PROB(E )＝PROB(E |R1)PROB(R1)+PROB(E |R2)PROB(R2)
显然PROB(E |R1)，也就是R2条件下E 的条件概率，为0。如果第一张牌不为A，那么不可能拿到两张A，因此必须计算PROB(E |R1)PROB(R1)，而这个值就是PROB(E )。现在有PROB(R1)=204/。换句话说，第一张牌拿到A的可能性是1/13。因为总共有13种秩，所以这一概率是说得通的。
现在需要计算PROB(E |R1)。如果第一张牌是A，那么剩下的51张牌中还剩3张A。因此，PROB(E |R1)=3/51=1/17。因此可以得出结论：PROB(E )=(1/17)(1/13)=1/221。
现在用(4.10)式来计算事件E“掷3颗骰子，至少出现一个1点”的概率，就像示例4.16中描述过的掷骰子游戏那样。首先，我们一定要理解，那个例子中描述的“结果”的概念与概率空间中的点并不匹配。在示例4.16中，我们建立的概率空间有56种不同的“结果”，这是骰子出现1到6点的次数。例如，“一个4点、一个5点和一个6点”是一种结果，而“两个3点和一个4点”是另一种结果。然而，这种情况下各种结果的概率并不相同。特别要说的是，3个数字都不同的概率是某个数字出现两次的概率的两倍，是3个骰子数字都相同的概率的6倍。
尽管可以使用点对应示例4.16中那种“结果”的概率空间，不过考虑按顺序掷骰子，从而构建一个包含的点概率相等的概率空间要更为自然。这样一来就有63=216种不同的结果与按次序掷3次骰子的事件对应，而每个结果的概率均为1/216。
我们可以不使用(4.10)式，而是直接计算至少有一颗骰子为1点的概率。首先，计算没有1出现的情况数。可以为3颗骰子分配2到6之中的任一数字。这样概率空间中不含1的点共有53=125个，所以有1的点就有216-125=91个。因此，PROB(E )91/216，大约为42%。
上述方法虽然简短，但需要使用些许“技巧”。计算这一概率的另一种方式是“强行”将概率空间分为3个区域，对应出现一个数字、两个不同数字或3个不同数字的情况。设Ri 是具有i 个不同数字的点所在的区域。可以按照下列方式计算各区域的概率。就R1而言，总共有6个点，也就是3个骰子均为1到6这些点时的情况。就R3而言，根据4.4节中的规则，从6个数字中选出3个不同的数字共有6×5×4=120种方式。因此R2中一定是具有剩下的216-6-120=90个点。4各区域的概率分别是PROB(R1)=6/216=1/36、PROB(R2)=90/216=5/12、PROB(R3)=120/216=5/9。
4可以直接计算该数字，用选择会出现两次的点数的6种方式，乘上选择其余骰子点数的5种方式，再乘上选择只出现一次的那个数字所在位置的种方式。就是6×5×3=90种方式。
接着要计算条件概率。如果出现了6个数字中的3个数字，那么其中一个为1的概率是1/2。如果出现了2个数字，那么至少出现一次1的概率是1/3。如果只有一个数字出现，那么该数字为1的概率是1/6。因此PROB(E |R1)=1/6、PROB(E |R2)=1/3，而且PROB(E |R3)=1/2。将这些概率都代入(4.10)式中，就得到
PROB(E ) = (1/6)(1/36)+(1/3)(5/12)+(1/2)(5/9)　　　 　=1/216+5/36+5/18=91/216
当然，这一分数和直接计算的结果是吻合的。如果能理解直接计算中的那些“诀窍”，那么直接计算的方法是相当容易的。不过，将问题分为若干区域往往是一种更为可靠的保障成功的方式。
4.10.3　独立实验的乘积法则
一类常见的概率问题是求一系列独立实验的一系列结果的概率。在这种情况下，(4.10)式具有了特别简单的形式，表明这一系列结果的概率就是每一结果概率的乘积。
首先，将概率空间等分为k 个区域，就会对所有的i有PROB(Ri )=1/k，因此(4.10)式可以简化为
PROB(E) = PROB(E |Ri )　　　　　　(4.11)
看待(4.11)式的一种实用方式是将E的概率视为各区域条件下E 的概率的平均值。
现在考虑表示两项独立实验X1和X2的结果的概率空间。可以将该空间分为k个区域，每个区域都是点的集合，这些点表示具有某个特定值的X1的结果，这样每个区域都具有相同的概率1/k。
假设要计算事件E“X1的结果为a，且X2的结果为b”的概率，可以使用(4.11)式。如果Ri 不是对应X1的结果a 的区域，那么PROB(E |R1)=0。因此，(4.11)式中就只剩下a 区域的项了。如果说该区域为Ra，就得到
PROB(E ) = PROB(E |Ra)　　　　　　(4.12)
PROB(E |Ra)是什么？它是在X1的结果为a的条件下，“X1的结果为a，且X2的结果为b”的概率。因为给定了X1的结果为a，所以PROB(E |Ra)是在X1的结果为a的条件下，X2的结果为b的概率。又因为X1和X2是相互独立的，所以PROB(E |Ra)就是X2的结果为b的概率。如果X2可能有m种结果，那么PROB(E |Ra)就是1/m。那么(4.12)式就成了
PROB(E ) =
我们可将上述推理一般化为针对任意数量的实验。想这样做，可以令实验X1是一系列实验，并通过对独立实验总数量的归纳来证明，有着特定序列的全部结果的概率等于每个结果的概率的乘积。
利用独立性简化计算
如果知道实验是相互独立的，就有很多机会简化概率计算。乘积法则是一个例子。另一个例子就是，只要E 是表示实验X1特定结果的点集合，F 是另一个独立实验X2特定结果的点集合，那么就有PROB(E |F )＝PROB(E )。
原则上讲，分辨两项实验是否相互独立是个复杂的任务，涉及对表示实验结果对的概率空间的检测。不过，通常可以借助该情形的物理特性，在不进行这种计算的情况下得出实验互相独立的结论。例如，在依次掷骰子时，不存在物理学上的原因令一次投掷的结果能影响其他投掷的结果，所以它们肯定是独立实验。而从牌堆中取牌则与掷骰子的情况不同。因为取出的牌是无法在随后的过程中被再次取出的，所以不用指望连续取牌是相互独立的事件。事实上，我们已在示例4.29中看到了这种独立性的缺失。
电话号码后四位为1234的概率是0.0001。每一位号码的选择都是有0到9这10种可能结果的实验。其次，每一位的选择都独立于其他位的选择，因为这里进行的是4.2节中介绍的“有放回的选择”。第一位是1的概率为1/10。同样，第二位是2的概率为1/10，而其他两位的情况也是一样的。所以4位数字依次为1234的概率就是(1/10)4=0.0001。
4.10.4　习题
1. 使用图4-14所示的概率空间，给出如下事件对的条件概率。
(a) 在第一颗骰子为奇数的条件下，第二颗骰子是偶数。
(b) 在第二颗骰子至少为3的条件下，第一颗骰子是偶数。
(c) 在第一颗骰子为4的条件下，两颗骰子点数之和至少为7。
(d) 在两颗骰子点数之和为8的条件下，第二颗骰子是3。
2. 将掷骰子（见示例4.16）游戏的概率空间按照示例4.33所示划分为3个区域，使用这一划分方式与4.10式计算如下概率。
(a) 至少出现两个1点。
(b) 3颗骰子都是1点。
(c) 刚好有一颗骰子是1点。
3. 证明：在掷3颗骰子的游戏中，3颗骰子点数均不同的概率，是有两颗骰子出现同一点数的概率的两倍，是3颗骰子点数均相同的概率的6倍。
4. * 通过对n 的归纳证明，如果有n 项实验，而且每一项实验都是相互独立的，那么任一系列结果的概率等于对应实验各项结果概率的乘积。
5. * 证明：如果有PROB(F |E )=PROB(F )，则有PROB(F |E )=PROB(E )。并证明：如果实验X1独立于实验X2，那么X2也独立于X1。
6. * 考虑从W和L中作出选择组成的长度为7个字母的序列的集合。可以将其视为表示7场4胜制比赛的结果的序列，其中W表示第一支队伍获得1场比赛的胜利，而L表示第二支队伍获胜。哪支队伍先取得4场胜利则赢得这场系列赛（因此，有些比赛可能从未进行过，不过我们需要将其假设结果包含在这些点中，从而获得各点概率相等的概率空间）。
(a) 在某支队伍取得第一场比赛胜利的条件下，该队在这