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

高中数学扩展

---

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

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

矩阵 — 更多模运算 — 数学规划 — 马尔可夫链

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

有序选择（排列）

假设您的音乐库中有 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 首不同的歌曲中选择一首作为第一个位置（或第一首播放的歌曲），从剩下的 9 首中选择一首作为第二个位置（因为已经选了一首歌曲），从剩下的 8 首中选择一首作为第三个位置（因为已经选了 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$

种方法可以安排 4 个人坐在圆桌旁。

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!}}$

我们使用了 m 个项目从 n 个项目中排列的公式，然后除以 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 乔伊仍然很饿，想再吃一份三明治。他可以用火腿、奶酪、萨拉米香肠、番茄和生菜（无需全部使用）。他不想在同一个三明治中放火腿和萨拉米香肠。乔伊可以制作多少种不同的三明治（三明治里配料的顺序无关紧要）？