计数原理

此页面文字抄袭自剑桥大学出版社出版的《IB 文凭数学高级水平》一书。此处文字应删除。

学习目标

能够将复杂的计数问题分解成更容易计数的步骤，然后将它们组合在一起，
能够计算排列一组对象的排列方式数量，
能够使用称为阶乘函数的有用新工具的代数性质，
知道从一组对象中选择对象的多少种方法，以及
知道将这些工具应用于更难问题的各种策略。

简介

计数是数学中最早学习的内容之一，乍一看似乎非常简单。如果有人被要求计算学校里有多少人，这将不是一项非常棘手的任务。如果有人被要求计算如果每个人都要与其他人比赛，需要进行多少场比赛，这会稍微复杂一些。如果有人被要求计算可以选出多少支不同的足球队，可能会发现数量太大而无法计算，因此需要想出一些巧妙的技巧。本章旨在帮助发展在如此困难的情况下进行计数的策略。

乘积原理和加法原理

菜单

主菜

披萨
汉堡
西班牙海鲜饭

甜点

冰淇淋
水果沙拉

对非常小的群体进行计数很容易。因此，需要将更复杂的问题分解成对小群体进行计数。但如何将这些计数组合在一起才能得出整体问题的答案呢？答案在于使用乘积原理和加法原理，可以使用以下菜单来进行说明。

安娜想点一道主菜和一道甜点。她可以选择三种主菜中的一种和两种甜点中的一种。她可以做出多少种不同的选择？鲍勃想点一道主菜或一道甜点。他可以选择三种主菜中的一种或两种甜点中的一种；他可以做出多少种不同的订单？

我们可以使用符号 $n(A)$ 表示对 $A$ 进行选择的种数。

乘积原理 允许从 $A$ 中选择一个选项并从 $B$ 中选择一个选项，那么需要将各个可能性相乘。

乘积原理（AND 规则）进行选择 $A$ 和选择 $B$ 的种数是选择 $A$ 的种数与选择 $B$ 的种数的乘积。

$n(A{\text{ AND }}B)=n(A)\times n(B)$

加法原理 如果要从 $A$ 中选择一个选项或从 $B$ 中选择一个选项，那么结果就是将可能性相加。

加法原理有一个重要的限制。只有当选择 $A$ 和选择 $B$ 之间没有重叠时，才能使用它。例如，不能用加法原理来计算骰子上出现奇数或素数的次数。如果选择 $A$ 和选择 $B$ 之间没有重叠，这两个事件是互斥的。

加法原理（或规则）选择 $A$ 或选择 $B$ 的方法数量是 $A$ 选项数量与 $B$ 选项数量的总和。

如果 $A$ 和 $B$ 是互斥的，那么

$n(A{\text{ OR }}B)=n(A)+n(B)$

应用加法原理或乘法原理最难的部分是分解问题，并决定使用哪个原理。人们必须自查确保所有情况都被检查过，并确保它们是互斥的。通常，将方程式改写以强调需要什么，'AND' 或 'OR'，会有所帮助。

从 $n$ 个对象中选择某个东西 $r$ 次的方法数量是 $n^{r}$ 。

排列的计数

单词 'ARTS' 和单词 'STAR' 都包含相同的字母，但排列顺序不同。它们都是字母 R、A、T 和 S 的排列（也称为排列）。可以计算出不同排列的数量。

第一个字母有四种可能性，然后对于每个第一个字母的选择，第二个字母有三种选择（因为一个字母已经被使用过了）。这给第三个字母留下了两种选择，然后最后一个字母就被固定了。使用 'AND 规则'，可能的排列数量是 $4\times 3\times 2\times 1=24$ 。

$n$ 个不同对象的排列数量等于小于或等于 $n$ 的所有正整数的乘积。这个'表达式缩写为 $n!$ （读作 'n 阶乘'）。

排列指将一组对象按特定顺序排列的方式。排列 $n$ 个对象的方法数量为 $n!$

$n!=n(n-1)(n-2)...\times 2\times 1$

阶乘的代数

要解决更复杂的计数问题，通常需要简化涉及阶乘的表达式。这可以通过使用阶乘公式来完成，

$n!=n(n-1)(n-2)...\times 2\times 1$

然后继续寻找各项的公因数。理解一个阶乘与下一个阶乘之间的联系很重要

$(n+1)!=(n+1)\times n!$

能够简化涉及 $n!$ 的表达式很有用，因为 $n!$ 很快就会变得非常大。通常，即使使用计算器也无法计算阶乘。例如，标准科学计算器只能计算到 $69!=1.71\times 10^{98}$ （保留三位有效数字）。

选择计数

假设从一个有 11 名学生的班级中选出 3 名学生参加与校长会面。可以选出多少种不同的三个人小组？

在这个例子中，需要从 11 名学生中选择 3 名学生，但他们不必按照任何指定的顺序排列。顺序不重要；例如，选择阿斯帕西亚、弗里妮，然后拉哈布与选择弗里妮、拉哈布，然后弗里妮是一样的。这种选择被称为组合。一般来说，从 $n$ 个对象中选择 $r$ 个对象的方法数量用符号 ${n \choose r}$ 或 $^{n}C_{r}$ （读作“n C r”或“从 n 个中选 r 个”）表示。

组合指选择一组对象的方式，其中顺序无关紧要。从 $n$ 个对象中选择 $r$ 个对象的方法数量为

${n \choose r}={\frac {n!}{r!(n-r)!}}$

排除原则

排除原则是一种通过先计算不感兴趣的事物来计算感兴趣的事物的方法。这通常用于计算某些属性被禁止（不允许）的情况。

排除原则通过先计算所有不满足条件的结果，然后从总结果数中减去它，来计算满足给定条件的结果数。

想象一下，使用数字 1-5 中的每一个数字恰好一次来形成一个五位数的代码。如果要计算有多少个此类代码不以“25”结尾，可以算出所有不以“25”结尾的可能选项。这个方法有效，但很长很复杂。更简单的方法是使用排除原则。

计算有序选择

有时，需要从一个更大的组中选择一些对象，但选择的顺序很重要。例如，找到比赛中前三名选手的可能性，或从一组固定的数字中形成数字。处理这些情况的策略是，首先从更大的组中选择，然后排列所选对象。

假设整个集合的大小为 $n$ ，并且要选择和排序大小为 $r$ 的子集。执行此操作的方法数量用符号 $^{n}P_{r}$ 表示，并被描述为“从 $n$ 个对象中排列 $r$ 个对象的方法数”。可以使用公式 ${n \choose r}$ 推导出 $^{n}P_{r}$ 的公式：有 ${n \choose r}$ 种方法可以从主题中选择对象，并且这些对象可以以 $r!$ 种方法排列。因此，

$^{n}P_{r}={n \choose r}\times r!$

或者，类似地

$^{n}P_{r}={\frac {n!}{(n-r)!}}$

这可以使用阶乘代数写成

$^{n}P_{r}=n(n-1)(n-2)\ldots (n-r+1)$

以这种形式写出来，我们可以看到公式 $^{n}P_{r}$ ，是“与规则”的应用。例如，假设一场比赛有五个人，你想计算前三名的可能性数量。我们可以这样推理：如果获胜者有五种选择，那么对于每个获胜者，第二名有四种选择，第三名有三种选择。这给了我们 $5\times 4\times 3=^{5}P_{3}$ 。

保持物体在一起或分开

单词“SQUARE”有多少种字母排列方式可以使Q和U相邻？有多少种方式可以使元音字母全部分开？当一个问题有像这种约束条件时，我们需要一些巧妙的技巧来处理它们。

我们将要观察的第一类问题是，物体被强迫保持在一起。诀窍是想象单词“SQUARE”中的字母是写在瓷砖上的。如果Q和U需要在一起，我们实际上就是在处理五块瓷砖，其中一块包含QU。

S	QU	A	R	E

我们还必须记住，如果Q和U的顺序相反，也满足条件。

S	UQ	A	R	E

另一种约束条件是，物体必须保持分开。除非我们只分开两个物体，否则这不是物体保持在一起的反面。例如，三个物体保持在一起的反面包括两个在一起，第三个分开。所以，当处理“保持物体分开”时，我们需要关注关键物体可以放入的空隙。

考虑单词“SQUARE”有多少种排列方式，其中元音字母都不在一起。我们首先要排列所有辅音字母。其中一种排列方式是

*	S	*	Q	*	R	*

其中* 是可以放置元音字母的空隙。我们只有三个元音字母，所以只需要选择三个空隙，然后决定以什么顺序插入元音字母。