组合学

13

可能每个读者«Kvant»都熟悉重大体育比赛之前的激动人心——无论是足球世界杯还是国际象棋的“世纪之战”。此外，从那些不太准确记住易位规则的人那里，你可以听到一些深思熟虑的替换，比如“我会把波特什而不是拉森放在世界队的第一板上。”国际象棋专家和球迷争论斯梅斯洛夫和凯雷斯之间的胜利机会，而球迷在讨论巴西和英格兰国家队之间的比赛可能结果时几乎大打出手。

通常，在此类比赛之前，报纸会宣布一场知识竞赛，要求猜测整个比赛的结果（预测谁将获得“黄金女神”，或者苏联国际象棋队将击败世界队的分数）和个人作品的结果。乍一看，赢得这样的比赛有一个非常简单的方法：向编辑发送尽可能多的信件给编辑，数量与理论上可能的比赛结果相同，并在每封信中给出一个选项。至少有一个字母会击中目标！

但事情并没有那么简单——有太多的选择。当然，如果你只需要预测本世纪比赛结束的比分，那么发送 81 个字母就足够了：进行了 40 场比赛，苏联国家队可以得到从 0（brrr…）到 40 之间的任意分数（那太好了！）。但是，如果您还需要在每个棋盘上指示比赛的结果（至少预测谁会获胜），那么可能的选项数量就会急剧增加。

在人类活动的各个领域中都会出现需要找到特定操作、特定事件的可能选项数量的问题。这些问题现在在学校被称为组合学，并且不被教授，而是作为选修课进行研究）。

1. 总和和乘积规则。解决组合问题的基础是两个简单的规则 - 正确的和和正确的乘积。

总和规则。如果我们有$m$种方法来选择元素$a$和（独立地）$n$种方法来选择元素$b$，那么可以用$m+n$种方法来选择“$a$或$b$”。

例如，如果盘子里有 5 个苹果和 9 个梨，那么可以通过 14 种方式选择“苹果或梨”——选择 5 个苹果中的一个或 9 个梨中的一个。

正确的工作有些困难。它涉及一对元素$(a, b)^*$的选择。

产品规则。如果我们有$m$方法来选择元素$a$和$n$方法来选择元素$b$，那么可以通过$mn$方法选择对$(a,b)$。

因此，如果盘子里有 5 个苹果和 9 个梨，那么可以以 $5\cdot 9=45$ 的方式选择这对（苹果，梨）。

*) 通过重新排列元素得到的两个对被认为是不同的，例如，对(1, 4)被认为与对(4,1)不重合。

14

为了验证乘积规则的有效性，我们用$a_1, \dots, a_m$表示所有选择元素$a$的方式，用$b_1, \dots, b_n$表示所有选择元素$b$的方式。然后，可以将这些元素组成的所有对排列在下表中的$m$行和$n$列中：

$$(a_1, b_1), \dots, (a_1, b_n),$$
$$(a_m, b_1), \dots, (a_m, b_n).$$

在此表中只有 $mn$ 个标准杆。

请注意，有时选择更复杂 - 您必须首先选择元素 $a$，然​​后根据此选择选择元素 $b$。但是，如果元素$a$可以通过$m$方式选择，并且每个元素都可以通过$n$方式选择，那么不同对的数量$(a, b)$又是$mn$。你自己证明一下。

当然，我们可能需要做出的不是两个选择，而是多个选择。在这种情况下，您需要检查每个选项的选项数量。换句话说，它正确地遵循了规则。

如果元素$a_1$可以通过$n_1$方式选择，元素$a_2$可以通过$n_2$方式选择，元素$a_k$可以通过$n_k$方式选择，则集合$(a_1, \dots, a_k)$可以通过$n_1 \dots n_k$方式选择（在这种情况下，仅通过元素的顺序彼此不同的集合被认为是不同的）。

现在我们已经可以解决世纪比赛可能结果的数量问题了。每个棋盘可能有 3 个结果：获胜、平局和失败。由于棋盘的数量是 10 个，因此可能有 $3^{10} = 59049$ 个不同的结果。如果你不仅需要想象每个获胜者的结果，还需要想象他的分数，那么答案将是$9^{10}$。

使用乘积规则，您还可以解决相当复杂的问题，其中对选项的选择施加了附加条件。

例子。俄语字母表中有 33 个不同的字母。如果不允许两个相同字母连续出现的单词，您可以组成多少个包含 5 个字母的单词？

当然，这里的“词”与语言学术语有不同的含义——像abbed或ababa这样的“词”是允许的。但像 quarrel、press、aachen 这样的词是不允许的 - 它们在一行中包含两个相同的字母。

为了解决这个例子，我们将逐个选择字母 - 首先是第一个，然后是第二个，第四个，第五个，然后以 33 种方式进行选择 - 毕竟，我们可以使用俄语字母表中的所有 33 个字母。但第二个字母只能有 32 种选择方式——毕竟它一定与第一个不同。您可以通过 32 种方式选择第三个字母 - 它必须与第二个字母不同；第四个和第五个字母也可以通过 32 种方式选择。总共我们得到$33 \cdot 32 \cdot 32 \cdot 32 = 34603008$个满足给定条件的不同单词。

2. k-子集。使用求和和乘积规则，您可以解决各种组合问题。但这并不总是方便，就像用公理解决任何几何问题并不总是方便一样。除了公理之外，我们还使用几何定理，这使我们能够缩短问题的解决方案。同样，在组合数学中，存在几个简单的“标准”问题，通常可以减少其他问题的解决方案。

这些问题是用集合论的语言表述的。如果读者不熟悉什么是“集合”、“集合的元素”、“集合的交集”、“集合的并集”，我们请他参考文献，文章末尾给出了文献列表。然而，我们将仅使用最简单的集合论概念，这些概念现在将在高中四年级和五年级学习，作为示例，我们将采用四个元素的集合，并选择由该集合的元素组成的子集和单词（图 1-5）。

15

图 1. 令集合$N$由四个元素组成：马、象、后、车。

我们来解决下面的问题。 5名学生参加游泳考试。如果学生游过 100 米（任何时间），则测试通过。如果学生来抓他，那么考试就没有通过。一次游泳可以有多少种方式结束？

各种情况都是可能的。可以假设所有学生都是游泳健将，或者可能所有五个学生都必须获救。结果总数可以这样计算。让我们按字母顺序排列所有学生：Andreev、Borisov、Voldin、Grigoriev、Dmitriev。对于他们每个人来说，都有两种可能性——要么通过测试，要么没有通过。在第一种情况下，我们将数字 1 分配给该学生，在第二种情况下，我们将数字 0 分配给该学生。然后游戏的结果将表示为由 0 和 1 组成的长度为 5 的序列。例如，序列 0, 1, 1, 0, 1 表示只有鲍里索夫、沃尔丁和德米特里耶夫游得足够好。如果只有格里戈里耶夫参加测试，那么比赛结果的报告将如下所示：0,0,0,1,0。序列0,0,0,0意味着没有一个学生到达终点线。

这样，游戏结果数的问题就简化为：从数字0和1中可以算出多少个长度为5的序列？这个问题的答案是由正确的乘积给出的：因为在序列中的每个位置我们都有两种可能性的选择，那么结果的总数是$2 \cdot 2 \cdot 2 \cdot 2 = 32$。因此，游泳有 32 种可能的结果。

在分析的问题中，我们需要找出集合$N$中可以算出多少个子集：{Andreev，Borisov，Voldin，Grigoriev，Dmitriev}。

在这种情况下，允许有一个空子集，以及与整个集合$N$一致的子集。结果答案是$32 = 2^5$。同理证明，如果一个集合$N$包含$n$个元素，则它有$2^n$个子集。使用数学归纳法可以证明相同的结果。

在奥运会上他们是这样做的：前两名晋级决赛。我们来看看在这种情况下比赛能有多少种结果。从数学上讲，该问题表述如下：您可以通过多少种方式从包含 5 个元素的集合中选择 2 个元素？很容易检查是否可以通过 10 种方法来完成（自己写下所有这些方法）。但这种“直接搜索”的方式只适合少数参与者。我想要一个可以让我立即回答问题的公式。所以，我们需要解决以下问题。

$n$元素的集合$N$中有多少个$k$子集？

为了简洁起见，这里我们将“$k$子集”与“包含$k$元素的子集”一起说。

从给定集合$N$中选择子集可以通过以下方式找到。我们把集合$N$的元素放进一个袋子里，然后把手伸进这个袋子里，拿出一个子集。当然，子集的所有$k$元素都会被一次性取出，无法为它们建立合理的顺序。

18

图 5. 集合$N$的元素有$P_4=4!=24$排列。

有必要从其中一一提取出该集合的元素。但这次我们不会将这些元素放回包中，而是将它们排成一排。在 $k$ 选择之后，我们将再次获得 $k$-单词 $(a_1, \dots, a_n)$，但这次元素之间没有重复项 $a_1, \dots, a_n$ *)。换句话说，我们可以说$k$-没有重复的单词被排序为$k$-集合$N$的子集。

没有重复 $n$ 元素的$k$-单词的数量由 $A_n^k$ 表示。从产品规则可以立即得出：

$$A_n^k=n(n-1)\dots(n-k+1).$$

事实上，第一个元素可以以 $n$ 的方式选择，第二个元素只能以 $n-1$ 的方式选择，因为你不能获取已经选择的元素。第三个元素可以通过 $n-2$ 方式、…、$k-1-(n-k+1)$ 方式选择。

*) 这样的$k$-单词被称为没有重复的位置。

这意味着实数路的总数由公式(3)表示。

例如，如果在委员会的 10 名成员中需要任命一名代表、一名替代者和一名秘书，则可以通过$10\cdot 9\cdot 8\cdot 720$ 方式完成。

5. 重新安排。如果将集合$N$的元素从袋子中取出并排成一排（并且没有返回一个元素），那么最终集合$N$的所有元素都会按某种顺序定位。在这种情况下，我们讨论不重复 $n$ 元素的排列。因此，$n$元素的排列是一个$k$字，没有重复的$n$元素。式（3）$k=n$中的Polyag，我们发现$n$元素的排列数为$n!$。用符号$P_n$表示。所以，

$$P_n=n!$$

6. 具有重复的排列。我们已经知道从$n$“字母”我们可以