高中数学扩展/补充/基本计数

高中数学扩展

---

补充章节 — 质数和模算术 — 逻辑

数学证明 — 集合论和无限过程 — 计数和生成函数 — 离散概率

矩阵 — 进一步模算术 — 数学规划 — 马尔可夫链

补充章节
内容
基本计数
多项式除法
部分分数
求和符号
复数
微分
问题与项目
问题集
解答
练习解答
问题集解答

有序选择 (排列)

假设你的音乐库中有 10 首歌曲，你想要随机播放所有歌曲（即这 10 首歌曲会以随机顺序播放）。你的音乐库可以有多少种不同的播放方式？

这种类型的题被称为有序选择（排列），因为我们是在选取音乐库中的歌曲并以特定顺序进行播放。例如，以下这些选择被认为是不同的：

${\begin{array}{l}1,2,3,4,5,6,7,8,9,10\\7,3,10,4,9,5,1,8,2,6\\2,1,3,4,5,6,7,8,9,10\end{array}}$

这些明显地定义了不同的播放顺序，或实际上，不同的播放列表。

让我们逐步思考。我们可以从 10 首不同的歌曲中选择 1 首放在第一个位置（或播放的第一首歌曲），从剩下的 9 首歌曲中选择 1 首放在第二个位置（因为已经选了 1 首），从剩下的 8 首歌曲中选择 1 首放在第三个位置（因为已经固定了 2 首），以此类推。总的播放方式可以计算如下：

$10\times 9\times 8\times 7\times 6\times 5\times 4\times 3\times 2\times 1$

将近 400 万种不同的播放列表！

现在我们将介绍阶乘函数，它是一种表达以下内容的简便方法：

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

正式定义为：

${\begin{array}{l}0!=1\\n!=n\times (n-1)!\end{array}}$

因此，在我们的例子中：

${\begin{array}{l}10!=10\times 9!=10\times 9\times 8!...\\10\times 9\times 8\times 7\times 6\times 5\times 4\times 3\times 2\times 1\end{array}}$

如果我们有 30 首歌曲，但仍然只想要随机播放其中的 10 首呢？类似的推理得出以下结论：

$30\times 29\times 28\times 27\times 26\times 25\times 24\times 23\times 22\times 21$

种不同的方式。这等同于：

${\frac {30!}{20!}}={\frac {30!}{(30-10)!}}$

     注意！阶乘函数不对加法或乘法进行分配。

一般来说，从n个项目中选取m个项目的排列数量（例如，从 30 首歌曲中选取 10 首）为：

${\frac {n!}{(n-m)!}}$

其背后的原理是我们取消了n!乘积中除前m个因子以外的所有因子：

$30!=\underbrace {30\times 29\times ...\times 22\times 21} _{\text{First 10 factors}}\times \underbrace {20\times ...\times 2\times 1} _{(30-10)!=20!}$

当m等于n时，我们说我们是在计算n个项目的排列数量。

${\frac {n!}{(n-n)!}}={\frac {n!}{0!}}=n!$

在解决计数问题时，我们通常会使用“项目”或“元素”（在本例中为歌曲）以及“集合”（在本例中为集合或播放列表）这些词。

1. In how many ways can I arrange my bookshelf (7 books) if I own a trilogy and the 3 books have to be always together, in the same order?

2. In how many ways can I arrange my family (6 members) in a line, with the only rule that my parents have to be in adjacent positions?

排列（有重复）

用奇素数（即3、5或7）可以组成多少个不同的两位数？75、37、77、33都是可能的解。

这是一个排列的特殊情况，项目可以选择多次。通过计数，我们发现每个位置有3种可能性，因为数字可以重复。

$\underbrace {3\times 3} _{\text{2 positions}}=3^{2}$

9个不同的数字。

如果我们要从n个项目中选择m个，并且可能重复，那么会有

$\underbrace {n\times n\times n...\times n} _{\text{m times}}=n^{m}$

排列。

1. How many three-digit numbers can be formed with only prime digits, and odd digits may only be repeated twice?

环形排列

我们可以用多少种方法让4个人（爱丽丝、鲍勃、查尔斯和唐纳德）围坐在一张圆桌旁？

这也是排列的另一种特殊情况，4个元素以环形顺序排列，排列的起点和终点是未定义的。

如果我们简单地计算

$4!$

将会有一些重复。我们将重复计算每个独特的排列，因为像

${\begin{array}{l}{\text{A, B, C, D}}\\{\text{D, A, B, C}}\\{\text{C, D, A, B}}\\{\text{B, C, D, A}}\end{array}}$

被认为是等价的。请记住，圆桌没有起点。

     有4个人椅子和4组等价排列，这并非巧合。

如果我们任意给椅子编号，我们可以通过循环整个布局来获得所有等价的排列。我们会循环多少次？有多少个椅子/位置？4个。

将我们的第一个意图除以4（即将4个等价布置分组）

${\frac {4!}{4}}=3!$

6个唯一的布置。

另一种方法是强制定义布局的任意起点，换句话说，固定一个元素并排列剩下的3个元素

$(4-1)!=3!=6$

方法让四个人围坐在一张圆桌旁。

1. What if there are 7 people, but the table only has 5 chairs?

无序选择（组合）

在数学课的15名学生中，将选出5名学生代表班级参加全校数学竞赛。有多少种方法可以选择这5名学生？

这种类型的问题称为无序选择（组合），因为选择学生的顺序并不重要。例如，以下选择被认为是等价的

${\begin{array}{l}{\text{Joe, Lee, Sue, Violet, Justin}}\\{\text{Lee, Joe, Sue, Justin, Violet}}\end{array}}$

如前所述，有

${\frac {15!}{10!}}$

种方法以有序选择方式选择5名候选人，但对于每个不同的组合，有5！种有序选择（即相同的5名学生）。这意味着我们为每个组合都计算了5！次。因此，有

${\frac {15!}{10!\times 5!}}$

种方法选择5名学生代表班级。

一般来说，从n个项目中选择m个项目的种数为

${\frac {n!}{(n-m)!\times m!}}$

我们拿出了从 *n* 个项目中选出 *m* 个项目的排列公式，然后除以 *m*!，因为每个组合都被计算了 *m*! 个有序的选择（*m*! 次）。

这个公式用以下符号表示：

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

注意，${n \choose m}$ 通常读作 *从 n 中选 m*。

1. Try not to use a calculator and think of the problem with groups of 1 student.

2. Again, no calculator and this time there are 1 million students in the class and we want to form groups of 999,999 students.

重复组合

在这种特殊的组合问题情况下，元素可以被选择多次。也就是说，组可以包含同一个元素的多个样本。

知道哪些元素被采样不足以定义一个选择，我们需要知道 **每个元素被选择的次数** （即该元素被选择的样本数量）。本质上，这两种方法是相同的，因为说一个元素被选择了 0 次等同于说它没有被采样。

现在假设我们要从 *n* 个元素中选出 *m* 个元素。我们不应该把这个问题看成是 "从 *n* 个元素中选择 *m* 次"，而应该把它看成是 "将 *m* 个可用位置分配给 *n* 个不同的元素"（表示将 *m* 个元素放入 *n* 个集合中）。同样，这两种解释是等效的，因为元素被选择的次数由其对应集合中元素的数量表示。

为了定义一个选择，我们把每个集合中放入了与我们从该集合所代表的元素中选择的样本一样多的对象。我们可以创建一个字符串来标识选择，例如用一个方块来表示每个对象（样本），用一个短横线来表示集合边界

$-\underbrace {{\blacksquare }{\blacksquare }{\blacksquare }} _{\text{First set/element}}-\underbrace {{\blacksquare }{\blacksquare }} _{\text{Second set/element}}-\underbrace {{\blacksquare }{\blacksquare }} _{\text{Third set/element}}-$

这意味着三个位置被分配给第一个元素，两个位置被分配给第二个元素，两个位置被分配给第三个元素。换句话说，该选择包含三个第一类元素，两个第二类元素，两个第三类元素。该字符串可以代表一个随机的五个字母组成的字母组，仅包含字母 A，B，C

${\text{A, A, A, B, B, C, C}}$

连接的字符串由 *m* 个方块和 *n + 1* 个短横线组成。例如，以下代表从五个元素中选出的三个元素

$-\underbrace {{\blacksquare }{\blacksquare }} _{\text{First set/element}}-\underbrace {} _{\text{Second set/element}}-\underbrace {\blacksquare } _{\text{Third set/element}}-\underbrace {} _{\text{Forth set/element}}-\underbrace {} _{\text{Fifth set/element}}-$

注意，除了固定在字符串开头和结尾的两个短横线外，其他 *n - 1* 个短横线和 *m* 个方块可以移动，而不会使字符串无效。因此，在 *n - 1 + m* 个位置中，有 *n - 1 + m* 个可移动字符。可能的字符串数量等于将 *m* 个方块放在 *n - 1 + m* 个字符中的方法数量，换句话说，是从 *n - 1 + m* 个位置中选出 *m* 个位置的方法数量

${{n-1+m} \choose {m}}$

等效地，我们可以谈论将 *n - 1* 个短横线放在 *n - 1 + m* 个字符中的位置

${{n-1+m} \choose {n-1}}$

由于每个字符串都独一无二地确定一个选择或组，因此字符串的数量显然等同于可能的组或选择的数量。

如果我们要为长途旅行打包三种水果，而你只有香蕉、苹果、橙子、桃子和奇异果，那么会有

${{5-1+3} \choose {3}}={{5-1+3} \choose {5-1}}=35$

可能的打包组。

二项式系数

二项式系数

${n \choose m}$

表示从包含n个元素的集合中选择m个元素可以形成的无序组的数量。

以下是一些基本且有用的属性

• 从n个元素中选择m个元素的方式数量等于从n个元素中选择n-m个元素的方式数量，因为每个选定元素组都有一个相应的未选定元素组。选定元素组定义了另一个未选定元素组。

${n \choose m}={n \choose {n-m}}$

• 只有一种方法可以选择所有元素或不选择任何元素。

${n \choose 0}={n \choose n-0}=1$

• 有n种方法可以选择1或n-1个元素。

${n \choose 1}={n \choose {n-1}}=n$

• 之间的差异

${n \choose m}$

和

${{n+1} \choose m}$

在于第一个公式没有计算包含在第二个公式中添加的元素的组。包含来自包含n+1个元素的集合中的特定元素的m大小的组的数量是

${{(n+1)-1} \choose {m-1}}={n \choose {m-1}}$

因此

${{n+1} \choose m}={n \choose m}+{n \choose {m-1}}$

• 之间的差异

${n \choose {m+1}}$

和

${n \choose m}$

在于第一个公式计算的组比第二个公式计算的组多一个元素。每个m大小的组需要n-m中剩余的“缺失”元素中的一个才能增长到m+1大小。

${n \choose m}\times (n-m)$

但是，我们必须观察到我们多次计算每个m+1大小的组，实际上是m+1次。这是因为“缺失”的元素可以是结果组中的m+1个元素中的任何一个，换句话说，m+1个m大小的组（当与正确的元素关联时）将形成同一个m+1大小的组。从m+1大小的组中移除一个元素可以形成多少个m大小的组？

${{m+1} \choose 1}=m+1$

这表明

${n \choose {m+1}}={n \choose m}\times {\frac {n-m}{m+1}}$

二项式展开

二项式定理描述了以下表达式的代数展开

$(a+b)^{n}$

例如，取 *n* = 2，我们将尝试手动展开表达式，得到

$(a+b)^{2}=(a+b)(a+b)=aa+ab+ba+bb$

取 *n* = 3

$(a+b)^{3}=(a+b)(a+b)(a+b)=aaa+aab+aba+abb+baa+bab+bba+bbb$

在展开过程中，我们故意没有对表达式进行简化。正如你所看到的，最终展开的形式分别有四项和八项。这些项都是 *a* 和 *b* 在两个和三个因子的乘积中所有可能的组合。

因子的数量等于第一个乘积中二项式 *(a + b)* 的数量，而这反过来又等于 *n*。

在

$(a+b)^{n}$

中，每一项都有 *n* 个因子。有多少项只有一个 *b*？换句话说，我可以在 *n* 个不同位置中放置一个 *b* 有多少种方法？或者更好的是，我可以在 *n* 个位置中选择一个位置（放置一个 *b*）有多少种方法？

${n \choose 1}$

类似地，我们可以计算出其他所有项的系数

$(a+b)^{3}={3 \choose 0}a^{3}+{3 \choose 1}a^{2}b+{3 \choose 2}ab^{2}+{3 \choose 3}b^{3}$

更一般地说

$(a+b)^{n}={n \choose 0}a^{n}+{n \choose 1}a^{n-1}b+{n \choose 2}a^{n-2}b^{2}+...{n \choose n-1}ab^{n-1}+{n \choose n}b^{n}$

或者更简洁地使用求和运算符

$(a+b)^{n}=\sum _{i=0}^{n}{n \choose i}a^{n-i}b^{i}$

练习

1 用单词“BOOK”的字母可以排列出多少种不同的方式？

2 从一副牌中选出五张方块牌有多少种方法？

3 乔伊想给自己做三明治。他将使用火腿、奶酪、萨拉米香肠、番茄和生菜，但他不喜欢火腿和萨拉米香肠互相接触。他总是把生菜放在最上面。乔伊可以用多少种方法排列他三明治的配料？

4 瑞秋想买一杯冰淇淋。她从十种不同的口味中选择了三种，但她不喜欢将巧克力与香草混合。瑞秋可以点多少种不同的冰淇淋？

5 乔伊仍然很饿，想吃另一个三明治。他可以使用火腿、奶酪、萨拉米香肠、番茄和生菜（不必全部使用）。他不想在同一个三明治中放火腿和萨拉米香肠。乔伊可以做多少种不同的三明治（三明治中配料的顺序无关紧要）？