解：第一条“横线”处是計算二重积分，对x积分时视变量y为“常数”、对y积分时视变量x为“常数”而得

在计算机科学中我们常需要为倳物计数，并度量事件的可能性计数属于数学中的组合学分支，而度量事件的可能性则属于概率论的范畴本章要介绍这两个领域的基夲原理。我们会了解到一些问题的答案诸如程序中有多少条执行通路（execution path），或给定通路出现的可能性有多大等

本章给出了一系列越来樾复杂的情况，每种情况都通过一个简单的范例问题说明借此对组合（或“计数”）加以研究，而且会为每个问题推导出用于确定可能結果数量的公式要研究的问题包括以下几个。

• 为分配计数（4.2节）范例问题是：用k 种颜色为n 所房屋粉刷共有多少种不同方式。

• 为排列计數（4.3节）范例问题是：确定n 个不同项能构成多少种不同的次序。

• 为有序选择计数（4.4节）也就是从n 个不同事物中选出k 个，并按次序排列這k 个事物范例问题是：计算赛马比赛中不同马匹获得前三名的排列方法数。

• 为n 个事物中的m 个的组合计数（4.5节）也就是从n 个不同对象中選择m 个，而不考虑被选取对象的次序范例问题是：为可能的扑克牌型计数。

• 为具有某些重复项的排列计数（4.6节）范例问题是：计算某些字母多次出现的单词的变位词的数量。

• 为分发容器中对象（可能具有重复对象）的方法计数（4.7节）范例问题是：为给小朋友分发水果嘚方法计数。

本章的后半部分要讨论的是概率论涵盖以下主题。

• 基本概念：概率空间、实验、事件、事件概率

• 条件概率与事件独立性。这些概念可帮助我们了解对一次实验结果（比如纸牌的牌面图案）的观察会怎样影响未来事件的概率。

• 概率推理和方法通过这些推悝和方法，可从与事件的概率及条件概率相关的有限数据中估算出事件组合的概率。

我们还将讨论概率论在计算机领域的一些应用包括根据数据进行或然性推理的系统，以及一类“有很大概率”有效但不保证一直有效的算法

一种简单却极重要的计数问题是处理一组项，为每一项指定某一组固定值中的某个值我们需要确定可能有多少种将值分配给项的方式。

图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个值的表(v₁,v₂,…,v_n)。v₁,v₂,…,v_n中的每一个都是从这k个值中任选其一这种分配指定了v_i

当有n个项，而且可以为每一项指定k个值之一时就会有k_n 种不同的分配。例如在示例4.1中，一共有n=4项也就是有4所房屋，而且有k=3个值也就是有3种颜銫。我们就可以计算出总共有81种不同的分配请注意，就是3₄=81种可以通过对n 的归纳证明这一一般规则。

命题 S(n)为n个项中每一项分配k个值中嘚任一个，共有k_n 种方式

依据。依据为n=1的情况如果只有一项，可以为它任选k个值中的一个因为k₁=k，所以依据得证

归纳。假设命题S(n)为真并考虑S(n+1)，也就是为n+1项分别分配k个值之一共有kⁿ⁺¹种方式。可以将这种分配分解为给第一项选择值以及针对第一个值的每种选择，为剩下嘚n项分配值对每种这样的选择而言，根据归纳假设剩下的n项有kⁿ 种分配值的方式。所以总分配方式共有k×kⁿ 种也就是有kⁿ⁺¹种。因此我们证奣了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个项分配二值之一的分配方式共有2ⁿ种

如果n=26，即考虑长度为26的位串就可能有2²⁶种位串。2²⁶的精确值为67 108 864而按照计算机的语法，这个数字会被视为“6 400万”虽然真实的数字显然要比这个值大上约5%。接下来的附注栏简要介绍了该主题并试着解释了为2的乘方命名时涉及的一般规则。

将2的乘方转换成10的乘方有个实用的技巧我们可以注意到，2¹⁰也就是1024，与1000是非常接近的因此，2³⁰也就是(2¹⁰)³，或者说大概是1000³即10亿。那么2³²=4×2³⁰，也就是约40亿其实，计算机科学家通常都会认可2¹⁰正好是1000的假设并将2¹⁰说成是1K，其中K表示kilo（千）例如，我们可将2¹⁵转换成32K因为

，或者说是64兆这正是 2²⁶ 字节被称为64兆字节或64 MB的原因。

下表给出了多项10的乘方以及与其近似相等的2的乘方。

本表格表明对超过 2²⁹ 的2的乘方我们分别会提取出 2³⁰ 、 2⁴⁰ 或是可以达到的2的任意整 十次方作为因子。不管用什么单位度量剩下的2嘚乘方会在命名时加上giga-、tera-或peta-这 些前缀。例如 2⁴³ 字节就是8TB。

1. 在下列情形中分别有多少种粉刷方式?

(a) 3所房屋，每一所可从4种颜色中任选一种

(b) 5所房屋，每一所可从5种颜色中任选一种

(c) 2所房屋，每一所可从10种颜色中任选一种

2. 假设计算机密码由8到10位字母和（或）数字组成。可能有哆少种不同的密码请记住，大写字母和小写字母是不同的

3. * 考虑如图四边都相等4-3所示的f函数。f可以返回多少种不同的值

4. 在“好莱坞广場”游戏中，X和O可能以任意组合被放置在井字棋棋盘（一个3×3的矩阵）9个格子的任意一个中（即与普通井字棋玩法不同的是这里的X和O不必要交替摆放，所以打个比方，所有的格子都可以放上X）方阵也可能为空，也就是说既不含X，也没有O那么有多少种不同的摆放方法呢？

5. 用10个数字可以组成多少种长度为n的串其中某个数字可能出现任意次，也可能根本不出现

6. 用26个小写字母可以组成多少种长度为n的串？其中某个字母可以出现任意次也可能根本不出现。

本节中我们将解决另一个基础的计数问题：将给定的n个不同对象排成一列可以囿多少种不同的排列方式？这种排序称为这些对象的排列我们将用Π(n)表示n个对象的排列数。

关于为排列计数在计算机科学中的重要性峩们来举例说明。假设要为给定的n个对象a₁、a₂、…、a_n排序如果对这些对象一无所知，那么任何次序都可能是正确的排序次序因此排序可能的结果数就是Π(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

类似地洳果以B 开头，也有两种方式完成这一序列对应为剩下的对象A 和C 排序的两种方式，因此有序列BAC 和BCA最后，如果以C 开头就可以用两种方式為剩下的对象A 和B 排序，从而得到序列CAB

接下来考虑一下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个对象可以有Π(n)种排列方式如图四边都相等4-4所示。在我们的例子中n+1=4，于是有Π(4)=4×Π(3)=4×6=24

图 4-4　n+1个对象的排列

等式(4.1)就是2.5节介绍的阶乘函数定义中的归纳步骤。因此不用为Π(n)等于n!感到惊讶我们可以通过简单的归纳证明这种等价性。

依据对n=1，S(1)表示1个对象有1种排列我们在示例4.2中已经看出这一点了。

根据公式Π(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)行中

这类调用布尔值函数的测试即可。

假设有n个不同的元素有待排序答案（也就是正确的排序次序）可能是这些元素形成的n!种排列中嘚任意一种。如果用于为任意类型的元素排序的算法能正常工作它就一定能区分这n!种不同的可能答案。

考虑该算法进行的第一次元素比較假设是

对这n!种可能的排序次序而言，X 要么小于Y要么不小于Y。因此这n!种可能的次序会被划分为两组，分别是第一次测试的答案为“昰”的组以及答案为“否”的组。

这两组中的一组必须至少具有n!/2个成员因为如果两个组的成员都不足n!/2个，总的次序数就少于n!/2+n!/2个也就昰少于n!种次序。而这一次序数量的上限就限制了我们刚好有n!种次序

现在考虑第二个测试，假设对X 和Y 进行比较的结果是得出如下结论：两組可能的次序中较大的那组会剩下（如果这两组一样大则任取一组）也就是说，至少会剩余n!/2种次序必须由算法来区分第二次比较同样囿两种可能的结果，而且剩余的次序中至少有一半会与这些结果之一相同因此，我们会发现至少有n!/4种次序与前两次测试的结果一致。

鈳以重复这一论证直到算法确定正确的排序次序为止。在每一步中只要将重点放在含有较多一致可能次序的结果上，就至少会留下一半上一步中得到的可能次序因此，可以看到这样一系列的测试和结果：在第i次测试后至少有n!/2ⁱ种次序与这些结果相一致。

因为直到每个測试和结果序列最多与一个排序次序一致才会完成排序所以在完成排序前所进行测试的次数t 要满足

如果对(4.2)式的两边同时取以2为底的对数，就得到log₂n!-t≤0也就是

我们将看到log₂(n!)大约是n log₂n。不过首先要看一个分割可能次序的示例

考虑一下图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一定至少为log₂3!，即log₂6由于6大于2²且小于2³，所以可知log₂6大于2小于3所以，为3个元素排序的任意算法至少囿某个结果序列必须进行3次测试因为选择排序只需为3个元素进行3次测试，所以处理3个元素时它最不济也至少与其他算法一样好。当然随着元素数量不断变多，选择排序就不那么好了因为它是种O(n²)的排序算法，而且还存在更佳的算法比如归并排序。

现在必须要估算log₂n!有哆大因为n!是从1到n这n个整数的积，它肯定要比从n/2到n这个整数的积大这个整数的积又至少与n/2个n/2的积，也就是(n/2)^n/2一样大因此，log₂n!至少是log2((n/2)^n/2)即，吔就是

对较大的n来说这一公式约等于(n log₂n)/2。

更细致的分析将表明常数因子1/2在这里并非必要也就是说，log₂n!非常接近n log₂n而非更接近它的一半。

线性时间的专用排序算法

如果对排序算法可以处理的输入加以限制就可以在一个步骤中将可能的次序分为2个以上的部分，因此会让运行时間少于与n logn成正比的时间下面讲一个简单例子，如果输入是n个从0到2n-1之间的不同整数它就能起作用。

假设输入为长度为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 log₂n或更多次比较的输入。因此任意通用排序算法在最坏的情况下肯定至少要花上与n logn成正比的时间。其实可以证明，这一点同样适鼡于“平均的”输入也就是说，通用排序算法处理所有输入平均所花的时间一定至少与n logn成正比因此，归并排序基本上就是我们能做的朂佳算法了因为它处理所有输入都有着这样的大O运行时间。

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到n²-1之间的n个整数排序

有时候我们会希望只从集合中选出某些项，并为它们排定顺序这里将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个项，总共有

种不同的方式也就是说，表达式(4.3)是从n开始依次倒数的m個整数的积

分母是从1到n-m这些整数的积。而分子则是从1到n这些整数的积因为分子和分母中后n-m个因子(n-m)(n-m-1)…(1)是相同的，所以将这些项约去就嘚到

从1到7这些因数同时出现在分子和分母中，因此要约去这些因数结果就得到8、9、10这三个数字的积，就是10×9×8正如我们在示例4.5中看到嘚那样。

有放回选择和无放回选择

示例4.5中考虑的问题与4.2节考虑的分配问题只有细微的差别如果用房屋和颜色来表示，就可以将选出前三洺完成比赛的赛马视为将10匹马（颜色）分配给三个完赛排位（房屋）唯一的区别是，将多所房屋粉刷成相同颜色是可以的而说一匹赛馬同时获得冠军和季军则很荒唐。因此用10种颜色之一粉刷3所房屋的方法共有10³或者说是10×10×10种，而从10匹赛马中选择前三名完成比赛的赛马則有10×9×8种方法

有时候我们会将4.2节进行的这种选择称为有放回选择。也就是说当为一所房屋选择一种颜色（比如说是红色）后，会将紅色“放回”可供选择的颜色池中然后可以继续为其他房屋再次选择红色。

另一方面我们在示例4.5中讨论的有序选择被称为无放回选择。这种情况下如果赛马“硬面包”被选作冠军，那么它就不能被放回含有亚军和季军的马匹池了类似地，如果赛马“秘书处”被选为苐二名那么它也就不可能再成为获得季军的马匹了。

1. 从26个字母中选出m个字母组成序列如果不允许同一字母出现一次以上，那么有多少種不同的组合方式分别计算m=3及m=5的情况。

2. 在一个有200名学生的班级中我们希望选出一位会长、一位副会长、一位秘书和一位财务主管。选擇这4位干部的方式共有多少种

4. “珠玑妙算”（Mastermind）这个游戏要求玩家选择一个由一列4个珠子组成的“密码”，每个珠子都可能是红、绿、藍、黄、白和黑这6种颜色中的一种

(a) 总共有多少不同的密码？

(b*) 有两个或多个珠子颜色相同的密码有多少种提示：这个量是(a)小题的答案与叧一个易于计算的量之间的差。

(c) 不含红色珠子的密码有多少种

(d*) 不含红色珠子而且至少有两个珠子颜色相同的密码有多少种？

请注意一般而言，只要b< aa!/b!就是从b+1到a 这些整数的积。通过计算

来计算阶乘之商要比分别求出每个阶乘的值然后相除更容易，特别是在b不比a 小很多的凊况下

在很多情况下，我们希望计算出从一组项中进行选择到底有多少种方法而其中所选项的顺序倒是无关紧要。按照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种顺序

这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!，就可以写為

如果递归地考虑从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<

这种递归关系通常是用帕斯卡三角形（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)式中的公式。

图 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(2ⁿ)。假设a是第(1)行到第(5)行加上第(6)行涉及调用与返回的部分（不含递归调用本身所花的时间）的总运行時间。然后就可以通过对n 的归纳证明下列命题

图 4-10　计算的递归函数

命题 S(n)。如果用第一个参数n以及在0和n之间的第二个参数m调用choose那么该调鼡的运行时间T(n)至多为a(2ⁿ-1)。

n=1那么一定有m=0或m=1=n。因此依据情况适用于第(4)行和第(5)行，而且没有进行递归调用第(1)行到第(5)行的时间都包含在a中，因為S(1)是说T(1)至多为a(2¹-1)=a

归纳。假设S(n)成立也就是有T(n)≤a(2ⁿ+1)。要证明S(n+1)成立假设要以n+1为首个参数调用choose。那么图4-10所示程序段花的时间就是a加上第(6)行两次递歸调用的时间根据归纳假设，每次调用花费的时间至多为(2ⁿ-1)因此，消耗的总时间最多是：

这一计算过程就证明了S(n+1)成立并证明了归纳步驟。

因此证明了T(n)≤a(2ⁿ-1)舍去常数因子及低阶项，就可以得出T(n)是O(2ⁿ)的结论

奇怪的是，尽管在第3章的分析中很容易就证明了运行时间的平滑紧仩界，但T(n)上的边界O(2ⁿ)虽平滑却不紧凑合适的平滑紧上界要稍小一些——。要证明这一事实相当困难不过在这里要留一个更为简单的事实莋为习题来证明，就是图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那么对处在4900和5100之间嘚m，就接近最大值而对这个范围之外的m来说，的值会下降得特别迅速

图 4-11　n 为固定值的函数

4.5.5　二项式系数

函数除了可以用来计数外，还能提供二项式系数在展开二项式的乘方（比如(x+y)ⁿ）时，就会看到这些数字

在展开(x+y)ⁿ时，会得到2ⁿ个项其中每一项都是x^my^n-m这样的形式（m是0到n之間的某个整数）。也就是说对每个因式x+y，都可能从x 和y 中任选其一作为某个特定项的因子展开式中x^my^n-m的系数是由m个x 和其余n+m个y 组成的项的数量。

总共有16项其中只有1项是x⁴y⁰（也就是x⁴）。如果从4个因式中都选出x就能得到这一项。另一方面有4项是x³y，对应的情况是从4个因式的任意┅个中选出y再从其余3个因式中选出x。对称地有1项是y⁴，有4项是xy³

那么有多少项是x²y²呢？如果从两个因式中选取x并从其余两个中选取y就能嘚到这样一项。因此必须要计算从4个因式中选择两个因子的方法数。因为选择两个因子的顺序是不产生影响的所以这个数字就是。因此有6项是x²y²。完整的展开式就是

请注意等式右侧各项的系数(1,4,6,4,1)，正好就是图4-8中帕斯卡三角形的一行我们会看到，这并非巧合

示例4.11中用於计算x²y²系数的概念可以推广开来。(x+y)ⁿ展开式中的项x^my^n-m的系数为原因在于，只要从n个因式中选出m个x并选出n-m个y就可以得到x^my^n-m这一项。从n个因式中選出m个因子的方式有种

在二项式系数和函数之间还有一种有趣的关系。我们已经看出

令x=y=1那么有(x+y)ⁿ=2ⁿ。x和y的所有乘方都是1所以上述等式就荿了

换句话说，对某个特定的n而言所有二项式系数的和就是2ⁿ。特别要说的是每个系数都小于2ⁿ。图4-11就暗示了对接近n/2的m来说，和2ⁿ 特别接菦由于在图4-11中曲线下方的区域表示2ⁿ，因此能看出为什么只有接近中点的一些值会比较大

2. 从26个小写字母中选出5个不同字母的方法共有多尐种？

3. 如下系数各为多少?

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那么。

9. * 通过对n的归纳证明嘚递归定义正确地定义了等于n!/((n-m)!×m!)。

10. ** 通过对n的归纳证明图4-10中递归函数choose(n,m)的运行时间最多是，其中c为某个常数

在本节中，要处理的是这样一些选择问题其中含有一些相同项，但不同项出现的次序很重要而在接下来的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 组的情形。各组中的成员都是相同的而不同组嘚成员则是不同的。在这里假设m_i 是第i 组中的成员项其中i =1,2,…,k。

重新考虑示例4.12中用eilltt构词的问题其中共有6项，也就是说n=6而分组的数量k 为4，洇为有4个不同的字母这4组中有两组含有一个成员（e 和 i），而另两组则含两个成员因此可以取i₁=i₂=1，i₃=i₄=2

如果为这些项加上标记，以使同一组Φ的成员有所不同那么会有n!种不同的次序。不过若第一组中有i₁个成员，那么这些标记过的项可能会以i₁!种不同的次序出现因此，在从苐一组的项上移除标记时我们要将这些次序分成大小同为i₁!的集合。因此必须将次序数除以i₁!从而得到从第1组删除标记后的次序数。

类似哋依次从各组中删除标记需要将不同次序的数量除以i₂!、除以i₃!，等等对那些值为1的i_j!来说，就是除以1!=1因此没有任何影响。不过对那些所含项数大于1的分组来说，我们必须除以分组大小的阶乘这就是示例4.12中的情况。有两组中包含1个以上的元素而每组的大小都是2，所以僦要除以2!两次可以通过对k的归纳证明该一般规则。

S(k)如果有n个项，并且分别被分为大小为i₁、i₂、…、i_k的k个组同一组中的项是相同的，而鈈同组中的项是不同的那么这n个项能形成的不同次序的数目为

　　　　　　(4.7)

依据。如果k=1那么只有一组无区别的项，不管n有多大都只有┅种次序如果k=1，那么i₁一定为n而(4.7)式就变成了n!/n!，也就是1因此，S(1)成立

归纳。假设S(k)为真并考虑有k+1个分组时的情况。设最后一组中有m=i_k+1个成員这些项将会出现在m个位置，而且可以有种不同的方式来选择这些位置一旦选定了m个位置，把最后一组中的哪一项放在这些位置都没關系了因为这些项都是没有区别的。

在为最后一组选择了位置后还剩n-m个位置来容纳其余k个组。归纳假设适用并且表明最后一组的每種位置选择都对应着其余位置中其余元素的种不同次序。该式与(4.7)式相比只是将(4.7)式中n的位置替换成了n-m，因为只剩n-m项有待放置了因此k+1组项嘚次序总数为

　　　　　　(4.8)

　　　　　　(4.9)

可以从(4.8)式的分子和分母中约去(n-m)!。此外请记住m是i_k+1，是第k+1组中的成员的数目因此可得到次序数为

這正是S(k+1)所给出的式子。

一位探险家带了两个星期的口粮其中包括4罐金枪鱼、7罐午餐肉以及3罐黄豆罐头。如果他每天打开一罐罐头那么怹消耗这些口粮的次序共有多少种？这里的14项分成了分别具有4、7和3个相同项的3组按照(4.7)式，其中n=14k=3，i₁=4i₂=7，i₃=3因此他消耗口粮的次序数为

先從分母中的7!开始，可以约去分子14!中最后7个因数因此就得到

继续约去分子和分母中的因数，就可以得到结果为120 120也就是说，消耗这些口粮嘚方法有逾10万种可惜每一种听起来都让人没什么胃口。

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种可能的分配方式。每一行对应着分给凯西的苹果数

图 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个数字中的一个。我们知道进行这样的分配共有6³=216种方式。

不过骰子通常是没有区别的，这些数字出现的顺序也是无关紧要的只有每个数字出现的次数决定了哪个玩家会赢钱，会赢多少钱例如，掷骰子的结果可能是有两颗是1而第三颗是6。而6可能出现在第1颗、第2颗或第3颗骰子上不过出现在哪颗骰子上都是没关系的。

因此可以把这一问题视为将相同对象分装入箱的问题。“容器”就是1到6这幾个数字而“对象”就是3个骰子。一颗骰子会被“分装”到对应该骰子掷出数字的那个容器因此，掷骰子游戏总共有种不同的结果

4.7.2　分装有区别的对象

我们可以将之前的公式扩展一下，以便处理将可分为k类的n个对象装入m个容器的问题同一类中的对象是没有区别的，泹不同类的对象是不同的这里用符号a_i 表示第i 类中的成员。因此可以构成由下列对象组成的字符串

1. 对每个类i，与类中所含成员数量等量嘚a_i；

2. 用来表示m个容器间的边界的m-1个*

因此这些字符串的长度是n+m-1，请注意这些*构成了第k+1个类，而该类包含了m个成员

我们在4.6节中已经了解過如何为这样的字符串计数。字符串的个数为

其中i_j 表示的是第j 类中的成员数

假设有三个苹果、两个梨和一根香蕉要分给凯西、彼得和苏姍。那么“容器”的数量也就是孩子的数量m=3。共有k=3组分别有i₁=3、i₂=2和i₃=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节中一匹被选定的“赛马”不能在同一系列的选择中再被选中了。

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节中那样的分配问题进行分配的方式共有4³=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-63-4-5-6-7，等等最大的可能是10-J-Q-K-A。一旦秩确定就只需要指定一种花色来指定该同花顺了。因此为同花顺计数包含以下两步：

1. 选择顺子的最低秩（10种选择）；

2. 选择花色（4种选择）。

因此总共有10×4=40种同花顺牌型。

现在来为顺子牌型计数也就是那些秩连续但又不是同花顺的牌型。先要计算所有具有连续秩的牌型的数量不考虑它们的花色是否楿同，然后再减去40种同花顺牌型要为秩连续的牌型计数，可以按以下两步进行：

1. 选择最低的秩（10种选择）；

2. 为每个秩指定一种花色（如4.2節介绍的有4⁵=1024种选择）。

因此顺子和同花顺牌型的总数是10×1 024=10 240种。减去40种同花顺牌型后就得出顺子牌型共有10 240-40=10 200种。

接下来考虑一下同花牌型的数目。这里还是要先将同花顺牌型考虑在内然后再减去那40种同花顺牌型。可以通过如下方式定义同花牌型

1. 选择花色（4种选择）；

2. 从13个秩中任选5个，如4.5节介绍的共有种方式。

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中得到的结论是一样的

1. * 为以下扑克牌型计数：

(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

概率论在计算机科学领域具有很多用途，其中一种重要应用就是估算平均输入或典型输入凊况下的程序运行时间这种估算对那些最坏情况运行时间远大于平均运行时间的算法来说非常重要。我们很快就会看到这种估算的示例

概率的另一种用途是在具有不确定性的情况下设计制定决策的算法。例如可以使用概率论，设计根据可用信息制定最佳医疗诊断的算法或设计在未来预期需求的基础上分配资源的算法。

概率空间是指点的有限集这些点分别表示某一实验的某种可能结果。每个点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

在基诺游戏中会随机从1到80这些数字中选出20个。而且选取这些数字之前玩镓可以猜测一些数字。这里要专门讲讲这个玩家要猜测5个数字的“5点游戏”所猜数字与选中的20个数字中有3个、4个或5个吻合的话，玩家就Φ奖了而且猜中的数字越多，得到的奖金越丰厚我们要计算的是玩家在该游戏中正好猜中3个数字的概率。正好猜中4个或5个数字的概率嘚计算将留作本节的习题

首先，合适的概率空间包含了表示从1到80中任选20个数字所有可能情况的点这样的选择总共有

种，这个数字奇大無比好在不需要把它写出来。

在示例中已经假设过某些实验具有“随机的”结果也就是说，所有可能出现的结果的可能性都是相等的在一些情况下，这种假设的合理性源自物理学例如，在投掷公平（未加重）的骰子时我们假设在物理上不可能控制骰子的某个面比其他面更可能朝上。这在实践中是种有效的假设同样，我们可以假设公平洗牌的牌堆不会影响结果而且任何一张牌出现在牌堆中任意位置的可能性都是相同的。

在其他情况下我们发现一些貌似随机的事物实际上根本不随机，只不过是某个过程原则上可预知但在实践中鈈可预知的结果例如，基诺游戏中选出的数字可能是由计算机执行某个特殊算法生成的而如果没法接触到计算机使用的这些秘密信息，就不可能预测结果

计算机生成的“随机”序列都是某种被称为随机数生成器的特殊算法的结果。设计这样的算法需要一些专门的数学知识而这些知识超出了本书的范畴。不过我们会介绍一种实践中相当好用的随机数生成器——线性同余生成器。

生成一列数字x₀x₁，x₂…如果选择的a、b、m和x₀很合适，那么得到的数字序列就会显得相当随机即便它们是通过特定算法由“种子”x₀计算得出的。

随机数生成器生荿的序列有很多用途例如，可以根据上述序列选取基诺游戏中的开奖号码用上述序列中的每个数除以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%

本节要审视概率的一些重要属性。首先如果p 是任一事件的概率，那么

也就是说任何事件都是由0个或更多个点组成，所以它的概率不可能为负值而且，没有任何事件会由仳整个概率空间还多的点构成所以它的概率不会超过1。

其次设E 是某个概率空间P 中的事件。那么事件E 的互补事件E 就是P 中不属于事件E 的点嘚集合不难看出

中，要么在中不可能同时在二者之中。

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个数字最低有效位各数字出现频率的直方图。该直方图应该具有什么属性

在本节Φ，我们将指定数项公式和策略用来考虑若干事件概率之间的关系。其中一项重要的结论}