概率/组合学

我们都知道如何计数。然而，计数实际上可能相当复杂，并且存在许多与计数相关的复杂技术。在本章中，我们将介绍一些基本技术，这些技术是计算组合概率（在下一章中讨论）的基础。这些技术大量使用基本计数原理，在下一节中讨论。

基本计数原理

就像数学中有四种基本运算：加法、减法、乘法、除法一样，计数中也有四种相应的基本原理：加法、减法、乘法、除法计数原理。

加法和减法计数原理

命题. (加法计数原理) 如果有$n_{1}$ 种方法可以完成任务 1，以及$n_{2}$ 种方法可以完成任务 2，但是 我们不能同时完成两个任务，那么我们有 $n_{1}+n_{2}$ 种方法可以完成任务 1 或任务 2。

备注.

• 在集合论术语中，这意味着如果 $A$ 和 $B$ 是不相交的有限集（分别包含完成任务 1 和 2 的方法），则 $|A\cup B|=|A|+|B|$.

更一般地，我们有减法计数原理

命题。 （减法计数原理） 如果有 $n_{1}$ 种方法完成任务 1，并且有 $n_{2}$ 种方法完成任务 2，并且 有 $n_{3}$ 种方法同时完成两个任务，那么我们有 $n_{1}+n_{2}-n_{3}$ 种方法完成任务 1 或 任务 2。

备注.

• 解释：由于 $n_{1}+n_{2}$ 包含 了过多的方法（一些方法被重复计算），我们需要 排除 这些重复计算的方法 ($n_{3}$ 个)。
• 令 $n_{3}=0$ ，则得到加法计数原理。
• 用集合论的术语来说，这意味着如果 $A$ 和 $B$ 是有限集（分别包含完成任务 1 和 2 的方法），那么 $|A\cup B|=|A|+|B|-|A\cap B|$.
• 请注意，完成任务 1 或 任务 2 包含了同时完成两个任务的可能性。也就是说，“或” 是包含的。在数学中，“或” 通常被认为是包含的。

实际上，前面提到的两个计数原理只是更一般原理的特殊情况：包含-排除原理。

定理。 （容斥原理）设 $n$ 是一个正整数， $S_{1},S_{2},\dotsc ,S_{n}$ 是有限集。 那么，它们的并集的基数为 $${\begin{aligned}|S_{1}\cup \dotsb \cup S_{n}|&=|S_{1}|+|S_{2}|+\dotsb +|S_{n}|\\&\quad -{\big (}|S_{1}\cap S_{2}|+|S_{1}\cap S_{3}|+\dotsb +|S_{n-1}\cap S_{n}|{\big )}\\&\quad +{\big (}|S_{1}\cap S_{2}\cap S_{3}|+|S_{1}\cap S_{2}\cap S_{4}|+\dotsb +|S_{n-2}\cap S_{n-1}\cap S_{n}|{\big )}\\&\quad -\dotsb \\&\quad +(-1)^{n+1}|S_{1}\cap S_{2}\cap \dotsb \cap S_{n}|\\\end{aligned}}$$

备注.

• “容斥原理”这个名字来源于这个原理基于 过度包含，然后进行 补偿排除。 我们重复包含和排除过程，直到包含完全准确。
• 我们可以认为集合 $S_{1},S_{2},\dotsc ,S_{n}$ 包含完成任务 1,2,...,$n$ 的方法。 然后，并集 $S_{1}\cup S_{2}\cup \dotsb \cup S_{n}$ 包含完成任务 1,2,... 或 $n$ 的方法。

示例。（容斥原理的特殊情况）当 $n=2$ 时，容斥原理给出 $$|S_{1}\cup S_{2}|=|S_{1}|+|S_{2}|-|S_{1}\cap S_{2}|.$$ 当 $n=3$ 时，容斥原理给出 $$|S_{1}\cup S_{2}\cup S_{3}|=|S_{1}|+|S_{2}|+|S_{3}|-|S_{1}\cap S_{2}|-|S_{1}\cap S_{3}|-|S_{2}\cap S_{3}|+|S_{1}\cap S_{2}\cap S_{3}|.$$

示例。在 140 个人中，有 110 人至少会说英语、法语或德语。已知

• 90 人会说英语，30 人会说法语，42 人会说德语；
• 23 人会说英语和法语；
• 25 人会说英语和德语；
• 16 人会说法语和德语。

求会说英语、法语和德语的人数。

解答. 设 $E$、$F$、$G$ 分别表示会说英语、法语和德语的人的集合。那么，根据容斥原理，$$|E\cup F\cup G|=|E|+|F|+|G|-|E\cap F|-|F\cap G|-|E\cap G|+|E\cap F\cap G|\implies 110=90+30+42-23-29-16+|E\cap F\cap G|\implies |E\cap F\cap G|=12.$$ 因此，会说英语、法语和德语的人数为 $110-90-30-42+23+25+16=12$.

韦恩图

*----------------*
|90-13-12-11=54  | <---- E
|      *---------*--------------*
|      |25-12=13 |42-13-12-4=13 | <--- G
*------*---------*--------------*-----*
|      |   12    |16-12=4       |     |
|      *---------*--------------*     | <--- F
|  23-12=11      |  30-11-12-4=3      |
*----------------*--------------------*
  140-110=30

练习。

1 求会说（a）只有英语的人数；（b）只有法语的人数；（c）只有德语的人数。

	(a) 90; (b) 30; (c) 42
	(a) 54; (b) 13; (c) 3
	(a) 54; (b) 11; (c) 3
	(a) 54; (b) 3; (c) 11
	以上都不对。

2 假设在现在的 140 人中，有 $k$ 人学会说英语。计算 $k$ 使得其中 123 人至少会说英语、法语或德语中的一种，并且现在有 20 人会说英语、法语和德语。

	20
	21
	22
	23
	以上都不对。

3 从上一题继续。计算现在会说英语和法语的人数。

	23
	31
	36
	44
	以上都不对。

乘法计数原理

定理. (乘法计数原理)

一个树状图说明了这个概念。

设 $n$ 是一个正整数。如果做任务 $1,2,\dotsc ,n$ 分别有 $m_{1},m_{2},\dotsc ,m_{n}$ 种方法，那么做这 $n$ 个任务有 $m_{1}\times m_{2}\times \dotsb \times m_{n}$ 种方法。

证明. 我们用数学归纳法证明。设 $P(n)$ 为命题

"如果做任务 $1,2,\dotsc ,n$ 分别有 $m_{1},m_{2},\dotsc ,m_{n}$ 种方法，那么做这 $n$ 个任务有 $m_{1}\times m_{2}\times \dotsb \times m_{n}$ 种方法."

基础步骤: 假设做任务 1 有 $m_{1}$ 种方法。那么显然做这一个任务有 $m_{1}$ 种方法。所以，$P(1)$ 显然成立。

归纳假设: 设 $k$ 是一个任意正整数。假设 $P(k)$ 成立。也就是说，假设

如果完成任务 $1,2,\dotsc ,k$ 分别有 $m_{1},m_{2},\dotsc ,m_{k}$ 种方法，那么完成这 $k$ 个任务有 $m_{1}\times m_{2}\times \dotsb \times m_{k}$ 种方法。

是正确的。

Inductive Step: We want to show that $P(k+1)$ is true. So, we now assume that there are $m_{1},m_{2},\dotsc ,m_{k},{\color {darkgreen}m_{k+1}}$ ways to do the task $1,2,\dotsc ,k,{\color {darkgreen}k+1}$ respectively. By the inductive hypothesis, there are $m_{1}\times m_{2}\times \dotsb \times m_{k}$ ways to do the first $k$ tasks (task $1,2,\dotsc ,k$). Now, for each of the $m_{1}\times m_{2}\times \dotsb m_{k}$ ways of doing the first $k$ tasks, there are ${\color {darkgreen}m_{k+1}}$ ways to do the task $k+1$. Expressing it using a table, we have $${\begin{array}{cc}{\text{ways of doing the first }}k{\text{ tasks}}&{\text{number of ways to do task }}k+1\\\hline {\text{way 1}}&m_{k+1}\\{\text{way 2}}&m_{k+1}\\\vdots &\vdots \\{\text{way }}m_{1}\times m_{2}\times \dotsb m_{k}&m_{k+1}\\\end{array}}$$ Hence, the number of ways of doing the $k+1$ tasks (the first $k$ tasks, and the task $k+1$) is $$\underbrace {m_{k+1}+m_{k+1}+\dotsb +m_{k+1}} _{m_{1}\times m_{2}\times \dotsb m_{k}{\text{ times}}}=(m_{1}\times m_{2}\times \dotsb \times m_{k})m_{k+1}=m_{1}\times m_{2}\times \dotsb \times m_{k+1}.$$ So, $P(k+1)$ is true.

因此，根据数学归纳法，$P(n)$ 对每个正整数 $n$ 都成立。

$\Box$

备注.

• 有时，将“完成方式”替换为“结果”可能更自然，特别是在任务具有随机结果且无法控制结果的情况下（例如抽奖）。

• 类似地，将“任务”替换为“试验”有时可能更自然。

当我们使用乘法计数原理来解决一些计数问题时，需要注意以下几点

• 我们需要确保完成每个任务的方式数量是 固定的，并且不应该依赖于完成其他任务的方式。（参见以下示例）
• 在使用乘法计数原理来计算完成 $n$ 个任务的方式数量后，有可能一些方式（或“决策路径”，即我们“走过”的树状图路径）实际上对应于问题情况下 相同的结果，因此在该上下文中，这些方式应只算作一种结果。（参见以下示例）

示例。（试验结果数量不固定）考虑一个包含一个 红色 球和一个 蓝色 球的盒子。假设试验 1 和 2 分别是第一次和第二次从盒子中取出一个球。我们进一步假设当取出 红色 球时，我们将其放回盒子中。否则，我们不放回。那么，如果我们在试验 1 中取出 红色 球，那么试验 2 有两种结果。否则，试验 2 只有 1 种结果。在这种情况下，乘法计数原理不适用，因为试验 2 的结果数量不是 固定的（它在 1 和 2 之间变化，具体取决于试验 1 的结果）。

使用图表，这种情况如下所示

  Trial 1         Trial 2

              ---- red
             /    
   red  ----*
 /           \    
*             ---  blue
 \           
  blue  ----*--- red

我们可以看到，我们只有 3 种方法可以完成这两个任务。（这里，完成任务 2 的方法数量既不是 1 也不是 2。事实上，我们无法确定这个数字，因为这个数字根本不固定。）

示例。（两个决策路径导致相同的结果）

假设我们同时抛掷两枚相同且不可区分的硬币。我们还将一枚硬币的结果视为“试验 1”的结果，另一枚硬币的结果视为“试验 2”的结果。在这种情况下，我们可以使用图表来说明情况

Trial 1              Trial 2 
                    ---- H
                   / 
   H -------------* 
 /                 \---- T
/
*                   
\                   ----- H
 \                 /
   T -------------*
                   \
                    ----- T

在这种情况下，“试验 1 中为 H，试验 2 中为 T”与“试验 1 中为 T，试验 2 中为 H”相同，因为两者在该上下文中意味着相同的事情

我们从一枚硬币得到“正面”，从另一枚硬币得到“反面”。

因此，这两个试验实际上只有三个（不同的）结果

1. “两个正面”
2. “一个正面，一个反面”
3. “两个反面”，

而不是 $2\times 2=4$ 个结果，因为不可区分的试验导致两个决策路径导致相同的结果。

练习。假设你有一个抽屉，里面有 50 只相同的红色袜子和 50 只相同的蓝色袜子，假设你从抽屉里取出两只袜子。这两只袜子有多少种不同的颜色组合？

解决方案

我们从抽屉里取出两次。我们将“取 1”视为任务 1，将“取 2”视为任务 2。

Task 1              Task 2 
                    ---- R
                   / 
   R -------------* 
 /                 \---- B
/
*                   
\                   ----- R
 \                 /
   B -------------*
                   \
                    ----- B
R: red sock
B: blue sock

类似地，“任务 1 中为 R，任务 2 中为 B”的颜色模式本质上与“任务 1 中为 B，任务 2 中为 R”的颜色模式相同，因为在两种情况下，颜色组合都是“1 个红色 1 个蓝色”。在这种情况下，只有三个不同的颜色组合

1. 2 个红色
2. 1 个红色 1 个蓝色
3. 2 个蓝色

示例。

在一个国家，有三个城镇：A 镇、B 镇和 C 镇。每个城镇之间的路线由下图说明

  /*------*\          *------------*
 /          \        /             |
A---*\       /B ----*--------------C
      \ /*--*  \                  /
       *        \                /
                 *--------------* 

计算从 A 镇到 C 镇的路线数量。

解决方案. 首先，我们从 A 镇到 B 镇有 2 条路线，从 B 镇到 C 镇有 3 条路线。所以，从 A 镇到 C 镇有 $2\times 3=6$ 种路线。

练习。假设部分路线以以下方式断开：（xxx 表示断开路线）

  /*------*\          *------------*
 /          \        /             |
A---*\       /B xxx *--------------C
      \ /*--*  \                  /
       *        \                /
                 *--------------* 

现在计算从 A 镇到 C 镇的路线数量。

解决方案

路线数量为 $2\times 1=2$.

练习。

一位化学家有三种未知化学物质：化学物质 A、B 和 C。为了测试这三种化学物质，化学家决定进行以下所有实验

1. 混合 A 和 B
2. 混合 B 和 C
3. 混合 A 和 C

假设已知化学物质 A 比其他两种化学物质更具反应性，因此

• 混合不含化学物质 A 的两种化学物质后，有两种可能的结果：（i）无反应；（ii）弱反应；
• 混合含有化学物质 A 的两种化学物质后，有三种可能的结果：（i）无反应；（ii）弱反应；（iii）爆炸。

这三个实验有多少种可能的结果？

解决方案

实验1、2、3 的可能结果数分别为 3、2、3。因此，这三个实验的可能结果总数为 $3\times 2\times 3=18$.

示例：（幂集中的元素数）集合 $S$ 的幂集中元素的个数为 $2^{n}$，其中 $n$ 是集合 $S$ 中的元素个数。

证明：考虑集合 $S$ 中的 $n$ 个元素，逐个进行考虑。对于每个元素，我们可以选择 包含它或 不包含它在集合 $S$ 的一个子集中。因此，构造集合 $S$ 的一个子集需要 $n$ 步，每步都有两种可能的结果。根据乘法计数原理，这 $n$ 步有 $\underbrace {2\times 2\times \dotsb \times 2} _{n{\text{ times}}}=2^{n}$ 种可能的结果。也就是说，集合 $S$ 有 $2^{n}$ 个可能的（不同的）子集。根据定义，幂集包含集合 $S$ 的所有子集，因此幂集有 $2^{n}$ 个元素。

$\Box$

示例：假设我们掷两个（六面）骰子，颜色分别为红色和蓝色。证明向上面的数字组合可能出现的不同对数为 $6\cdot 6=36$.

证明：由于骰子是可区分的，我们可以使用乘法计数原理。更准确地说，我们可以将红色骰子可能出现的数字作为“试验1”的可能结果，蓝色骰子的可能结果作为“试验2”的可能结果。由于每次试验都有六种可能的结果，因此可能的结果（即可能出现不同的对数）为 $6\cdot 6=36$.

$\Box$

练习：假设红色骰子变成蓝色骰子，使得两个骰子不再可区分。证明向上面的数字组合可能出现的不同对数为 21。（提示：从上面的 36 对中减去一些对。）

证明

证明。 从例子中的 36 种结果中，有些组合在改变后与其他组合相同（即，我们不能将它们识别为两组不同的组合）。因此，我们需要从这 36 个组合中删除一个重复的组合。使用 $(a,b)$ 表示原始红蓝骰子中朝上的数字 $a$ 和 $b$，我们有 $${\begin{aligned}&(1,2),{\cancel {(2,1)}},(1,3),{\cancel {(3,1)}},(1,4),{\cancel {(4,1)}},(1,5),{\cancel {(5,1)}},(1,6),{\cancel {(6,1)}},&\leftarrow {\text{5 pairs removed}}\\&(2,3),{\cancel {(3,2)}},(2,4),{\cancel {(4,2)}},(2,5),{\cancel {(5,2)}},(2,6),{\cancel {(6,2)}},&\leftarrow {\text{4 pairs removed}}\\&(3,4),{\cancel {(4,3)}},(3,5),{\cancel {(5,3)}},(3,6),{\cancel {(6,3)}},&\leftarrow {\text{3 pairs removed}}\\&(4,5),{\cancel {(5,4)}},(4,6),{\cancel {(6,4)}},&\leftarrow {\text{2 pairs removed}}\\&(5,6),{\cancel {(6,5)}}.&\leftarrow {\text{1 pair removed}}\end{aligned}}$$ 总共删除了 $5+4+3+2+1=15$ 个组合，所以我们想要的数字是 $36-15=21$.

$\Box$

除法计数原理

定理. （除法计数原理）如果一个任务可以使用一个可以执行 $n$ 种方法的 过程 完成，并且对于执行任务的每种方法 $w$，在 过程 中恰好有 $d$ 种 $n$ 种方法对应于方法 $w$。（${\frac {n}{d}}$ 是一个正整数。）

从图形上看，它就像 $${\begin{aligned}{\text{Task }}\quad &{\text{ Procedure}}\\\hline {\text{way 1}}\leftrightarrow &{\begin{cases}{\text{way 1}}\\{\text{way 2}}\\\quad \vdots \\{\text{way }}d\end{cases}}\\{\text{way 2}}\leftrightarrow &{\begin{cases}{\text{way 1}}\\{\text{way 2}}\\\quad \vdots \\{\text{way }}d\end{cases}}\\\vdots \\{\text{way }}{\frac {n}{d}}\leftrightarrow &{\begin{cases}{\text{way 1}}\\{\text{way 2}}\\\quad \vdots \\{\text{way }}d\end{cases}}\\\hline \qquad \qquad &{\text{Total}}:{\frac {n}{d}}\times d=n{\text{ ways for the procedure}}\end{aligned}}$$

例子. （数牛）假设我们要计算一个牧场里牛的数量。我们先数出总共有 1000 条腿。由于每头牛有四条腿，所以牛的数量是 ${\frac {1000}{4}}=250$。（这里，“任务”可以解释为选择一头牛，“过程”可以解释为选择一条腿。然后，选择一条腿的 4 种方法对应于选择一头牛的 1 种方法。）

例子. （圆桌座位安排）

一个说明这个想法的动画。

计算在圆桌旁为四个人安排座位的种数，其中两个座位安排被认为是 相同 的，如果每个人都有 相同的左边邻居 和 相同的右边邻居。例如，以下两个座位安排被认为是相同的

   1               4
4     2         3     1
   3               2

但以下两个座位安排被认为是 不同 的

   1               4
4     2         1     3
   3               2

因为，对于第 1 个人来说，在左边座位安排中，他的左边和右边邻居分别是 2 和 4，而在右边座位安排中，他的左边和右边邻居分别是 4 和 2。

解决方案.

过程：首先，我们计算在圆桌旁为四个人安排座位的种数，不考虑座位安排是否被认为相同。我们将座位安排看作一个四步过程

1. 为第一个人分配一个座位（有 4 个空座位，所以有 4 种方法）
2. 为第二个人分配一个座位（有 3 个空座位，所以有 3 种方法）
3. 为第三个人分配一个座位（有 2 个空座位，所以有 2 种方法）
4. 为第四个人分配一个座位（有 1 个空座位，所以有 1 种方法）

方法数由以下公式给出：$$\underbrace {4} _{4{\text{ vacant seats}}}\times \underbrace {3} _{3{\text{ vacant seats}}}\times \underbrace {2} _{2{\text{ vacant seats}}}\times \underbrace {1} _{1{\text{ vacant seat}}}=24.$$ 任务：给定一个过程中的安排，我们可以将其顺时针旋转 90、180 或 270 度（旋转 360 度与不旋转相同），以产生另外三种不同的过程安排。然而，这四种安排在任务中被视为相同。这意味着过程中的这四种安排对应于任务中的一种安排。然后，根据除法计数原则，所需的方法数为 $${\frac {24}{4}}=6.$$

练习. 如果有五个人而不是四个人，计算方法数。

解决方案

步骤：首先，在圆桌旁坐五个人（不考虑座位是否被认为是相同的）的方法数为 $$\underbrace {5} _{5{\text{ vacant seats}}}\times \underbrace {4} _{4{\text{ vacant seats}}}\times \underbrace {3} _{3{\text{ vacant seats}}}\times \underbrace {2} _{2{\text{ vacant seats}}}\times \underbrace {1} _{1{\text{ vacant seat}}}=120.$$ 同样。

任务：给定过程中的安排，我们可以将其顺时针旋转 72、144、216 或 288 度，以产生 四个 更多不同的过程安排。但这五种安排在任务中被视为相同。因此，过程中的 五 种安排对应于任务中的一种安排。因此，所需的方法数为 $${\frac {120}{5}}=24.$$

示例。

假设 10 个人决定一起打篮球。因此，他们需要将自己分成两支无法区分的队伍，每支队伍有 5 个人。

1. 控球后卫
2. 得分后卫
3. 小前锋
4. 大前锋
5. 中锋

有多少种方法可以组建这两支队伍？

解决方案.

步骤：首先，我们假设这两支队伍是可区分的，例如一支是蓝队，另一支是红队。在这种情况下，我们可以将队伍组建过程视为一个 10 步过程

• 步骤 1：从 10 个人中选一个作为蓝队的控球后卫。（10 种方法）
• 步骤 2：从 9 个人中选一个作为蓝队的得分后卫。（9 种方法）
• 步骤 3：从 8 个人中选一个作为蓝队的小前锋。（8 种方法）
• ...
• 步骤 10：从 1 个人中选一个作为红队的中锋。（1 种方法）

所以，组建这两支可区分的队伍共有 $10\times 9\times 8\times \dotsb \times 1=3628800$ 种方法。

任务：给定一个组建两支队伍的过程方法，我们可以交换蓝队和红队的队员，以产生另一种不同的组建两支队伍的过程方法。也就是说，将最初在蓝队的队员都分配到红队，将最初在红队的队员都分配到蓝队，我们可以创建另一种组建两支队伍的过程方法。但这两种方法对应于任务中的一种方法（在这两种方法中，两支无法区分的队伍包含相同的队员，因此这两种方法被认为是相同的）。根据除法计数原则，方法数为 $${\frac {3628800}{2}}=1814400.$$

练习. 假设每支队伍都没有位置。也就是说，一支队伍的五个人都被视为仅仅是队伍的成员，没有特定的角色或位置。证明组建这两支队伍只有 126 种方法。（提示：确定将位置安排在最初队伍中 5 个人的方法数。然后，应用除法计数原则（将 1814400 除以某个数）。

证明

证明. 步骤：假设每支队伍仍然有位置。然后，根据上面的示例，组建这两支队伍有 1814400 种方法。

任务：给定步骤中的一个方法，我们可以将位置安排在两支队伍中 5 个人的位置。现在，让我们考虑有多少种排列方法。对于每支队伍，它是一个五步过程

1. 从 5 个队员中选择一个作为控球后卫（5 种方法）
2. 从 4 个队员中选择一个作为得分后卫（4 种方法）
3. 从 3 个队员中选择一个作为小前锋（3 种方法）
4. 从 2 个队员中选择一个作为大前锋（2 种方法）
5. 从 1 个队员中选择一个作为中锋（1 种方法）

所以，每支队伍的排列方法数为 $5\times 4\times 3\times 2\times 1=120$。然后，安排两支队伍是一个两步过程

1. 安排其中一支队伍（120 种方法）
2. 安排另一支队伍（120 种方法）

所以，排列的总方法数为 $120\times 120=14400$，其中包括给定的方法。

因此，这意味着在程序中，我们可以生成$14400-1=14399$ 种方法。但这些 14400 种方法在没有位置的情况下被认为是相同的（两支队伍都包含相同的成员）。根据除法计数原理，方法的数量为$${\frac {1814400}{14400}}=126.$$

$\Box$

我们应该意识到，如果不同的任务执行方式对应于程序中不同的数量，则除法计数原理不适用。考虑以下示例

示例。 （同一个笼子里的鸡和兔子）

假设同一个笼子里有一些鸡和兔子，但我们不知道有多少鸡和兔子。假设我们知道笼子里有 120 条腿。然后，学生 A 和 B 为计算笼子里动物的数量做出了以下论据

• 学生 A：由于每只兔子都有四条腿，笼子里有${\frac {120}{4}}=30$ 只动物。
• 学生 B：由于每只鸡都有两条腿，笼子里有${\frac {120}{2}}=60$ 只动物。

解释为什么两个学生都错了。

解决方案。学生 A 错了，因为笼子里并非每只动物都有四条腿（鸡有两条腿）。类似地，学生 B 错了，因为笼子里并非每只动物都有两条腿（兔子有四条腿）。我们可以看到除法计数原理在这里不适用。

示例。 假设我们抛硬币两次。没有任何假设，不同的结果是 HH、HT、TH 和 TT。假设我们将抛掷视为无序，即结果的顺序并不重要。在这种情况下，结果 HT 和 TH 被视为相同，例如两者都被视为“1 个正面 1 个反面”，或者简称为“1H1T”。但结果 HH 和 TT 仍然被视为不同。

有了这样的考虑，结果就变成了“2H”、“1H1T”和“2T”。但我们看到“1H1T”对应于“HT”和“TH”（“程序”中的两种方式），而“2H”对应于“HH”（“程序”中的一种方式）。所以，除法计数原理在这里不适用，这种情况下的结果数量不是由${\frac {4}{2}}=2$ 给出。

练习。 假设我们抛硬币两次，我们只关心两次抛掷是否产生相同的结果。我们可以在此处使用除法计数原理吗？为什么？

解决方案

在这种情况下，"HH" 和 "TT" 都对应于"相同的结果"，而 "HT" 和 "TH" 对应于"不同的结果"。因此，对于"任务"的每个结果，都有两个对应于它的"程序"结果，因此可以使用除法计数原理获得所需的结果数量：$${\frac {4}{2}}=2.$$

将r个球放入n个单元格中的方法数量

在本节中，我们将讨论如何计算将$r$个球放入$n$个单元格中的方法数量。从这里，人们可能会问为什么我们考虑这种情况，而且似乎我们很少在实践中遇到这种情况。通常，我们想要计算做其他事情的方法数量，而不是将球放入单元格中。

虽然许多遇到的情况似乎与这种情况大不相同，特别是背景通常不是关于将球放入单元格中，但我们可以认为它们好像我们在将球放入单元格中。事实上，许多情况被称为“抽象等效”，从某种意义上说，"生成"结果的底层过程是相同的，但我们只是用不同的词语来描述。

让我们考虑一些与“将$r$个球放入$n$个单元格中”抽象等效的情况（对于某些$n$和$r$）

1. 10 人可能的生日数量：将 10 个“人”（球）放入 365 个“生日日期”（单元格）中。（这里，我们假设一年只有 365 天。）请注意，我们不是将 365 个“生日日期”放入 10 个“人”中。（如果是这种情况，有些人会有不止一个生日！）还要注意，我们可以将不止一个人放入同一个“生日日期”中。（多人可以分享同一个生日！）
2. 设置 6 位数字密码：将 6 个“密码位置”（球）放入 10 个“数字”（单元格）中 (0,1,...,9)。（同样，我们不是将“数字”放入“密码位置”中。如果是这种情况，那么某些密码位置包含不止一个数字，这是不可能的。）
3. 将 1000 人分类为 0-10 岁、11-20 岁、...、91-100 岁、101 岁或以上：将 1000 个“人”（球）放入 11 个“年龄组”（单元格）中。
4. 电梯有 20 个乘客，停在 10 层楼：将 20 个“乘客”（球）放入 10 个“楼层”（单元格）中。
5. 3 只鸽子飞进 2 个鸽舍：将 3 只“鸽子”（球）放入 2 个“鸽舍”（单元格）中。
6. 滚动 10 个骰子：将 10 个“骰子”（球）放入 6 个“结果”（单元格）。
7. 从一副扑克牌中抽取 3 张牌：将 3 个“抽签”（球）放入 52 个“牌”（单元格）。
8. 抛掷 2 枚硬币：将 2 个“抛掷”（球）放入 2 个“结果”（单元格）。
9. 从 20 个人中选出 5 个人组成委员会：将 5 个“委员会职位”（球）放入 20 个“人”（单元格）。

在本节中，我们将主要针对 四种类型 从可区分对象中选择某些对象的情况，根据选择是否 有序 以及选择是否 有放回 进行分类，推导一些计算选择方法数量的公式。我们可以应用上述“抽象等价”的概念，将这种选择转化为将一些可区分或不可区分的球放入一些具有特定容量的可区分单元格的问题，从而使我们能够更轻松、更方便地推导出公式。（正如我们将会看到的，球的可区分性对应于选择是否有序，而单元格的容量对应于选择是否有放回。）

在讨论这四种类型的选择之前，我们需要先介绍一个在后续内容中将频繁使用的数学概念。

定义。（阶乘）令 $n$ 为非负整数。 $n$ 的 阶乘，记为 $n!$，定义为：$$n!={\begin{cases}1,&n=0;\\n(n-1)(n-2)\dotsb (1),&n\geq 1.\end{cases}}$$

将 r 个可区分的球放入 n 个容量为 1 的可区分单元格（有序选择，不放回）

首先让我们讨论从 $n$ 个对象中 有序 选择 $r$ 个对象，不放回。我们可以认为这与将 $r$ 个可区分的球（选择 1、2、…、$r$）放入 $n$ 个可区分的单元格（对象 1、2、…、$n$）抽象等价，容量为 1。

• 容量为 1 是因为 不放回，我们无法多次选择同一个对象（无法将两个或多个球（选择）放入同一个单元格（对象））。

然后，我们推导出以下公式。

定理。 将 $r$ 个可区分的球放入 $n$ 个容量为 1 的可区分单元格的方法数量是 $_{n}P_{r}={\frac {n!}{(n-r)!}}$。

证明。 我们将放置视为一个 $r$ 步过程

• 对于第一个球，有 $n$ 个空格子。因此，有 $n$ 种方法将球放入格子中。
• 对于第二个球，有 $n-1$ 个空格子。因此，有 $n-1$ 种方法将球放入格子中。
• ...
• 对于第 $r$ 个球，有 $n-(r+1)$ 个空格子。因此，有 $n-(r+1)$ 种方法将球放入格子中。

因此，根据计数的乘法原理，所需方法的数量为 $$\underbrace {n} _{\text{ball 1}}\times \underbrace {(n-1)} _{\text{ball 2}}\times \dotsb \times \underbrace {(n-r+1)} _{{\text{ball }}r}={\frac {n\times (n-1)\times \dotsb \times (n-r+1)\times {\color {darkgreen}(n-r)\times \cdots \times 1}}{\color {darkgreen}(n-r)\times \cdots \times 1}}={\frac {n!}{(n-r)!}}.$$

$\Box$

示例. 在书架的一排上，有 5 个放置书籍的位置。艾米有 11 本书，想要填满这一排（顺序很重要）。有多少种可能的方法？

解答. 我们可以将 5 个放置书籍的位置视为 5 个球，艾米拥有的 11 本书视为 11 个格子，每个格子容量为 1（因为每本书最多只能放置一次）。因此，方法的数量为 $$_{11}P_{5}=11\times 10\times 9\times 8\times 7=55440.$$

示例。

在某个地方，有 10 根旗杆，放置在不同的位置。假设我们有 7 面不同的旗帜要放在旗杆上，并且每根旗杆最多只能放一面旗帜。有多少种可能的排列方法？

解答. 我们可以将 10 根旗杆视为 10 个可区分的格子（因为旗杆在不同的位置），每个格子容量为 1（旗杆最多只能放一面旗帜），并将 7 面不同的旗帜视为 7 个可区分的球。因此，排列方法的数量为 $$_{10}P_{7}=10\times 9\times 8\times 7\times 6\times 5\times 4=604800.$$

练习. 假设有 7 根旗杆和 10 面不同的旗帜。计算可能的排列方法的数量。

解决方案

我们可以将 7 根旗杆视为 7 个可区分的球，并将 10 面不同的旗帜视为 10 个可区分的格子，每个格子容量为 1（因为每面旗帜最多只能放在一根旗杆上）。经过这样的解释，情况与上面相同。因此，排列方法的数量也是相同的 (604800)。

示例。

从一副扑克牌（有 52 张牌）中抽取 5 张牌，抽取的顺序很重要，有多少种方法？

解答. 我们可以将 5 次有序抽取视为 5 个可区分的球，将一副扑克牌中的 52 张牌视为 52 个可区分的格子。那么，方法的数量为 $$_{52}P_{5}={\frac {52!}{47!}}=311875200.$$

练习. 如果抽取的顺序 不重要，有多少种方法？（提示: 考虑除法计数原理。为了确定对应于一个无序抽取的有序抽取的数量，考虑对 5 次抽取进行排序（或 排列）的方法数量。）

解决方案

要排列 5 次抽签，我们可以将 5 次抽签视为 5 个可区分的球，将 5 个有序位置视为 5 个可区分的单元格（容量为 1）。那么，这种排序的方案数为 $_{5}P_{5}={\frac {5!}{0!}}=5!=120$.

这反过来意味着 120 种有序抽签对应 1 种无序抽签。也就是说，有 120 种有序抽签，其中 5 次抽签始终包括 5 张牌的组合。因此，根据除法计数原理，方案数为 $${\frac {311875200}{120}}=2598960.$$

示例。 （比赛）有 16 位候选人参加比赛。

(a) 有多少种方法可以颁发冠军、第一名和第二名？

(b) 艾米和鲍勃是 16 位候选人中的两位。假设艾米获得了第一名，而鲍勃没有获得任何奖项。有多少种方法可以颁发冠军、第一名和第二名？

(a) 方案数为 $$_{16}P_{3}=\underbrace {16} _{\text{winner}}\times \underbrace {15} _{\text{1st runner-up}}\times \underbrace {14} _{\text{2nd runner-up}}=3360.$$

(b) 方案数为 $$_{14}P_{2}\times 1=\underbrace {14} _{\text{winner}}\times \underbrace {1} _{\text{1st runner-up: Amy}}\times \underbrace {13} _{\text{2nd runner-up}}=182.$$

练习。

1 假设克里斯也是 16 位候选人中的一员。鉴于艾米、鲍勃和克里斯获得了比赛的奖项，计算颁发冠军、第一名和第二名的方案数。

	1
	3
	6
	32
	96

2 继续上一个问题。鉴于艾米、鲍勃和克里斯 没有 获得比赛的任何奖项，计算颁发冠军、第一名和第二名的方案数。

	1716
	2496
	3354
	3357
	3359

示例。 证明排列（或排列）$n$ 个可区分对象的方案数为 $n!$.

证明。 排列 $n$ 个可区分对象与将 $n$ 个可区分对象（球）放入 $n$ 个可区分的（且有序的）“位置”（单元格）相同。（例如，当球 1、2、3 分别放入位置 2、3、1 时，这意味着按以下顺序排列三个球：3、1、2。）因此，方案数为 $_{n}P_{n}={\frac {n!}{(n-n)!}}={\frac {n!}{0!}}=n!$.

$\Box$

示例。 有多少种方法可以排列字符串“APPLE”？(提示: 您可能需要使用除法计数原理。）

解决方案。首先，我们排列字符串，就像两个“P”是可区分的。然后，有 $5!$ 种方法可以执行“过程”。但实际上两个“P”是不可区分的，因此 $5!$ 种方法中的一些实际上被认为是相同的。更准确地说，当我们交换两个“P”在一个给定字符串中的位置时，得到的字符串在“任务”中应该与之前相同，但如果我们在“过程”中将两个“P”视为可区分的，我们将其视为两个不同的字符串。因此，我们将方案数除以 2，以获得执行“任务”的方案数：$${\frac {5!}{2}}=60,$$ 这就是我们想要的。

练习. 字符串“PEPPER”有多少种排列方式？

解决方案

我们使用与上面例子类似的方法。首先，我们将字符串排列，就好像三个“P”和两个“E”是可以区分的一样。因此，有 $6!$ 种“过程”排列方式。

现在，对于“任务”，给定一个字符串，对 3 个“P”进行排序不会改变字符串。同样，对 2 个“E”进行排序也不会改变字符串。但是，这种排序会在过程中改变字符串。根据乘法计数原理和关于排序的结果，有 $3!\times 2!=12$ 种这样的排序，因此在过程中有 12 种方式对应一个给定的字符串。因此，排列方式的数量是 $${\frac {6!}{12}}=60.$$

上面例子中的情况实际上可以解释为划分的特例。

划分

为了排列字符串“APPLE”，我们可以将情况看作是将 5 个（可区分且有序的）字母位置划分为 4 个组：“A”、“P”、“L”和“E”，我们要求“A”、“P”、“L”、“E”组分别包含 1、2、1、1 个字母位置。类似地，为了排列字符串“PEPPER”，我们可以将情况看作是将 5 个（可区分且有序的）字母位置划分为 3 个组：“P”、“E”和“R”，我们要求“P”、“E”、“R”组分别包含 3、2、1 个字母位置。

这种情况下实际上等效于将可区分的球放入可区分的盒子中，并对每个盒子中必须包含的球数进行一些限制。一般来说，“将$n$ 个可区分的物体划分为$k$ 个组，其中组 1、2、…、$k$ 必须分别包含$n_{1},n_{2},\dotsc ,n_{k}$ 个物体”（仅仅改变将物体放入某个组的顺序不会影响划分，因为最终组中仍然包含相同的东西。）实际上等效于“将$n$ 个可区分的球放入盒子 1、2、…、$k$ 中，其中盒子 1、2、…、$k$ 必须分别包含$n_{1},n_{2},\dotsc ,n_{k}$ 个球”。

定理. 将$n$ 个可区分的球放入盒子 1、2、…、$k$ 中，其中盒子 1、2、…、$k$ 必须分别包含$n_{1},n_{2},\dotsc ,n_{k}$ 个球，方法的数量是 ${\binom {n}{n_{1},n_{2},\dotsc ,n_{k}}}={\frac {n!}{n_{1}!n_{2}!\dotsb n_{k}!}}$.

证明。 首先，我们考虑一个过程，在这个过程中我们认为单元格 1、2、...、$k$ 包含 $n_{1},n_{2},\dotsc ,n_{k}$ 个 有序位置 用于放置一个球（例如，在单元格 1、2、...、$k$ 中有 $n_{1},n_{2},\dotsc ,n_{k}$ 个“子单元格”。在这种情况下，我们可以将放置视为 $n$ 个可区分球的排列，因为 $k$ 个单元格总共包含 $n$ 个“有序位置”（“子单元格”）。经过这样的考虑，放置的方法数量为 $n!$。

但当然我们实际上没有这样的“子单元格”。所以，我们将使用除法计数原理。给定“任务”中的特定分区，有 $n_{1}!,n_{2}!,\dotsc ,n_{k}!$ 种方法来排列单元格 1、2、...、$k$ 中子单元格的可区分球，所以总共有 $n_{1}!n_{2}!\dotsc n_{k}!$ 种方法，对应于“任务”中的一种方法。因此，根据除法计数原理，分区的方法数量为 ${\frac {n!}{n_{1}!n_{2}!\dotsc n_{k}!}}$。

$\Box$

备注.

• ${\binom {n}{n_{1},n_{2},\dotsc ,n_{k}}}$ 被称为 多项式系数。

练习。

计算排列字符串“EXERCISE”的方法数量。

	28
	56
	3360
	6720
	20160

示例。 证明将数字 171237615 排序使得形成的数字为奇数的方法数量为 23520。

证明。 我们考虑相反情况的排列数量，即形成的数字为偶数，因为这个数字更容易计算。我们可以注意到，为了使形成的数字为偶数，该数字必须以数字 2 或数字 6 结尾。因此，我们考虑在这两种情况下的排序方法数量。

情况 1：以 2 结尾。那么，我们只能在头八个数字位置对剩下的 8 个数字进行排序。排序的方法数量为 ${\frac {8!}{3!2!}}=3360$（有三个“1”和两个“7”。所有其他数字都只出现一次。）

情况 2：以 6 结尾。那么，我们只能在头八个数字位置对剩下的 8 个数字进行排序。排序的方法数量为 ${\frac {8!}{3!2!}}=3360$（有三个“1”和两个“7”。所有其他数字都只出现一次。）

我们还可以看到，一个数字不能同时以数字 2 和 6 结尾。 因此，这两种情况下没有共同的排序。 因此，形成偶数的排序数量是 $3360+3360=6720$.

现在，我们考虑 没有 任何限制的排序数量。 该数字由 ${\frac {9!}{3!2!}}=30240$ 给出。 由于形成的数字是奇数或偶数，我们可以从没有限制的排序数量中减去形成偶数的排序数量，以得到所需数量。 因此，所需数量是 $30240-6720=23520$.

$\Box$

练习。 在下面，扑克牌有 52 张，每个玩家都得到相同数量的牌（即 13 张）。 还假设四个玩家分别被称为北、东、南、西玩家，分别坐在桌子上的北、东、南、西位置。

(a) 证明将一副扑克牌分给 4 个玩家的方法数量约为 $5.364\times 10^{28}$.

(b) 证明将一副扑克牌分给 4 个玩家的方法数量，使每个玩家都正好有一张 A，约为 $5.659\times 10^{27}$.

(c) 证明将一副扑克牌分给 4 个玩家的方法数量，使一个玩家得到所有四张 A，约为 $5.667\times 10^{26}$.

(d) 证明将一副扑克牌分给 4 个玩家的方法数量，使北玩家得到所有 13 张同花顺，约为 $3.379\times 10^{17}$.

证明

一般来说，我们可以将 52 张牌视为 52 个可区分的球，将四个玩家视为四个可区分的单元格。 但对不同部分的单元格的球的数量要求不同。

(a)

证明。 以这种方式分发扑克牌可以被视为将 52 张牌分成四个（可区分的）组，每组正好包含 13 张牌。 因此，方法的数量是 ${\frac {52!}{(13!)^{4}}}\approx 5.364\times 10^{28}$.

$\Box$

(b)

证明。 我们首先考虑牌组中没有 A 的 48 张牌。 有 ${\frac {48!}{(12!)^{4}}}$ 种方法将 48 张牌分成四个 12 张牌的组。 现在，我们考虑四张 A 的分配。 由于每个玩家都正好有一张 A，分配四张 A 就相当于对四张 A 进行排列。 因此，该数字是 $4!$。 因此，该数字是 $4!\times {\frac {48!}{(12!)^{4}}}\approx 5.659\times 10^{27}$.

$\Box$

(c)

证明。 我们首先考虑牌组中没有 A 的 48 张牌。 有 ${\frac {48!}{(13!)^{3}\times 9!}}$ 种方法将 48 张牌分成四个组，使得其中三个组分别包含 13 张牌（没有得到所有四张 A 的玩家），一个组包含 9 张牌（得到所有四张 A 的玩家）。 由于一个玩家得到了所有四张 A，并且没有指定该玩家，因此根据哪个玩家得到四张 A，有四种分配四张 A 的可能性。 因此，该数字是 $4\times {\frac {48!}{(13!)^{3}\times 9!}}\approx 5.667\times 10^{26}$.

$\Box$

(d)

证明： 首先考虑牌堆中的 39 张牌，其中去掉了一种特定类型的牌。有 ${\frac {39!}{(13!)^{3}}}$ 种方法将 39 张牌分成三组，每组 13 张，分别对应东、南、西玩家。由于北玩家得到所有 13 张同类型的牌，并且类型没有指定，因此有四种类型的可能性。因此，总数为 $4\times {\frac {39!}{(13!)^{3}}}\approx 3.379\times 10^{17}$.

$\Box$

例： （骰子结果序列）一个六面骰子掷九次。证明出现 1、3 和 5 各三次的不同结果序列的数量为 1680。

证明： 将这九次（有序）骰子结果看作分成三组，分别代表出现 1、3 和 5 的结果。每个组包含 3 个结果，因为数字 1、3、5 各出现了 三次。因此，对结果进行分组的方法数量为 ${\frac {9!}{3!3!3!}}=1680$.

对于每种结果分组方式，我们都会得到一个唯一的结果序列。（例如，如果我们将第一次、第二次和第四次结果放入代表出现 1 的组中，第五次、第七次和第九次结果放入代表出现 3 的组中，剩下的结果放入代表出现 5 的组中，那么我们得到的序列将是： （第一次结果）1、1、5、1、3、5、3、5、3 （第九次结果），按照此顺序。）因此，结果成立。

$\Box$

练习。

1 计算出现 2、4 和 6 各三次的不同序列数量。

	840
	1680
	3360
	6720
	361200

2 假设我们掷骰子 12 次。计算每个数字出现两次的不同序列数量。

	2520
	5040
	113400
	369600
	7484400

例： （行走路径）考虑以下图表： $${\begin{array}{c|c|c|c|c}A&&&&B\\\hline &&E&&\\\hline C&&&&D\\\end{array}}$$ 假设我们最初位于 $A$，并且只能每一步向右走一个单元格或向下走一个单元格。证明从 $A$ 到 $D$ 的不同步数序列的数量为 15。

证明： 首先，观察到我们需要 正好 6 步才能从 $A$ 到 $D$，包括 4 步向右走 ($\rightarrow$) 和 2 步向下走 ($\downarrow$)。（这可以从图表中观察出来，并且我们只能向右走一个单元格或向下走一个单元格的假设非常重要）

因此，不同步数序列的数量等效于 4 个 $\rightarrow$ 和 2 个 $\downarrow$ 的不同序列的数量。

那么可以将其视为一个划分问题：将 6 个步进位置划分为 2 组，其中一组代表 $\rightarrow$ （包含 4 个步进位置），另一组代表 $\downarrow$ （包含 2 个步进位置）。

因此，所需的数字是 $$\underbrace {6!} _{\text{steps}}/(\underbrace {2!} _{\downarrow }\underbrace {4!} _{\rightarrow })=15.$$

$\Box$

练习。

1 如果每一步也可以向左走一个格，请再次计算不同序列的数目。

	15
	35
	90
	105
	以上都不对

2 如果我们还需要在从 $A$ 到 $D$ 的行走过程中经过 $E$，请计算不同序列的数目。（提示: 可以将其视为从 $A$ 到 $E$，然后从 $E$ 到 $D$ 的行走）。

	9
	10
	11
	12
	13

3 如果我们不能在行走过程中经过 $C$，请计算不同序列的数目。

	10
	11
	12
	13
	14

4 假设艾米和鲍勃最初分别位于 $A$ 和 $B$。请计算艾米步进的不同序列数量，使得艾米和鲍勃在 $E$ 处相遇，已知艾米每一步只能向右走一个格或向下走一个格，而鲍勃每一步只能向左走一个格或向下走一个格。

	3
	6
	9
	12
	15

下面我们将讨论不带放回的无序选择，可以将其视为划分的特例。

将 r 个不可区分的球放入 n 个可区分的单元格中，每个单元格最多容纳一个球（不带放回的无序选择）

之前我们讨论过将 $r$ 个 可区分的 球放入 $n$ 个 可区分的 容量为一的盒子中。现在，我们将考虑 $r$ 个球是 不可区分的 的情况。（可以把球想象成 相同的（比如颜色和大小相同），因此无法区分。）类似地，这种放置等同于无放回的选取（$r$ 个球代表选择，每个盒子仍然最多只能放一个球）。然而，在这种情况下，$r$ 个球（选择）是不可区分的。所以，我们只知道哪些 $r$ 个盒子包含一个球（被选中），但不知道他们 以什么顺序 包含一个球，因为球是不可区分的。因此，对于哪些盒子包含一个球（被选中）的顺序在这种情况下并不重要，因为我们无法识别不同选择顺序的差异。因此，我们将选择过程视为 无序的。这种选择过程很常见，因为我们通常更关心 什么 被选中，而不关心 什么顺序 选择东西。

在这种情况下，我们实际上可以将其视为划分的一种特殊情况。

• 对于包含一个球的盒子（$r$ 个），他们被放入 “选中” 组（他们被选中放置一个球）。
• 对于包含零个球的盒子（$n-r$ 个），他们被放入 “未选中” 组（他们没有被选中放置一个球）。

所以，这意味着这种放置等同于将 $n$ 个 可区分的 盒子分成两组，分别包含 $r$ 个 可区分的 盒子和 $n-r$ 个 可区分的 盒子。有了这样的考虑，以下结果是显而易见的

定理。 将 $r$ 个不可区分的球放入 $n$ 个 可区分的 容量为一的盒子的方法数为 ${\binom {n}{r}}={\frac {n!}{r!(n-r)!}}$.

这里，我们给出了该定理的另一种证明，它利用了之前关于可区分球的结果和除法计数原理。

证明。 从之前关于可区分球的结果可知，有 ${\frac {n!}{(n-r)!}}$ 种方法将 $r$ 个可区分球放入 $n$ 个容量为 1 的可区分单元格。但这里我们需要的是球不可区分时的方案数。因此，我们考虑除法计数原理：每个球不可区分的放置方案对应 $r!$ 个球可区分的放置方案（通过排列 $r$ 个可区分球获得）。因此，所需的方案数为 $${\frac {n!}{(n-r)!}}{\bigg /}r!={\frac {n!}{r!(n-r)!}}.$$

$\Box$

备注.

• ${\binom {n}{r}}$ 称为 二项式系数。它也可以用 $_{n}C_{r}$ 表示。
• ${\binom {n}{r}}$ 读作 “n 选 r”。

例子。 考虑一个有 10 人的小组。

(a) 从 10 人中选出 4 人组成委员会，有多少种方法？

(b) 假设这 10 人中有 6 名男性和 4 名女性，委员会需包含 2 名男性和 2 名女性。现在有多少种方法？

(c) 除了委员会需包含 2 名男性和 2 名女性的要求外，委员会中还有 4 个职位：1 名领导人和 3 名成员。现在有多少种方法？

解决方案.

(a) 委员会的选拔顺序并不重要。因此，我们可以将 4 个委员会职位视为不可区分的球，放入 10 个可区分的单元格（10 人）中。因此，方案数为 ${\binom {10}{4}}=210$。

(b) 在这种情况下，要组成委员会，我们需要两步

1. 从 6 名男性中选出 2 人组成委员会 (${\binom {6}{2}}$ 种方法)
2. 从 4 名女性中选出 2 人组成委员会 (${\binom {4}{2}}$ 种方法)

根据乘法计数原理，方案数为 ${\binom {6}{2}}\times {\binom {4}{2}}=90$。

(c) 我们考虑两种不同的情况

情况 1：领导人是男性。那么，3 名成员应该是一名男性和两名女性。在这种情况下，要组成委员会，我们需要三步

1. 从 6 名男性中选出 1 人担任领导人（6 种方法）
2. 从 5 名男性中选出 1 人担任成员（5 种方法）（领导人不能同时担任成员）
3. 从 4 名女性中选出 2 人担任成员 (${\binom {4}{2}}$ 种方法)

根据乘法计数原理，有 $6\times 5\times {\binom {4}{2}}=180$ 种方法。

情况 2：领导人是女性。那么，3 名成员应该是一名女性和两名男性。我们也需要三步来组成委员会

1. 从 4 个女性中选 1 个作为领导（4 种方法）
2. 从 3 个女性中选 1 个作为成员（3 种方法）
3. 从 6 个男性中选 2 个作为成员（${\binom {6}{2}}$ 种方法）

然后，根据乘法计数原理，共有 $4\times 3\times {\binom {6}{2}}=180$ 种方法。

我们可以观察到，情况 1 和情况 2 中没有共同的方法，因为领导者要么是男性，要么是女性。因此，所需方法数为 $180+180=360$。

练习. 继续从 (c) 开始。假设 Amy 是 4 个女性中的一个，Bob 是 6 个男性中的一个。进一步假设，如果领导人是男性，则必须选择 Amy 作为成员，如果领导人是女性，则必须选择 Bob 作为成员。证明方法数为 150。

解决方案

我们考虑两种不同的情况

情况 1：领导人是男性。那么，3 个成员应该是 1 个男性和 2 个女性。在这种情况下，为了组建委员会，我们需要四个步骤

1. 从 6 名男性中选出 1 人担任领导人（6 种方法）
2. 从 5 个男性中选 1 个作为成员（5 种方法）
3. 选择 Amy 作为成员（1 种方法）
4. 从 3 个女性中选 1 个作为成员（3 种方法）

根据乘法计数原理，共有 $6\times 5\times 1\times 3=90$ 种方法。

情况 2：领导人是女性。那么，3 个成员应该是 1 个女性和 2 个男性。我们需要四个步骤来组建委员会

1. 从 4 个女性中选 1 个作为领导（4 种方法）
2. 从 3 个女性中选 1 个作为成员（3 种方法）
3. 选择 Bob 作为成员（1 种方法）
4. 从 5 个男性中选 1 个作为成员（5 种方法）

然后，根据乘法计数原理，共有 $4\times 3\times 1\times 5=60$ 种方法。

我们可以观察到，情况 1 和情况 2 中没有共同的方法，因为领导者要么是男性，要么是女性。因此，所需方法数为 $90+60=150$。

示例。

虚线椭圆提醒我们，这些是集合，其中顺序不重要。

考虑集合 $\{1,2,3\}$。从集合中的 3 个元素中选择（a）零个元素；（b）一个元素；（c）两个元素；（d）三个元素，共有多少种方法？因此，分别列出具有 0、1、2、3 个元素的子集，并证明共有 $2^{3}=8$ 个子集。

解决方案。首先，选择元素是无序的，因为选择元素的顺序不会影响选择的最终结果。

(a) ${\binom {3}{0}}=1$。

(b) ${\binom {3}{1}}=3$。

(c) ${\binom {3}{2}}=3$。

(d) ${\binom {3}{3}}=1$。

子集列表

• ${\binom {3}{0}}=1$ 集包含 0 个元素。它是空集：$\varnothing$。
• ${\binom {3}{1}}=3$ 个集合包含 1 个元素。它们是 $\{1\}$，$\{2\}$ 和 $\{3\}$。
• ${\binom {3}{2}}=3$ 个集合包含 2 个元素。它们是 $\{2,3\}$，$\{1,3\}$ 和 $\{1,2\}$。
• ${\binom {3}{3}}=1$ 个集合包含 3 个元素。它是集合本身：$\{1,2,3\}$。

总共有 $1+3+3=1=8$ 个子集。

示例。 (比赛) 有一场比赛有 16 名候选人，决赛只有 3 个名额。进入决赛的方法数是 ${\binom {16}{3}}={\frac {16\times 15\times 14}{3\times 2\times 1}}=560.$

练习。

1 艾米、鲍勃和克里斯是 $16$ 名候选人中的三位。计算将他们选入决赛的方法数。

	1
	3
	6
	32
	96

2 从上一题继续。计算选择除艾米、鲍勃和克里斯以外的候选人进入决赛的方法数。

	220
	286
	554
	557
	559

示例。 我们有 10 个相同的灯泡，其中 3 个是坏的，另外 7 个灯泡正常工作。我们要把这 10 个灯泡排成一排来照明。为了确保灯泡均匀排列，要求两个坏灯泡不能相邻。有多少种方法可以排列这 10 个灯泡？

解决方案。为了确保没有两个坏灯泡相邻，请考虑以下图表

        * * * * * * *
       ^ ^ ^ ^ ^ ^ ^ ^
* : normally operating bulb
^ : place for at most one defective light bulb

对于每个坏灯泡，我们需要将其放置在正常工作灯泡之间的某个间隙中。此外，为了确保没有两个坏灯泡相邻，每个间隙只能包含 最多一个 坏灯泡。

由于坏灯泡是相同的，因此无法区分（在坏灯泡之间）。所以，情况与将 3 个无法区分的球放入 8 个可区分的单元格（由 "^" 表示的 8 个位置）相同。因此，数量是 $${\binom {8}{3}}=56.$$

例：（超级百万）考虑超级百万彩票游戏。在该游戏中，玩家需要从游戏板上的上半部分白色区域（对应白球）的1到56中选择五个号码，并在游戏板上的下半部分黄色区域（对应金色巨型球）的1到46中选择一个巨型球号码。之后，会抽出五个1到56的白色球和一个1到46的金色巨型球，这些球的号码将决定彩票的结果。特别地，如果抽出的五个白色球的号码和抽出的金色巨型球的号码与玩家选择的号码完全匹配，则玩家赢得头奖。

彩票有多少种不同的结果？

解。我们将结果的决策过程视为一个两步过程

1. （五个白色球）将五个抽取视为五个不可区分的球（每个抽取的具体数字并不重要。我们只关心五个抽取的数字是什么），并将数字1到56视为56个可区分的单元格（容量为一，因为一个白色球不能被抽取多次）。那么，抽取五个白色球的方式数量是${\binom {56}{5}}=3819816$.
2. （一个金色巨型球）从46个金色巨型球中抽取一个有46种方法。

因此，结果的数量是$3819816\times 46=175711536$.

例：（组合证明恒等式）令$n$和$r$是非负整数，使得$n\geq r$。证明$${\binom {n}{r}}={\binom {n-1}{r-1}}+{\binom {n-1}{r}}$$

（a）组合地；

（b）解析地。

组合地证明某件事，是指我们考虑一个特定的情况，并使用两种方法计算该情况的方式/结果/等等的数量，从而得到两个计算相同数字的表达式。然后，我们可以将这两个表达式相等。这种证明也称为双重计数证明，因为我们对同一个数字进行了两次计数。

(a)

证明。考虑将$r$个不可区分的球放入$n$个可区分的单元格（容量为一）的情况。根据前面的定理，方式数量是${\binom {n}{r}}$.

因此，我们有了第一个计数方式数量的方法，对应于方程的左侧。现在，我们使用另一种方法来计数方式数量。首先，我们关注单元格1，并将情况分成两种情况

情况1：单元格1包含一个球。那么，有$r-1$个球剩余，以及$n-1$个单元格剩余。因此，将剩余的$r-1$个球放入剩余的$n-1$个单元格的方式数量是${\binom {n-1}{r-1}}$。由于单元格包含一个球只有一个方法，所以根据乘法计数原理，方式数量是${\binom {n-1}{r-1}}$.

情况 2：单元格 1 包含零个球。那么，还剩 $r$ 个球，以及 $n-1$ 个单元格。因此，方法的数量类似地为 ${\binom {n-1}{r}}$。

由于单元格 1 或者包含一个球，或者包含零个球，所以在情况 1 和 2 中没有共同的方法。因此，放置的方法数量为 $${\binom {n-1}{r-1}}+{\binom {n-1}{r}},$$ 与 RHS 中的表达式相对应。

$\Box$

(b)

证明。 考虑 RHS。我们有 $${\begin{aligned}{\binom {n-1}{r-1}}+{\binom {n-1}{r}}&={\frac {(n-1)!}{(r-1)!(n-1-r+1)!}}+{\frac {(n-1)!}{r!(n-1-r)!}}\\&={\frac {(n-1)!}{(r-1)!(n-r)!}}+{\frac {(n-1)!}{r!(n-r-1)!}}\\&={\frac {(n-1)!}{{\color {blue}(r-1)!}(n-r){\color {blue}(n-r-1)!}}}+{\frac {(n-1)!}{r{\color {blue}(r-1)!(n-r-1)!}}}&{\big (}(n-r)!=(n-r)(n-r-1)!{\text{ and }}r!=r(r-1)!{\big )}\\&={\frac {{\color {red}r}(n-1)!+(n{\color {red}-r})(n-1)!}{r(n-r){\color {blue}(r-1)!(n-r-1)!}}}\\&={\frac {n(n-1)!}{\underbrace {r{\color {blue}(r-1)!}} _{r!}\underbrace {(n-r){\color {blue}(n-r-1)!}} _{n-r!}}}\\&={\frac {n!}{r!(n-r)!}}\\&={\binom {n}{r}},\end{aligned}}$$ 建立了所需的恒等式。

$\Box$

备注.

• 另一种组合证明是 双射证明，但我们这里不再讨论它，因为它比较高级。

例如。 令 $n$ 和 $r$ 为非负整数，使得 $n\geq r$。证明 $${\binom {n}{r}}={\binom {n}{n-r}}$$ 的组合意义。

证明。 考虑有 $n$ 个人，从中选出 $r$ 个人参加委员会。这种选择是无序的（顺序不影响结果），并且无放回（我们不能选择一个人多次参加委员会）。根据前面的定理，这样做的方法数为 ${\binom {n}{r}}$。

另一方面，我们可以将这种情况视为从 $n$ 人中选出 $n-r$ 个人 不 参加委员会。同样，这种选择是无序的，并且无放回（一个人不能被选择多次不参加）。因此，这样做的方法数为 ${\binom {n}{n-r}}$。

由于这两种解释是在同一情况下进行的，因此这两种方法数相同。因此，我们得到了所需的恒等式。

$\Box$

练习。 令 $m,n$ 和 $r$ 为非负整数，使得 $m\geq r$ 且 $n\geq r$。证明 范德蒙德恒等式，即 $${\binom {m+n}{r}}=\sum _{k=0}^{r}{\binom {m}{k}}{\binom {n}{r-k}}$$ 的组合意义。

证明

证明。 考虑将 $r$ 个不可区分的球放入 $m+n$ 个可区分的容量为 1 的盒子的情况。根据前面的定理，这样做的方法数为 ${\binom {m+n}{r}}$。

现在，让我们考虑另一种计算方法。我们关注前 $m$ 个单元格，在 $m+n$ 个单元格中。我们根据放入前 $m$ 个单元格的球的数量，将情况分为 $r$ 种情况。

情况 0： 0 个球被放入前 $m$ 个单元格。我们将此放置过程视为两步操作

1. 将 0 个球放入前 $m$ 个单元格 (${\binom {m}{\color {blue}0}}$ 种方式)
2. 将 $r-{\color {blue}0}$ 个球放入剩下的 $n$ 个单元格 (${\binom {n}{r-{\color {blue}0}}}$ 种方式)

因此，这种情况下的方法数量为 ${\binom {m}{\color {blue}0}}\times {\binom {n}{r-{\color {blue}0}}}$.

情况 1： 1 个球被放入前 $m$ 个单元格。我们将此放置过程视为两步操作

1. 将 1 个球放入前 $m$ 个单元格 (${\binom {m}{\color {blue}1}}$ 种方式)
2. 将 $r-{\color {blue}1}$ 个球放入剩下的 $n$ 个单元格 (${\binom {n}{r-{\color {blue}1}}}$ 种方式)

因此，这种情况下的方法数为 ${\binom {m}{\color {blue}1}}\times {\binom {n}{r-{\color {blue}1}}}$.

...

情况 $k$：${\color {blue}k}$ 个球被放置到 $m$ 个单元格中。我们将放置视为一个两步过程

1. 将 ${\color {blue}k}$ 个球放置到 $m$ 个单元格中（${\binom {m}{\color {blue}k}}$ 种方法）
2. 将 $r-{\color {blue}k}$ 个球放置到其他 $n$ 个单元格中（${\binom {n}{r-{\color {blue}k}}}$ 种方法）

因此，这种情况下的方法数为 ${\binom {m}{\color {blue}k}}\times {\binom {n}{r-{\color {blue}k}}}$.

...

情况 $r$：${\color {blue}r}$ 个球被放置到 $m$ 个单元格中。我们将放置视为一个两步过程

1. 将 ${\color {blue}r}$ 个球放入 $m$ 个盒子 (${\binom {m}{\color {blue}r}}$ 种方法)。
2. 将剩下的 $r-{\color {blue}r}$ 个球放入剩下的 $n$ 个盒子 (${\binom {n}{r-{\color {blue}r}}}$ 种方法)。

因此，在这种情况下，方法数为 ${\binom {m}{\color {blue}r}}\times {\binom {n}{r-{\color {blue}r}}}$。

我们可以观察到，在任意两组情况下，没有共同的方法。因此，方法数为 $$\sum _{k=0}^{r}{\binom {m}{k}}{\binom {n}{r-k}}.$$

$\Box$

将 r 个可区分的球放入 n 个可区分的盒子，盒子容量无限制（带替换的顺序选择）

到目前为止，我们只考虑了无放回的选择，或者等价地，容量为一的单元格。从本节开始，我们将讨论有放回的选择，或者等价地，容量无限的单元格（相同的东西可以被选择无限次）。在本节中，让我们考虑一个更简单的例子：将$r$个可区分的球放入$n$个可区分的单元格，每个单元格的容量无限。这等价于从$n$个可区分的物体中以有序的方式选择$r$个物体，并有放回，通过将球 1,2,...,$r$ 视为选择 1,2,...,$r$，单元格 1,2,...,$n$ 视为物体 1,2,...,$n$。特别地，由于每个物体都可以被选择无限次，因此每个单元格的容量都是无限的。但是计算这种放置方法的数量实际上非常简单，因为我们只需使用乘法计数原理。

命题。 将$r$个可区分的球放入$n$个可区分的单元格，每个单元格的容量无限的方法数是$n^{r}$。

证明。 我们将放置视为一个 $r$ 步过程

• 步骤 1：选择$n$个单元格中的一个来放置球 1。（$n$ 种方法）
• 步骤 2：选择$n$个单元格中的一个来放置球 2。（$n$ 种方法）
• ...
• 步骤 $r$：选择$n$个单元格中的一个来放置球 $r$。（$n$ 种方法）

总而言之，根据乘法计数原理，方法数为 $$\underbrace {n\times n\times \dotsb \times n} _{r{\text{ times}}}=n^{r}.$$

$\Box$

备注.

• 实际上，这种情况只是乘法计数原理应用的一个特例，其中每个$r$任务的方案数相同（$n$种）。

示例. 有多少个6位数，每个数字都是奇数？

解答. 由于每个数字都是奇数，所以每位数字有五个选择：1、3、5、7、9。因此，这样的数字有$5^{6}=15625$个。

示例. 掷两个不同的骰子，有多少种可能的结果？

解答. 每个骰子有六种结果。因此，可能结果的数量是$6^{2}=36$.

练习. 假设我们从一副有52张牌的扑克牌中抽取5张牌有放回，每张牌都记录下来，记录保持顺序。有多少种可能的抽牌记录？

(a) 五张A？

(b) 五张相同花色的A？

(c) 五张相同的牌？

(注意：计数的方法不一定是本节中提到的方法。)

解决方案

(a) 可能性数量为$4^{5}=1024$。 (每次抽取，都有四种A的选择。)

(b) 可能性数量为$4\times 1\times 1\times 1\times 1=4$。 (第一次抽取，有四种A的选择。 对于接下来的四次抽取，抽取的A必须与第一次抽取的A相同花色，因此这四次抽取中只有一个选择。)

(c) 可能性数量为$52\times 1\times 1\times 1\times 1=52$。 (第一次抽取，有52种选择，对于剩下的每次抽取，只有一个选择，就是第一次抽取的牌。)

示例. （设置密码） 假设我们设置一个包含6个字符的密码，遵循以下规则

(R1) 允许使用数字

(R2) 允许使用字母，区分大小写

(R3) 特殊字符（即所有非数字和字母的字符）不允许

证明设置此密码的方案数为 56800235584。

证明. 密码的6个位置，每个位置都有$\underbrace {2} _{\text{cases}}\times \underbrace {26} _{\text{alphabets}}+\underbrace {10} _{\text{numbers}}=62$ 种字符选择。 此外，字符可以在多个位置重复出现，并且顺序很重要。 因此，这是带放回的区分对象的排序选择。 因此，所需的数量为 $\underbrace {62} _{\text{1st position}}\times \underbrace {62} _{\text{2nd position}}\times \dotsb \times \underbrace {62} _{\text{6th position}}=62^{6}=56800235584.$

$\Box$

练习。

1 假设一台机器每秒可以进行$3.5\times 10^{11}$次密码猜测。 使用公式$${\text{the maximum time needed}}\approx {\frac {\text{number of ways to set the password}}{\text{guessing speed}}}.$$ 近似计算机器正确猜测六字符密码所需的最长时间（精确到小数点后两位）。

	0.00 秒
	0.15 秒
	0.16 秒
	6.16 秒
	369.72 秒

2 假设密码的安全性取决于机器使用上一个问题中相同的公式在最短时间内猜出密码所需的时长是否大于或等于 100 年（即 $100\times 365.25\times 24\times 3600=3155760000$ 秒）。为了使密码达到安全性，密码所需的最小字符数（遵循相同的规则）是

	11
	12
	13
	14
	15

示例。 考虑一个抽屉，里面有一些红袜子和蓝袜子。假设你从抽屉里抽出一只袜子五次，每次抽完后放回。有多少种可能的袜子抽取 序列？

解答。 每次抽取都有两种可能性：（i）抽取一只红袜子；（ii）抽取一只蓝袜子。因此，可能的序列数量是 $2^{5}=32$（因为我们考虑的是序列，顺序很重要）。

示例。 考虑一个概率论课程，有 23 人。有多少种可能的 23 人的生日 序列？（假设一年有 365 天。）

解答。 每个人都有 365 种可能的生日。因此，可能的序列数量是 $365^{23}\approx 8.565\times 10^{58}$.

练习。 所有学生生日都不同的序列有多少种？因此，证明在所有可能序列（如上例所示）中，至少两个人 有相同生日的序列比例约为 50.73%。 (提示：在班级中，要么 所有人的生日都不相同，要么 至少两个人有相同的生日。）

解决方案

我们将这种情况视为一个 23 步过程

• 第 1 个人有 365 种可能的生日。
• 第 2 个人有 364 种可能的生日（与第 1 个人不同）。
• 第 3 个人有 363 种可能的生日（与前 2 个人不同）。
• ...
• 第 23 个人有 343 种可能的生日（与前 22 个人不同）。

因此，序列数量为 $365\times 364\times 363\times \dotsb \times 343={\frac {365!}{342!}}\approx 4.22\times 10^{58}$.

这意味着 至少两个人 有相同生日的序列数量为 $8.565\times 10^{58}-4.22\times 10^{58}\approx 4.345\times 10^{58}$. 因此，该比例为 ${\frac {4.345\times 10^{58}}{8.565\times 10^{58}}}\approx 0.5073=50.73\%$.

将 r 个不可区分的球放入 n 个可区分的盒子中，盒子容量无限制（无序选择，可重复）。

在上节中，球是可以区分的。现在，我们将讨论一个更复杂的情况，球是不可区分的。

这种情况的难点在于，我们不能像之前关于将 $r$ 个不可区分的球放到 $n$ 个可区分的容量为 1 的盒子（“任务”）中的情况一样，应用除法计数原理来计算方法的数量。在之前的情况下，我们知道任务中的每一种方法都对应于程序中的 $r!$ 种方法（我们将 $r$ 个可区分的球放入盒子），通过考虑排列被 一个球 占据的 $r$ 个盒子的方法的数量。

但是，在这种情况下，每个盒子可以包含多个球。这意味着被占据的盒子数量可以在 1（所有 $r$ 个球都在一个盒子里）到 $r$（每个盒子一个球）之间变化，具体取决于我们在任务中如何将球放入盒子。因此，任务中的不同方法对应于程序中不同数量的方法。因此，我们不能应用除法计数原理。

由于这个原因，在这种情况下，开发方法数量的方法与之前讨论的方法有很大不同，我们需要一些技巧。

定理。 将 $r$ 个不可区分的球放到 $n$ 个可区分的容量无限的盒子中的方法数量为 $_{n}H_{r}={\binom {n-1+r}{r}}$.

证明。 为了证明这一点，我们引入星号和杠杆符号，来表示球放入盒子的方式。特别是，用 $r$ 个（相同的）星号来表示 $r$ 个不可区分的球，用 $n$ 个（有序的）空格来表示 $n$ 个可区分的盒子。例如，

       *********     9 indistinguishable balls

           |
           |          placement
           v

  **|*| |***|*| |**   
   1 2 3  4  5 6  7  Cell

用来表示

• 盒子 1 中有 2 个球
• 盒子 2 中有 1 个球
• 盒子 3 中有 0 个球
• 盒子 4 中有 3 个球
• 盒子 5 中有 1 个球
• 盒子 6 中有 0 个球
• 盒子 7 中有 2 个球。

此外，在这种情况下，我们正在将 $r=9$ 个不可区分的球放入 $n=7$ 个盒子。

引入这种符号后，我们将计算排列这些星号和杠杆的方法数量，因为 每一种 星号和杠杆的排列都对应于将 $r$ 个不可区分的球放入 $n$ 个可区分的盒子中的 一种 方法。因此，排列的方法数量正好是将球放入盒子中的方法数量。

如果有 $n-1$ 根棍子和 $r$ 颗星星，它们可以任意排列，以表示不同的位置。总共有 $n-1+r$ 个（有序且可区分的）位置来放置星星或棍子。这里，我们关注星星的放置。我们可以将此解释为从这 $n-1+r$ 个位置中无序地选择 $r$ 个位置来放置星星，不放回（当一颗星星被放置在一个位置时，我们不能在同一个位置放置另一个星星）。因此，放置方法的数量为 ${\binom {n-1+r}{r}}$。一旦我们放置了 $r$ 颗星星，只有一种方法可以放置棍子：将它们放置在剩余的位置。

因此，排列 $n-1$ 根棍子和 $r$ 颗星星的方法有 ${\binom {n-1+r}{r}}$ 种，因此结果随之而来。

$\Box$

备注.

• $r$ 可以大于 $n$。

示例. 将 10 个相同的球分配到 4 个不同的箱子（容量无限）有多少种方法？

解答. 我们可以将 10 个相同的球视为 10 个不可区分的球，将 4 个不同的箱子视为 4 个可区分的单元格（容量无限）。那么，方法数为 $_{4}H_{10}={\binom {4-1+10}{10}}={\binom {13}{10}}=286$。

示例。

掷两个相同的骰子有多少种结果？

解答. 我们可以将两个相同的骰子视为 2 个不可区分的球，将掷骰子的 6 种结果视为 6 个可区分的单元格（容量无限，因为一种结果可以在两个骰子上出现多次）。那么，结果数为 $_{6}H_{2}={\binom {6-1+2}{2}}={\binom {7}{2}}=21$。

练习. 掷 三个 相同的骰子有多少种结果？

解决方案

这次，我们有 3 个不可区分的球，还有 6 个可区分的单元格。因此，结果数为 $_{6}H_{3}={\binom {6-1+3}{3}}={\binom {8}{3}}=56$。

示例. 有 8 种不同的食物或饮料，即汉堡、鸡蛋、薯条、蛋糕、苹果派、苹果汁、橙汁和可乐。除非另有说明，否则套餐可以包含相同项目多次。

(a) 有多少种不同的 4 项目套餐必须包含不同的项目？

(b) 有多少种不同的 4 件组合？

(c) 有多少种不同的 3 种食物和 1 种饮料的组合？

解决方案.

我们可以将组合中的 4 种选择视为 4 个不可区分的球（因为我们关心的是整体的 4 种选择是什么，而不关心这 4 种选择中的 每一种具体是什么，所以应该将其视为不可区分的），并将 8 种食物/饮料视为 8 个可区分的单元格。

(a) 由于组合必须包含不同的项目，这意味着我们不能在一个单元格中放置多个食物选择。换句话说，单元格的容量为一。因此，组合的数量由 ${\binom {8}{4}}=70$ 给出。

(b) 这一次，由于组合可能包含多次相同的项目，这意味着单元格的容量变得无限。因此，组合的数量为 ${\binom {8-1+4}{4}}=330$.

(c) 由于组合需要包含 3 种食物和 1 种饮料，我们需要分两个步骤

1. 我们需要将 4 个不可区分的球中的一个放入 3 个可区分的单元格中的一个，代表 3 种饮料（苹果汁、橙汁和可乐）。（3 种方法）
2. 然后，我们将剩下的 3 个不可区分的球放入另外 5 个可区分的单元格中（容量无限），代表 5 种食物。（$_{5}H_{3}$ 种方法）

因此，组合的数量为 $3\times {}_{5}H_{3}=3\times {\binom {5-1+3}{3}}=3\times {\binom {7}{3}}=105$.

练习。

(a) 有多少种不同的 4 种食物组合？

(b) 艾米很喜欢吃汉堡，所以她每次选择 4 件组合的时候都会选择两个汉堡。计算艾米点餐 4 件组合的不同方法的数量。

解决方案

(a) 由于组合需要包含 4 种食物，我们正在将 4 个不可区分的球放入 5 个可区分的单元格中，代表 5 种食物。因此，组合的数量为 $_{5}H_{4}={\binom {5-1+4}{4}}=70$

(b) 由于有 2 个不可区分的球必须放入代表汉堡的单元格中（只有一种方法），所以还有 2 个不可区分的球剩下，要放入其他 7 个单元格中（它们不能放入汉堡的单元格中，因为艾米选择的是 正好 两个汉堡）。因此，组合的数量为 $_{7}H_{2}={\binom {7-1+2}{2}}=28$.

示例。 （选 3 个）考虑一个名为 选 3 个 的彩票游戏。在这个游戏中，玩家从 0 到 9 中选择三个数字，并且每天多次宣布 3 个 中奖号码。玩家在选择三个数字时，有两种方法可以使用这三个数字进行游戏

1. 精确顺序：如果玩家选择的三个数字与他选择后最近一次宣布的中奖号码 完全 相匹配（在数字和顺序上），则玩家获胜。（更高的奖金）
2. 任何顺序：如果玩家选择的三个数字与他选择后最近一次宣布的中奖号码的数字相匹配（但顺序不一定相同），则玩家获胜。（更低的奖金）

因此，选择不同游戏方式的玩家对中奖号码的看法不同

• 对于选择 精确顺序 的玩家，他们关心中奖号码的顺序和数字。
• 对于选择 任何顺序 的玩家，他们只关心中奖号码的数字。

因此，不同的中奖号码的数量可能不同，因为“不同”的含义取决于游戏方式。（这里，“不同”指的是不同中奖号码所代表的结果不同。例如，1,2,3 和 1,3,2 从精确顺序的角度来看是不同的，但从任何顺序的角度来看是相同的（因为中奖号码中的三个数字是相同的，因此这两个中奖号码的含义相同：如果玩家分别选择了数字 1,2,3 一次，那么他就会获胜）。在本例中，我们将从这两个角度计算不同的中奖号码的数量。

(a) 从精确顺序的角度来看，有多少种不同的中奖号码？

(b) 从任何顺序的角度来看，有多少种不同的中奖号码？

解决方案.

(a) 从精确顺序的角度来看，中奖号码的顺序很重要。然后，我们可以将中奖号码的形成视为一个三步过程

1. 从十个数字 0-9 中选择一个作为第一个中奖号码。（10 种方法）
2. 从十个数字 0-9 中选择一个作为第二个中奖号码。（10 种方法）
3. 从十个数字 0-9 中选择一个作为第三个中奖号码。（10 种方法）

因此，有 $10^{3}=1000$ 种不同的中奖号码。

(b) 从任意顺序的角度来看，中奖号码的顺序无关紧要。我们只关心哪三个数字出现在中奖号码中。因此，我们可以将中奖号码的三个位置视为三个不可区分的球，并将数字 0-9 视为十个可区分的单元格（容量无限，因为 0-9 之间的数字可以被选中超过一次作为 3 个中奖号码）。然后，不同中奖号码的数量为 $$_{10}H_{3}={\binom {10-1+3}{3}}=220.$$

例：（方程的整数解数）考虑方程 $$x_{1}+x_{2}+\dotsb +x_{7}=10.$$ (a) 当 $x_{1},\dotsc ,x_{7}$ 为非负整数时，方程有多少个解？

(b) 当 $x_{1},\dotsc ,x_{7}$ 为正整数时，方程有多少个解？

(c) 证明当 $x_{1},\dotsc ,x_{7}$ 为非负整数时，不等式 $x_{1}+x_{2}+\dotsb +x_{7}<10$ 有 11440 个解。

解决方案.

(a) 我们可以将数字 10 视为 10 个不可区分的球（每个球代表“1”），并将 $x_{1},x_{2},\dotsc ,x_{7}$ 视为 7 个可区分的单元格，容量无限（每个单元格可以包含 0 个或多个球，对应于 $x_{1},x_{2},\dotsc ,x_{7}$ 的非负性）。（例如，如果单元格 $x_{3}$ 包含 2 个球，则意味着 $x_{3}=2$。）因此，解的数量是将球放入单元格的方式的数量，即 $$_{7}H_{10}={\binom {7-1+10}{10}}=8008.$$

(b) 令 $x_{1}'=x_{1}-1,\dotsc ,x_{7}'=x_{7}-1$. 那么，$x_{1}',\dotsc ,x_{7}'$ 都是非负整数。那么，我们有 $$x_{1}+x_{2}+\dotsb +x_{7}=10\iff x_{1}'+x_{2}'+\dotsb +x_{7}'={\color {darkgreen}3}.$$ 由此可知解的个数为 $_{7}H_{\color {darkgreen}3}={\binom {7-1+3}{3}}=84$.

(c) 可以通过考虑所有 10 种可能的情况来计算解的个数：$x_{1}+\dotsb +x_{7}=0,1,\dotsc ,{\text{ or }}9$. 但这里我们提供了一种替代的、更方便的方法，它使用了一个巧妙的技巧

证明。 为了使不等式变成等式，我们在左侧添加一个额外的正整数项 $x_{8}$，这导致了一个等式：$$x_{1}+x_{2}+\dotsb +x_{8}=10$$ 其中 $x_{8}$ 是一个 正整数。这个等式与不等式等价，因为 $$x_{1}+x_{2}+\dotsb +x_{7}<10\iff x_{1}+x_{2}+\dotsb +x_{7}=10-\underbrace {x_{8}} _{\text{+ve integer}}<10\iff x_{1}+x_{2}+\dotsb +x_{8}=10.$$ 所以，为了得到这个等式的解的个数，我们将情况考虑如下

• 10 个不可区分的球
• 8 个可区分的单元格代表 $x_{1},x_{2},\dotsc ,x_{8}$，其中每个单元格 $x_{1},\dotsc ,x_{7}$ 包含零个或多个球，而单元格 $x_{8}$ 包含一个或多个球。

由于单元格 $x_{8}$ 必须包含一个或多个球，因此我们必须先将 10 个不可区分的球中的一个放入此单元格（1 种方式）。因此，还有 9 个剩余的不可区分的球。同样地，我们可以暂时忽略单元格 $x_{8}$ 中的球。然后，将 9 个球放入 8 个单元格的方式数量为 $_{8}H_{9}$。之后，我们可以考虑回到单元格 $x_{8}$ 中的球，以确定相应的解决方案。

因此，解的数量为 $_{8}H_{9}={\binom {8-1+9}{9}}=11440.$

$\Box$

练习。 一位投资者正在积极跟踪 7 只不同的股票，他想以某种方式在这 7 只股票上投资 100,000 美元。假设每只股票的每股价格为 10,000 美元。使用上述示例中的适当结果，确定

(a) 投资 7 只股票的方式数量。

(b) 投资 7 只股票并节省部分资金（非零）的方式数量。

解决方案

我们可以将 $x_{1},\dotsc ,x_{7}$ 视为分别为股票 1、...、7 购买的股票数量。

(a) 8008。 （每只股票的股票数量为非负整数。由于总投资额为 100,000 美元，因此购买的股票总数为 10。）

(b) 11440。 （总投资额小于 100,000 美元，因此购买的股票总数小于 10。）

Example. Consider the multinomial theorem which states that $$(x_{1}+x_{2}+\dotsb +x_{r})^{n}=\sum _{(n_{1},n_{2},\dotsc ,n_{r}):n_{1}+n_{2}+\dotsb +n_{r}=n}^{}{\binom {n}{n_{1},n_{2},\dotsc ,n_{r}}}x_{1}^{n_{1}}x_{2}^{n_{2}}\cdots x_{r}^{n_{r}}$$ for every positive integer $k$ and nonnegative integer $n$. Also, $n_{1},\dotsc ,n_{r}$ are nonnegative. In particular, the summation notation means that the sum is taken over all nonnegative integer vectors (i.e., lists of numbers) $(n_{1},n_{2},\dotsc ,n_{r})$ such that $n_{1}+n_{2}\dotsc +n_{r}=n$. For example, $$(x_{1}+x_{2}+x_{3})^{2}={\binom {2}{2,0,0}}x_{1}^{2}x_{2}^{0}x_{3}^{0}+{\binom {2}{0,2,0}}x_{1}^{0}x_{2}^{2}x_{3}^{0}+{\binom {2}{0,0,2}}x_{1}^{0}x_{2}^{0}x_{3}^{2}+{\binom {2}{1,1,0}}x_{1}^{1}x_{2}^{1}x_{3}^{0}+{\binom {2}{1,0,1}}x_{1}^{1}x_{2}^{0}x_{3}^{1}+{\binom {2}{0,1,1}}x_{1}^{0}x_{2}^{1}x_{3}^{1}=x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+2x_{1}x_{2}+2x_{1}x_{3}+2x_{2}x_{3}.$$ Show that there are $_{n}H_{r}$ terms in the expansion by the multinomial theorem.

证明。 注意到展开式中的每一项都对应于一个非负整数向量 $(n_{1},n_{2},\dotsc ,n_{r})$。因此，展开式中项的数量正好是非负整数向量 $(n_{1},n_{2}\dotsc ,n_{r})$ 的数量，满足条件 $n_{1}+n_{2}+\dotsb +n_{r}=n$，即方程 $n_{1}+n_{2}+\dotsb +n_{r}=n$ 的解的数量，其中 $n_{1},n_{2},\dotsc ,n_{r}$ 是非负整数。

为了得到这个数字，我们将情况视为将 $n$ 个不可区分的球放入 $r$ 个可区分的单元格，这些单元格具有无限容量，分别代表 $n_{1},n_{2},\dotsc ,n_{r}$。根据之前的结果，该数字为 $_{n}H_{r}$。

$\Box$

示例。 四个渔夫一起去钓鱼。假设他们今天钓到 20 条相同的鱼，需要将这些鱼分给彼此。有多少种分配方式呢？

解决方案。我们将 20 条鱼视为 20 个不可区分的球，将 4 个渔夫视为 4 个可区分的单元格。因此，方法数为 $$_{4}H_{20}={\binom {4-1+20}{20}}=1771.$$

示例。 十个相同的机器人乘坐电梯，电梯从 1/F 到 6/F 一层一层地移动。假设他们必须在其中一层楼的左侧下电梯。

(a) 有多少种不同的下电梯方式？

(b) 假设将十个相同的机器人替换为十个不同的人。有多少种不同的下电梯方式？

解决方案.

(a) 我们将十个相同的机器人视为 10 个不可区分的球，将六层楼视为六个可区分的单元格。然后，数量为 $_{6}H_{10}=3003$.

(b) 我们将 10 个人下电梯的过程视为一个 10 步的过程

• 第 1 步：第一个人可以在六层楼中任意一层下电梯。(6 种方法)
• 第 2 步：第二个人可以在六层楼中任意一层下电梯。(6 种方法)
• ...
• 第 10 步：第十个人可以在六层楼中任意一层下电梯。(6 种方法)

因此，数量为 $6^{10}=60466176$.

练习。 一家公司有 20 名员工，他们将被分成三个团队：A 团队、B 团队、C 团队。这 20 名员工中有 3 人将被选中分别担任 A 团队、B 团队、C 团队的队长。除此之外，对每个团队的人数没有要求。

(a) 如果这 20 名员工是相同的机器人，请证明有 171 种划分方法。

(b) 如果这 20 名员工是不同的人，请证明有 883318714920 种划分方法。

证明

(a)

证明。 我们将划分过程视为两步过程

1. 分别从 120 个相同的机器人中选择 A 团队、B 团队、C 团队的三个队长（一种方法）。
2. 剩下 17 个员工，我们将他们视为 17 个不可区分的球，放入 3 个可区分的单元格（代表三个团队）中，这些单元格的容量无限制。($_{3}H_{17}$ 种方法)

因此，方法数为 $_{3}H_{17}={\binom {3-1+17}{17}}=171$.

$\Box$

(b)

证明。 我们将划分过程视为两步过程

1. 分别从 20 个人中选择 A 团队、B 团队、C 团队的三个队长。($20\times 19\times 18$ 种方法)
2. 对于剩下的 17 个人中的每一个人，他们可以被分配到三个团队中的一个。($3^{17}$ 种方法)

所以，方法数为 $20\times 19\times 18\times 3^{17}=883318714920$.

$\Box$

练习。 艾米有九个相同的戒指。假设她的每根手指都可以戴无限多个戒指。

(a) 请证明她右手戴戒指有 715 种方法。

(b) 请证明她两只手戴戒指有 48620 种方法。

(c) 假设她的左手要戴四个戒指，右手要戴另外五个戒指。请证明她两只手戴戒指有 8820 种方法。

(d) 假设她每个无名指都戴一个戒指。请证明她两只手戴戒指有 3432 种方法。

证明

(a)

证明。 方法数为 $_{5}H_{9}=715$。(9 个不可区分的球：9 个戒指；5 个容量无限制的可区分单元格：5 根手指)

$\Box$

(b)

证明。 方法数为 $_{10}H_{9}=48620$。(9 个不可区分的球：9 个戒指；10 个容量无限制的可区分单元格：10 根手指)

$\Box$

(c)

证明。 考虑两步

1. 左手戴戒指。($_{5}H_{4}=70$ 种方法。4 个不可区分的球：4 个戒指；5 个容量无限制的可区分单元格：5 根手指)
2. 右手戴戒指。($_{5}H_{5}=126$ 种方法。5 个不可区分的球：5 个戒指；5 个容量无限制的可区分单元格：5 根手指

所以，方法数为 $70\times 126=8820$.

$\Box$

(d)

证明。 考虑两步

1. 每个无名指都戴一个戒指。(1 种方法)
2. 剩下的八根手指戴着七个剩余的戒指。 ($_{8}H_{7}=3432$ 种方式。7 个不可区分的球：7 个戒指；8 个可区分的细胞，容量无限：8 根手指)

所以，方法的数量是 3432。

$\Box$

摘要

将 $r$ 个球放入 $n$ 个可区分的细胞

	容量为一个的细胞	容量无限的细胞
可区分的球	$$n^{r}$$	$${\frac {n!}{(n-r)!}}$$
不可区分的球	$${\binom {n-1+r}{r}}$$	$${\binom {n}{r}}$$

练习。 尝试证明上述每个公式，不参考前几节。之后，您可以将您的证明与前几节中的证明进行比较。

或者等效地，

从 $n$ 个可区分的对象中选择 $r$ 个对象

	有替换	无替换
有序	$$n^{r}$$	$${\frac {n!}{(n-r)!}}$$
无序	$${\binom {n-1+r}{r}}$$	$${\binom {n}{r}}$$

不可区分的细胞

当 细胞 不可区分时，通常没有简单明了的公式来计算方法的数量。此外，在这种情况下，可能更难想象“不可区分的细胞”是什么样子，因为即使细胞是相同的，它们的 position 应该不同，以便球可以放置在不同的细胞中。然后，这些细胞仍然是可区分的。为了可视化不可区分的细胞，人们可以想象在球被放入细胞后，“排序”这些细胞，根据它们包含的球的数量，球最少的细胞放在最左边，球最多的细胞放在最右边。（具有相同球数的细胞可以随意放在一起。）然后，在将球“投入”细胞 并 对细胞进行排序后，我们可以观察这些细胞来观察结果。在这种情况下，细胞可以被视为不可区分的，因为我们只知道有多少个细胞包含 0 个、1 个等球，但不知道原始的细胞 1、2、.. 包含多少个球（我们无法在排序后判断哪个细胞是原始的“细胞 1、2、..”）。

当我们遇到不可区分的细胞时，我们可能需要逐一考虑方法。

示例。 四个人要被分成 3 个 不可区分的 组。假设每个组可以包含零个人或多个人。证明有 14 种可能的组合。

证明。 我们将这种情况视为将四个可区分的球（代表四个人）放入三个不可区分的细胞（代表三个组）中，这些细胞具有无限容量。 然后，我们对球 1、2、3、4 放入三个不可区分的细胞（按包含的球数排序的细胞）有以下不同的排列方式。（我们使用数字 1、2、3、4 分别表示球 1、2、3、4，并将两个竖线创建的三个空格作为不可区分的细胞（“排序”后的细胞）。请注意，空格中数字的顺序无关紧要。我们只关心 哪些 数字包含在每个空格中。）

1. $||1234$
2. $|1|234$
3. $|2|134$
4. $|3|124$
5. $|4|123$
6. $|12|34$
7. $|13|24$
8. $|14|23$
9. $1|2|34$
10. $1|3|24$
11. $1|4|23$
12. $2|3|14$
13. $2|4|13$
14. $3|4|12$

因此，共有 14 种方法。

$\Box$

计数问题的强大工具：生成函数

定义。 （生成函数）一个 生成函数 是一个 幂级数，其系数给出特定数字序列。也就是说，序列 $a_{0},a_{1},a_{2},\dotsc$ 的生成函数由 $$G(x)=\sum _{n=0}^{\infty }a_{n}x^{n}=a_{\color {darkgreen}0}x^{\color {darkgreen}0}+a_{\color {darkgreen}1}x^{\color {darkgreen}1}+a_{\color {darkgreen}2}x^{\color {darkgreen}2}+\dotsb .$$

备注.

• $x^{k}$ 的系数，即 $a_{k}$，可以通过 $a_{k}={\frac {1}{k!}}G^{(k)}(0)$ 获得，其中 $G^{(k)}(0)$ 表示函数 $G$ 在 $x=0$ 处的 $k$ 阶导数。
• 在后面的章节中，我们将研究两种重要的生成函数：矩生成函数（mgf）和概率生成函数（pgf），它们的系数在某种意义上分别给出矩序列和概率序列。可以使用与上述类似的方法获得这些系数（表示矩/概率）。

以下定理给出了一些常见的生成函数。

定理。 （牛顿广义二项式定理）令 $\alpha$ 为一个 实数。 那么，$$(1+x)^{\alpha }=\sum _{k=0}^{\infty }{\binom {\alpha }{k}}x^{k}$$ 其中 $|x|<1$，并且 ${\binom {\alpha }{k}}={\frac {\alpha (\alpha -1)(\alpha -2)\dotsb (\alpha -k+1)}{k!}}$ 是 广义二项式系数。

备注.

• 定理中的级数也称为 二项式级数。
• 方程中的级数实际上是 $(1+x)^{\alpha }$ 在零处的泰勒级数。也就是说，如果我们令 $f(x)=(1+x)^{\alpha }$，那么该级数由以下给出

$$\sum _{n=0}^{\infty }{\frac {f^{(n)}(0)}{n!}}x^{n}$$

其中 $f^{(n)}(0)$ 是函数 $f$ 在 $x=0$ 处的 $n$ 阶导数，条件 $|x|<1$ 是为了确保这个级数收敛。

• 然而，需要注意的是，仅仅这个泰勒级数收敛并不保证它收敛到函数的实际值（它可能收敛到其他地方）。因此，仅仅使用这个泰勒级数不足以证明该定理。

• 定理中的级数是序列 ${\binom {\alpha }{0}},{\binom {\alpha }{1}},{\binom {\alpha }{2}},\dotsc$ 的生成函数。

以下是该定理的一些特例

• (等比级数) $(1+x)^{-1}=1-x+x^{2}-x^{3}+\dotsb$: 序列 1,-1,1,-1,... 的生成函数;
• (等比级数) $(1-x)^{-1}=1+x+x^{2}+x^{3}+\dotsb$: 序列 1,1,1,1,... 的生成函数;
• (负二项式级数) $(1-x)^{-n}=\sum _{r=0}^{\infty }{\binom {n-1+r}{r}}x^{r}$: 序列 ${\binom {n-1}{0}},{\binom {n-1+1}{1}},{\binom {n-1+2}{2}},{\binom {n-1+3}{3}},\dotsc$ ;
• （二项式定理）$(1+x)^{n}={\binom {n}{0}}+{\binom {n}{1}}x+\dotsb +{\binom {n}{n}}x^{n}$：是序列${\binom {n}{0}},{\binom {n}{1}},{\binom {n}{2}},\dotsc ,{\binom {n}{n}}$ 的生成函数；（$n$ 是非负整数）
• （二项式定理）$(x+y)^{n}={\binom {n}{0}}x^{n}y^{0}+{\binom {n}{1}}x^{n-1}y+\dotsb +{\binom {n}{n}}x^{n-n}y^{n}$。（注意到$(x+y)^{n}=x^{n}(1+y/x)^{n}$，并将定理应用于$(1+y/x)^{n}$ 的 RHS 得出。）

示例. 使用生成函数的概念，证明将 $r$ 个不可区分的球放入 $n$ 个可区分的箱子的方法数为 ${\binom {n}{r}}$。

证明。 我们将选择过程编码为二项式序列，然后使用系数来确定所需的方法数量。更准确地说，考虑二项式序列：$$\underbrace {(1+x)(1+x)\dotsb (1+x)} _{n{\text{ times}}}=(1+x)^{n}=1+\cdots +{\binom {n}{r}}x^{r}+\cdots +{\binom {n}{n}}x^{n}.$$ 我们将 $n$ 个括号 $(1+x)$ 编码为 $n$ 个单元格，如果我们在括号中选择 "1"，则该单元格有零个球。如果我们在括号中选择 "$x$"，则该单元格有一个球。由于有 $r$ 个球，因此 $r$ 个 $n$ 个括号中包含一个球，因此所需的方法数量是 $x^{r}$ 的系数（系数给出通过将 $x$ 乘以恰好 $r$ 个括号来 "构建" $x^{r}$ 的方法数量（"$x$" 是通过在恰好 $r$ 个单元格中放置一个球而得到的）。因此，方法数量为 ${\binom {n}{r}}$.

$\Box$

示例。 证明将 $r$ 个无法区分的球放入 $n$ 个可区分的单元格中，每个单元格容量无限的方法数量为 ${\binom {n-1+r}{r}}$.

证明。 我们将 $n$ 个括号 $(1+x+x^{2}+\dotsb )$ 编码为 $n$ 个单元格。如果我们在括号中选择“1”，那么单元格中没有球，如果我们在括号中选择“$x$”，那么单元格中有一个球，如果我们在括号中选择“$x^{2}$”，那么单元格中有两个球，等等。然后，所需数字是 $x^{r}$ 的系数（通过在不同的括号中乘以一些 $x$ 的幂来“构建” $x^{r}$ 的方法数量（幂由一些单元格中的一些球获得））在生成函数 $$\underbrace {(1+x+x^{2}+\dotsb )(1+x+x^{2}+\cdots )\cdots (1+x+x^{2}+\cdots )} _{n{\text{ times}}}=\underbrace {(1-x)^{-1}(1-x)^{-1}\dotsb (1-x)^{-1}} _{n{\text{ times}}}=(1-x)^{-n}.$$ 这是负二项式级数。因此，$x^{r}$ 的系数是 $${\binom {n-1+r}{r}}.$$

$\Box$

示例。 证明将 $n$ 个可区分的球放入单元格 1、2、...、$k$ 中，其中单元格 1、2、...、$k$ 必须分别包含 $n_{1},n_{2},\dotsc ,n_{k}$ 个球的方法数量是 ${\frac {n!}{n_{1}!n_{2}!\dotsb n_{k}!}}$，使用生成函数的概念。

证明： 我们将 $n$ 个括号 $(x_{1}+x_{2}+\dotsb +x_{k})$ 编码为 $n$ 个单元格。如果选择 $x_{1},x_{2},\dotsc ,x_{k}$，我们就在单元格 1, 2, ..., $k$ 中放一个球。由于我们希望单元格 1, 2, ..., $k$ 中恰好包含 $n_{1},n_{2},\dotsc ,n_{k}$ 个球，我们感兴趣的是 $x_{1}^{n_{1}}x_{2}^{n_{2}}\dotsb x_{k}^{n_{k}}$ 的系数，即，将不同的 "$x_{i}$" 在不同的括号中相乘以创建乘积 $x_{1}^{n_{1}}x_{2}^{n_{2}}\dotsb x_{k}^{n_{k}}$ 的方法数量，在 $$\underbrace {(x_{1}+x_{2}+\cdots +x_{k})(x_{1}+x_{2}+\cdots +x_{k})\cdots (x_{1}+x_{2}+\cdots +x_{k})} _{n{\text{ times}}}=(x_{1}+x_{2}+\cdots +x_{k})^{n},$$ 也就是 ${\frac {n!}{n_{1}!n_{2}!\dotsb n_{k}!}}$，根据 多项式定理。

$\Box$

例如： 计算方程 $x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}=26$ 的解的个数，其中 $x_{1},x_{2},\dotsc ,x_{6}$ 为正数，$x_{5}>3$ 且 $3\leq x_{6}<6$.

解. 考虑生成函数 $$\underbrace {(x+x^{2}+x^{3}+\dotsb )^{4}} _{x_{1},x_{2},x_{3},x_{4}}\underbrace {(x^{4}+x^{5}+x^{6}+\dotsb )} _{x_{5}}\underbrace {(x^{3}+x^{4}+x^{5})} _{x_{6}}=x^{4}(1-x)^{-4}x^{4}(1-x)^{-1}(x^{3}+x^{4}+x^{5})=(x^{11}+x^{12}+x^{13})(1-x)^{-5}.$$ （不同括号内的 $x$ 的幂表示不同未知数 $x_{i}$ 所选的整数）。

根据牛顿广义二项式定理， $x^{15},x^{14},x^{13}$ 在 $(1-x)^{-5}$ 中的系数分别为 ${\binom {-5}{15}}(-1)^{15}=3876,{\binom {-5}{14}}(-1)^{14}=3060,{\binom {-5}{13}}(-1)^{13}=2380$。这意味着 $x^{26}$ 在 $(x^{11}+x^{12}+x^{13})(1-x)^{-5}$ 中的系数为 $3876+3060+2380=9316$。因此，解的个数为 9316。

备注.

• 也可以注意到$(1-x)^{-5}$ 是一个负二项式级数，并继续使用，例如，${\binom {5-1+15}{15}}$ 来获得$x^{15}$ 在$(1-x)^{-5}$ 中的系数。

示例. 假设你去水果店购买 15 个水果。水果店里有两个苹果，三个梨，六个香蕉，以及无限数量的柚子。证明你可以用 84 种不同的方式购买这 15 个水果。（假设每种水果都是相同的，因此无法区分。）

Proof. Consider the generating function $${\begin{aligned}G(x)&=\underbrace {(1+x+x^{2})} _{\text{apple}}\underbrace {(1+x+x^{2}+x^{3})} _{\text{pear}}\underbrace {(1+x+x^{2}+x^{3}+x^{4}+x^{5}+x^{6})} _{\text{banana}}\underbrace {(1+x+x^{2}+\dotsb )} _{\text{grapefruit}}\\&={\frac {1-x^{3}}{1-x}}\cdot {\frac {1-x^{4}}{1-x}}\cdot {\frac {1-x^{7}}{1-x}}\cdot {\frac {1}{1-x}}&({\text{geometric series formulas}})\\&=(1-x^{3})(1-x^{4})(1-x^{7})(1-x)^{-4}\\&=(1-x^{3}-x^{4}+x^{10}+x^{11}-x^{14})(1-x)^{-4}.\end{aligned}}$$ (The powers of $x$ in different brackets indicate the number of different fruits bought.) By Newton's generalized binomial theorem, the coefficients of $x^{15},x^{12},x^{11},x^{5},x^{4},x$ in $(1-x)^{-4}$ is ${\binom {-4}{15}}(-1)^{15}=816,{\binom {-4}{12}}(-1)^{12}=455,{\binom {-4}{11}}(-1)^{11}=364,{\binom {-4}{5}}(-1)^{5}=56,{\binom {-4}{4}}(-1)^{4}=35,{\binom {-4}{1}}(-1)=4$ respectively. Thus, the desired number of ways is the coefficient of $x^{15}$ in $G(x)$, which is $$816-455-364+56+35-4=84.$$

$\Box$

示例. 假设你掷了四个相同的骰子。证明有 136 种不同的结果，使得得到的数字之和能被 9 整除。

证明. 考虑生成函数$$G(x)=\underbrace {(x+x^{2}+x^{3}+x^{4}+x^{5}+x^{6})^{4}} _{4{\text{ dices}}}{\overset {\text{ GS }}{=}}x^{4}(1-x^{6})^{4}(1-x)^{-4}=(x^{4}-4x^{10}+6x^{16}-4x^{22}+x^{28})(1-x)^{-4}$$（$x$ 的幂表示得到的数字）。由于掷了四个骰子，因此数字之和的范围为 4 到 24。在这个数字范围内，9 和 18 可以被 9 整除。因此，所需结果的数量是$x^{9},x^{18}$ 在$G(x)$ 中的系数之和。现在，让我们逐一找到这些系数。

$x^{9}$ 的系数:

根据牛顿广义二项式定理，$x^{5}$ 在$(1-x)^{-4}$ 中的系数为$$-{\binom {-4}{5}}=56.$$ 因此，$x^{9}$ 的系数为 56。

$x^{18}$ 的系数:

根据牛顿广义二项式定理，$x^{14},x^{8},x^{2}$ 在 $(1-x)^{-4}$ 中的系数分别为 $${\binom {-4}{14}}=680,{\binom {-4}{8}}=165,{\binom {-4}{2}}=10$$。因此，$x^{18}$ 的系数为 $$680-4(165)+6(10)=80.$$

因此，结果数量为 $56+80=136$.

$\Box$

练习。 有 8 种不同的食物或饮料，分别是汉堡、鸡蛋、薯条、蛋糕、苹果派、苹果汁、橙汁和可乐。除非另有说明，组合可以包含相同项目多次。

(a) 假设每种食物或饮料只有 2 个库存。证明有 266 种不同的 4 项目组合。 (提示: 你可能会发现以下公式有用: $(1-x^{3})^{8}=1-8x^{3}+{\text{terms with order higher than }}x^{4}$ (这可以通过将 "$-x^{3}$" 看作定理中的 $x$ 来得到。)

(b) 假设每种食物价格 10 美元，每种饮料价格 5 美元。证明有 60 种不同的 20 美元组合。 (提示: 将 5 美元视为一个单位。那么，每种食物对应两个单位，每种饮料对应一个单位。利用这个想法，构造一个适当的生成函数，其幂为这些“单位”。之后，你可能会发现以下公式有用: $(1-x^{2})^{\alpha }=\sum _{k=0}^{\infty }{\binom {\alpha }{k}}(-x^{2})^{k}$ (通过将 "$x^{2}$" 看作广义二项式定理中的 "$x$" 来得到 (条件变为 $|x^{2}|<1$).)

证明

(a)

证明： 考虑生成函数 $$G(x)=\underbrace {(1+x+x^{2})^{8}} _{\text{food/drink item}}{\overset {\text{ GS }}{=}}(1-x^{3})^{8}(1-x)^{-8}=(1-8x^{3}+{\text{terms with order higher than }}x^{4})(1-x)^{-8}$$ （不同括号中的 $x$ 的幂代表选择的不同物品数量。）根据牛顿广义二项式定理，$x^{4},x$ 在 $(1-x)^{-8}$ 中的系数分别为 $${\binom {-8}{4}}=330,-{\binom {-8}{1}}=8$$ 。因此，$x^{4}$ 在 $G(x)$ （即我们想要的数字）中的系数为 $$330-8(8)=266.$$

$\Box$

(b)

证明： 考虑生成函数 $$G(x)=\underbrace {(1+x^{2}+x^{4}+\dotsb )^{5}} _{\text{food}}\underbrace {(1+x+x^{2}+\dotsb )^{3}} _{\text{drink}}=(1-x^{2})^{-5}(1-x)^{-3}$$ （不同括号中的 $x$ 的幂表示用于不同食品/饮料项目的 $5 的数量。对于每种食物，需要两个 $5，因此 $x$ 的幂每次增加 2）由于套餐总成本为 $20，即四个 $5，因此我们想要的数字由 $x^{4}$ 的系数给出。

现在，我们考虑 $x^{0},x^{2},x^{4}$ 在 $(1-x^{2})^{-5}$ 中的系数:（将 $x^{2}$ 看作广义二项式定理中的 $x$）

• $x^{0}:{\binom {-5}{0}}={\color {red}1}$
• $x^{2}:-{\binom {-5}{1}}={\color {blue}5}$
• $x^{4}=(x^{2})^{2}:{\binom {-5}{2}}={\color {darkgreen}15}$

现在，我们考虑 $x^{0},x^{2},x^{4}$ 在 $(1-x)^{-3}$ 中的系数:（对于 $x^{1},x^{3}$，我们不能用它来构造 $x^{4}$，因为只有 $x^{0},x^{2},x^{4}$（对于阶数最多为 $x^{4}$ 的项）在 $(1-x^{2})^{-5}$ 中可用）

• $x^{0}:{\binom {-3}{0}}={\color {darkgreen}1}$
• $x^{2}:{\binom {-3}{2}}={\color {blue}5}$
• $x^{4}:{\binom {-3}{4}}={\color {red}15}$

因此，$G(x)$ 中 $x^{4}$ 的系数是 $${\color {red}1(15)}+{\color {blue}5(6)}+{\color {darkgreen}15(1)}=60.$$

$\Box$

其他练习

练习。

文件:Ryu combo.gif

考虑游戏街头霸王。在本练习中，我们考虑不同的“连招”。为了简单起见，我们做以下假设

1. 只有四种类型的动作：拳（P）、脚（K）、前进（F）、跳跃（J）
2. 一个连招可以包含 2-4 个动作，这些动作可以是不同的，也可以是相同的，并且动作可以按任何顺序排列（顺序很重要）。例如，

• P不是连招，因为它只包含 1 个动作。
• PJJ 是一个连招。
• PPKF 是一个连招。
• KKKFJ不是连招，因为它包含 5 个动作。

(a) 有多少个不同的连招？

(b) 如果一个连招不能以跳跃开始，有多少个不同的连招？

(c) 证明如果一个连招必须包含至少一个“攻击动作”（即拳或脚），则有 308 个不同的连招。

解决方案

(a) 我们将情况分为 3 种情况。

情况 1：连招包含 2 个动作。然后，有 $\underbrace {4} _{\text{move 1}}\times \underbrace {4} _{\text{move 2}}=16$ 个不同的连招（每个动作有 4 种选择）。

情况 2：连招包含 3 个动作。然后，有 $\underbrace {4} _{\text{move 1}}\times \underbrace {4} _{\text{move 2}}\times \underbrace {4} _{\text{move 3}}=64$ 个不同的连招。

情况 3：连招包含 4 个动作。然后，有 $\underbrace {4} _{\text{move 1}}\times \underbrace {4} _{\text{move 2}}\times \underbrace {4} _{\text{move 3}}\times \underbrace {4} _{\text{move 4}}=256$ 个不同的连招。

由于这四种情况中没有相同的连招，因此不同的连招总数为 $16+64+256=336$。

(b) 我们将情况分为 3 种情况。

情况 1：连招包含 2 个动作。然后，有 $\underbrace {3} _{\text{move 1}}\times \underbrace {4} _{\text{move 2}}=12$ 个不同的连招（动作 1 不能是跳跃。所以，动作 1 只有 3 种选择）。

情况 2: 组合包含 3 个动作。然后，就有 $\underbrace {3} _{\text{move 1}}\times \underbrace {4} _{\text{move 2}}\times \underbrace {4} _{\text{move 3}}=48$ 种不同的组合。

情况 3: 组合包含 4 个动作。然后，就有 $\underbrace {3} _{\text{move 1}}\times \underbrace {4} _{\text{move 2}}\times \underbrace {4} _{\text{move 3}}\times \underbrace {4} _{\text{move 4}}=192$ 种不同的组合。

由于这四种情况下没有相同的组合，所以不同的组合总数是 $12+48+192=252$。

(c)

证明。 我们首先考虑包含 零 个攻击动作的不同组合。同样地，我们将情况分为 3 种。

情况 1: 组合包含 2 个动作。然后，就有 $\underbrace {2} _{\text{move 1}}\times \underbrace {2} _{\text{move 2}}=4$ 种不同的组合（每个动作有 2 种选择）。

情况 2: 组合包含 3 个动作。然后，就有 $\underbrace {2} _{\text{move 1}}\times \underbrace {2} _{\text{move 2}}\times \underbrace {2} _{\text{move 3}}=8$ 种不同的组合。

情况 3: 组合包含 4 个动作。然后，就有 $\underbrace {2} _{\text{move 1}}\times \underbrace {2} _{\text{move 2}}\times \underbrace {2} _{\text{move 3}}\times \underbrace {2} _{\text{move 4}}=16$ 种不同的组合。

由于这四种情况下没有相同的组合，所以包含零个攻击动作的不同组合总数是 $4+8+16=28$。因此，为了得到所需的组合数，我们将这个数字（28）从所有可能的不同组合数（336）中减去：$336-28=308$。

$\Box$

练习。

考虑一个与剑相关的游戏。在这个游戏中，有五级剑，从 1 到 5。为了获得一把等级 $n$ 的剑，玩家需要获得三把等级 $n-1$ 的剑，它们会自动组合成一把等级 $n$ 的剑。例如，为了获得一把等级 2 的剑，玩家需要获得三把等级 1 的剑。

玩家最初获得一把1级剑，并且可以使用最高等级的剑（每次只能使用一把剑）来击败怪物，以赚取金币。假设每个怪物的生命值（HP）为100，而使用等级为 $n$ 的剑，玩家每秒可以对怪物造成 $2^{n}$ 点伤害，也就是说，等级为 $n$ 的剑的 每秒伤害（DPS）为 $2^{n}$。例如，使用一把3级剑，DPS 为 8，因此需要 ${\frac {100}{8}}=12.5$ 秒来杀死一个怪物。杀死一个怪物后，玩家可以获得1枚金币，1级剑的价格是1枚金币（并且只能购买1级剑，但1级剑供应无限）。

证明玩家需要 812.5 秒才能获得一把 5 级剑。

证明

证明。 游戏过程如下

1. 当玩家拥有等级为 $n$ 的剑并且它是他的最高等级剑时，玩家使用它来杀死一些怪物，以获得足够的金币来购买 两把 额外的等级为 $n$ 的剑。之后，玩家将拥有三把等级为 $n$ 的剑，因此可以获得一把等级为 $n+1$ 的剑。
2. 重复步骤 1 直到玩家获得一把 5 级剑。

我们逐步考虑获得一把 5 级剑的过程

1. 使用 1 级剑杀死两只怪物，获得 2 枚金币，购买两把 1 级剑，然后玩家获得一把 2 级剑。（花费 ${\frac {200}{2}}=100$ 秒）
2. 使用 2 级剑杀死六只怪物，获得 6 枚金币，购买六把 1 级剑，然后玩家获得两把 2 级剑，因此获得一把 3 级剑。（花费 ${\frac {600}{2^{2}}}=150$ 秒）
3. 使用 3 级剑杀死 18 只怪物，获得 18 枚金币，购买 18 把 1 级剑，然后玩家获得 6 把 2 级剑，因此获得两把 3 级剑。之后，玩家获得一把 4 级剑。（花费 ${\frac {1800}{2^{3}}}=225$ 秒）
4. 使用 4 级剑杀死 54 只怪物，获得 54 枚金币，购买 54 把 1 级剑，然后获得 18 把 2 级剑，然后获得 6 把 3 级剑，然后获得 2 把 4 级剑。之后，玩家获得一把 5 级剑。（花费 ${\frac {5400}{2^{4}}}=337.5$ 秒）

因此，总共需要 $100+150+225+337.5=812.5$ 秒。

$\Box$

练习。 在某所大学，学生每个学期需要修五门课程，并且在 通过 八个学期后，学生毕业。另一方面，如果学生 不及格 两个学期 连续，他将被学校开除。（这里，通过一个学期是指通过该学期修的所有课程，不及格一个学期是指该学期至少有一门课程不及格。）我们将这种情况视为两个结果的有序序列：通过（P）和不及格（F）。例如，PPPFPFF 表示第 1、2、3 个学期通过，第 4 个学期不及格，第 5 个学期通过，第 6、7 个学期不及格。学生在第 7 个学期被开除，因此序列停止。另一方面，PPPPPPPPP 表示连续通过八个学期，并且学生毕业，因此序列也停止。

在本练习中，我们将统计在不同情况下有多少种不同的序列。

(a) 证明有 765 种不同的序列。

(b) 证明如果学生在 12 个学期后还没有毕业，也会被开除，那么有 466 种不同的序列。

证明

(a)

证明。 首先，请注意学生最终要么毕业，要么最终不及格。也就是说，序列最终会停止。换句话说，序列的长度必须是有限的。（实际上，可以通过重复模式“FP”八次来构建一个具有最大长度的序列：FPFPFPFPFPFPFPFP。此序列的长度为 16，我们可以看到它是最大长度，因为我们不能在中间添加更多“F”（否则学生将被开除），并且有八个“P”。）

为了统计序列的数量，我们考虑两种情况

情况 1：学生最终毕业。这意味着序列中包含八个“P”，但序列中没有两个连续的“F”。图形地，

        P P P P P P P P
       ^ ^ ^ ^ ^ ^ ^ ^ ^
^: position for at most one "F"

在由“^”指示的每个位置（9 个位置），我们可以选择 (i) 放入一个“F”；或 (ii) 不放入一个“F”。因此，每个位置都有两种方法。总共有九步，每步都有两种方法。因此，序列的数量为 $2^{9}=512$.

案例 2：学生最终不及格。这意味着序列中出现了连续的两个“F”。现在我们考虑有多少种不同的序列，使得最后两个学期是连续的两个“F”。以下是可能性

                           number of sequences    number of "P"s before "FF"
                   FF            1                      0

                 P FF            2                      1
                ^
               P P FF           2^2                     2
              ^ ^
             P P P FF           2^3                     3
            ^ ^ ^
           P P P P FF           2^4                     4
          ^ ^ ^ ^
         P P P P P FF           2^5                     5
        ^ ^ ^ ^ ^
       P P P P P P FF           2^6                     6
      ^ ^ ^ ^ ^ ^
     P P P P P P P FF           2^7                     7
    ^ ^ ^ ^ ^ ^ ^
^: position for at most one "F"
(semester just before "FF" must be "P", otherwise the "FF" occurs earlier)

因此，此情况下的序列数量为 $$1+2+2^{2}+2^{3}+2^{4}+2^{5}+2^{6}+2^{7}=253.$$

结合两种情况，可以得出有 $512+253=765$ 种不同的序列（两种情况中没有共同的序列）。

$\Box$

(b)

证明。在这种情况下，更明显的是序列最终必须停止，序列的最大长度为 12。

为了计算序列数量，我们同样考虑两种情况

案例 1：学生最终毕业。这意味着序列中有八个“P”，但序列中没有连续的两个“F”，并且序列的长度最多为 11。图形表示如下：

        P P P P P P P P
       ^ ^ ^ ^ ^ ^ ^ ^ ^
^: positions for placing at most 3 "F"s, with each contains at most one "F".

在由“^”表示的 9 个位置中，我们可以最多放置 3 个“F”，每个位置最多包含一个“F”。这等同于将 $k$ 个不可区分的球（“F”）放入 9 个可区分的单元格（由“^”表示）中，每个单元格容量为 1，其中 $k=0,1,2,{\text{ or }}3$。因此，序列数量为 $${\binom {9}{0}}+{\binom {9}{1}}+{\binom {9}{2}}+{\binom {9}{3}}=130.$$

案例 2：学生最终不及格。我们首先考虑序列中存在连续的两个“F”的情况（这意味着学生通过获得“FF”而不是在 12 个学期后没有 8 个“P”而不及格）。这里，我们还包括在获得“FF”后，长度仅为 12 的情况。

现在我们考虑有多少种不同的序列，使得最后两个学期是连续的两个“F”（长度最多为 12，包括最后的两个“F”）。以下是可能性

                           number of sequences    number of "P"s before "FF"
                   FF            1                      0              

                 P FF            2                      1
                ^
               P P FF           2^2                     2
              ^ ^
             P P P FF           2^3                     3
            ^ ^ ^
           P P P P FF           2^4                     4
          ^ ^ ^ ^
         P P P P P FF           2^5                     5   
        ^ ^ ^ ^ ^
       P P P P P P FF           9C4                     6   (place at most 4 "F"s)
      ^ ^ ^ ^ ^ ^
     P P P P P P P FF           9C3                     7   (place at most 3 "F"s)
    ^ ^ ^ ^ ^ ^ ^
(semester just before "FF" must be "P", otherwise the "FF" occurs earlier)

此情况下序列的数量为 $1+2+2^{2}+2^{3}+2^{4}+2^{5}+{\binom {9}{4}}+{\binom {9}{3}}=273$.

现在，我们考虑序列中不存在连续的两个“F”，但学生在 12 个学期后没有通过八个学期的情况（这意味着学生由于在 12 个学期后没有 8 个“P”而不及格）。以下是可能性

No. of  "P"s
     <5                           (impossible. Reason is similar to the case for 5 "P"s)

     5          P P P P P         (impossible. Even placing exactly one "F" at each position, the length is 11 < 12.)
               ^ ^ ^ ^ ^ ^

     6        P P P P P P         (place exactly 6 "F"s where each position contains at most one "F", making the length 12, and no "FF")
             ^ ^ ^ ^ ^ ^ ^  

     7      P P P P P P P         (place exactly 5 "F"s where each position contains at most one "F", making the length 12, and no "FF")
           ^ ^ ^ ^ ^ ^ ^ ^  

对于 6 个“P”的情况，序列数量为 ${\binom {7}{6}}=7$，对于 7 个“P”的情况，序列数量为 ${\binom {8}{5}}=56$。因此，总共有 $7+56=63$ 种序列。

由于这两种情况下没有共同的序列（一种情况包含“FF”，另一种情况不包含），在案例 2 中，总共有 $273+63=336$ 种序列。

结合两种情况，可以得出有 $130+336=466$ 种不同的序列（两种情况中没有共同的序列）。

$\Box$

练习。（注意：概率分布的概念本身不需要用于完成此练习。）

一位概率论课程的老师想从他的题库中创建一份课堂考试。课堂考试是关于概率分布的概念。题库中有 74 道与该概念相关的不同问题，它们分为以下类型

• 43 道关于离散分布的问题，包括

• 9 道关于伯努利分布的问题
• 5 道关于二项分布的问题
• 7 道关于负二项分布的问题
• 6 道关于几何分布的问题
• 3 道关于超几何分布的问题
• 13 道关于泊松分布的问题

• 31 道关于连续分布的问题，包括

• 10 道关于正态分布的问题
• 11 道关于指数分布的问题
• 3 道关于伽马分布的问题
• 2 道关于贝塔分布的问题
• 5 道关于均匀分布的问题

课堂考试将包含五道（不同的）问题。在以下内容中，当考虑方法数量时，问题的顺序并不重要，因为改变顺序不会影响考试的内容。

(a) 有多少种方法可以创建课堂考试？

(b) 有多少种方法可以创建包含 3 道关于离散分布的问题和 2 道关于连续分布的问题的课堂考试？

(c) 有多少种方法可以创建至少包含 1 道关于正态分布的问题的课堂考试？

(d) 有多少种方法可以创建一个包含正好一个关于正态分布的问题的课堂测试？

(e) 有多少种方法可以创建一个包含涵盖 5 种不同连续分布的问题的课堂测试？（即，包含关于 5 种不同连续分布的每种分布正好一个问题）

(f) 有多少种方法可以创建一个包含涵盖正好一种分布的问题的课堂测试？（即，包含关于单个分布的五个问题）

解决方案

由于测试中的问题是不同的，并且问题的顺序并不重要，因此创建课堂测试的过程等同于将 5 个不可区分的球（代表测试中的 5 个问题）放入 74 个可区分的单元格（代表题库中的 74 个不同问题）中，每个单元格的容量为 1（因为测试中的问题不能重复）。

(a) 方法数为 ${\binom {74}{5}}=16108764$.

(b) 根据要求，我们需要将 3 个球放入 43 个离散分布的单元格中，并将 2 个球放入 31 个连续分布的单元格中。因此，方法数为 ${\binom {43}{3}}\times {\binom {31}{2}}=5738565$.

(c) 根据要求，我们需要将 1 个球放入 10 个正态分布的单元格中（10 种方法），并将剩余的 4 个球放入剩余的 72 个单元格中（测试中包含一个关于正态分布的问题，并且不能重复）(${\binom {72}{4}}$ 种方法）。因此，方法数为 $10\times {\binom {72}{4}}=10287900$.

(d) 根据要求，我们需要将 1 个球放入 10 个正态分布的单元格中（10 种方法），并将剩余的 4 个球放入剩余的 63 个单元格中（排除所有与正态分布相关的問題）(${\binom {63}{4}}$ 种方法）。因此，方法数为 $10\times {\binom {63}{4}}=5956650$.

(e) 我们将根据该要求创建测试视为一个 5 步过程：将一个球放入 (i) 10 个单元格；(ii) 11 个单元格；(iii) 3 个单元格；(iv) 2 个单元格；(v) 5 个单元格。那么方法数为 $\underbrace {10} _{\text{norm}}\times \underbrace {11} _{\text{exp}}\times \underbrace {3} _{\text{gamma}}\times \underbrace {2} _{\text{beta}}\times \underbrace {5} _{\text{uniform}}=3300$.

(f) 为了使测试中的所有问题都只涵盖单个分布，该分布在题库中至少应有 5 道题。因此，对于超几何分布、伽马分布和贝塔分布来说这是不可能的。方法数由 $$\underbrace {\binom {9}{5}} _{\text{Ber}}+\underbrace {1} _{\text{bin}}+\underbrace {\binom {7}{5}} _{\text{NB}}+\underbrace {\binom {6}{5}} _{\text{geo}}+\underbrace {\binom {13}{5}} _{\text{Pois}}+\underbrace {\binom {10}{5}} _{\text{norm}}+\underbrace {\binom {11}{5}} _{\text{exp}}+\underbrace {1} _{\text{uniform}}=2150.$$

练习。 假设你去一家餐厅吃自助午餐。餐厅有 60 种不同的食物，包括

• 7 种沙拉
• 23 种肉类
• 6 种蔬菜
• 14 种甜点
• 10 种面包

假设每种食物都有无限份。每次拿食物时，你需要把它们放在盘子里。假设每次要放 3-5 种食物到盘子里。

(a) 证明有 8257997 种方法可以把食物放在盘子里。

(b) 一名学生提出以下论点来计算如果盘子里至少有一份肉类，那么放食物到盘子的方法数。

因为盘子里至少有一份肉类，所以需要将一个球放入代表 23 种肉类的 23 个单元格中（23 种方法）。之后，将剩余的球放入代表 60 种食物的 60 个可区分单元格中。

我们现在考虑不同食物数量的情况（将 $k=2,3,{\text{ or }}4$ 个不可区分的球（“盘子位置”）放入 60 个单元格中），得到

• 3 种食物：$23\times {}_{60}H_{2}=42090$
• 4 种食物：$23\times {}_{60}H_{3}=869860$
• 5 种食物：$23\times {}_{60}H_{4}=13700295$

所以，方法总数为 $42090+869860+13700295=14612245$.

解释为什么答案必须是错误的，并解释论点中存在哪些错误。(提示: 为了解释为什么答案必须是错误的，请将该数字与 (a) 中的数字进行比较。错误在于对乘法计数原理的使用不当。您可以阅读讨论该原理的部分以获得一些想法。）

解决方案

(a)

证明。 我们可以将 60 种不同的食物视为 60 个可区分的单元格，它们具有无限容量，并将“盘子位置”视为不可区分的球。放入单元格中的“盘子位置”数量取决于盘子里放了多少食物（3、4 或 5）。因此，我们将情况分为 3 种情况。

情况 1：3 种食物（球）。所以，我们将 3 个球放入 60 个单元格中。因此，方法数为 $_{60}H_{3}=37820$.

对于 4 种食物和 5 种食物的情况，情况类似，方法数分别为 $_{60}H_{4}=595665$ 和 $_{60}H_{5}=7624512$。因此，方法总数为 $37820+595665+7624512=8257997$.

$\Box$

(b) 答案一定是错的，因为这个数字比 (a) 中的数字还要大，但 (b) 中有一个额外的条件。通过增加一个额外条件，(a) 中的一些方式不被允许，并且不会有任何额外的方案。因此，这个数字应该小于 (a) 中的数字。

该论证的错误在于，当学生使用乘法计数原理来获得食物数量时，"任务"是不可区分的，这导致了多条决策路径导致相同的结果。让我们考虑一个包含 3 种食物的例子。

1. 第一个决策路径：第一步，将一个球放到肉类 1 中，第二步，将两个球分别放到肉类 2、3 中。
2. 第二个决策路径：第一步，将一个球放到肉类 2 中，第二步，将两个球分别放到肉类 1、3 中。

因此，结果是三个 不可区分 的球分别进入肉类 1、2、3，无论哪条决策路径都是如此。

但是，在使用乘法计数原理时，我们假设每条决策路径都只产生一个结果，因此学生得到的数字确实是决策路径的数量。但有些路径会导致相同的结果，因此这个数字不是方案总数。

练习。 假设你抛硬币 10 次，得到一个结果序列。例如，序列 HTHHTHTTTT 表示第 1、3、4、6 次抛出正面，第 2、5、7、8、9、10 次抛出反面。

(a) 有多少个不同的序列？

(b) 证明由恰好五次（不是六次、七次，等等）连续 正面组成的不同序列的数量是 64。

解决方案

(a) 对于每一次抛掷，都有两种结果：正面 (H) 或反面 (T)。因此，不同的序列数量是 $2^{10}=1024$.

(b)

证明。 为了让正面出现 恰好 五次连续，"HHHHH" 需要被 "T" 包围。有六种情况

情况 1：第 1、2、3、4、5 次抛出正面 (HHHHHT????)。

情况 2：第 2、3、4、5、6 次抛出正面 (THHHHHT???)。

情况 3：第 3、4、5、6、7 次抛出正面 (?THHHHHT??)。

情况 4：第 4、5、6、7、8 次抛出正面 (??THHHHHT?)

情况 5：第 5、6、7、8、9 次抛出正面 (???THHHHHT)

情况 6：第 6、7、8、9、10 次抛出正面 (????THHHHH)

上述情况中，只有标记为 "?" 的抛掷才有自由度。对于其他抛掷，结果是固定的。在上述两种情况中，有四个 "?"（因此序列数量是 $2^{4}=16$），而对于剩余的情况，有三个 "?"（因此序列数量是 $2^{3}=8$）。因此，序列数量为 $$2\cdot 16+4\cdot 8=64.$$

$\Box$

练习。 考虑一个 角色扮演游戏 (RPG)，玩家需要在游戏开始时创建一个角色，并分配一些 技能点 给角色。假设玩家有 10 个技能点，角色有五个属性，如下所示

1. 生命值
2. 攻击力
3. 防御力
4. 速度
5. 幸运

玩家可以给每个属性分配 1-5 个技能点，我们将分配 10 个技能点给五个属性称为一个 加点。

(a) 证明不同的加点数量是 121。（提示：考虑使用生成函数。）

(b) 有多少种不同的加点方式，其中分配给幸运属性的技能点为 5 个？

(c) 假设如果分配给攻击力和速度属性的技能点至少为 3 个，那么加点方式称为 攻击加点，如果分配给生命值和防御力属性的技能点至少为 3 个，那么加点方式称为 防御加点。有多少种攻击加点方式？有多少种防御加点方式？攻击加点方式和防御加点方式的数量是否相等？

(d) 假设玩家可以在角色创建阶段留下一些 10 个技能点不分配，并在游戏中后期分配这些技能点。尽管如此，每个属性仍然需要分配至少 1 个技能点。证明在角色创建阶段分配技能点有 247 种方法。

解决方案

(a)

证明。 我们可以把 10 个技能点看作 10 个不可区分的球，五个属性看作五个容量为 5 的可区分的盒子，每个盒子中必须至少包含一个球。为了方便，我们考虑以下生成函数：$$G(x)=(x+x^{2}+x^{3}+x^{4}+x^{5})^{5}=\left({\frac {x(1-x^{5})}{1-x}}\right)^{5}=x^{5}(1-x^{5})^{5}(1-x)^{-5}=x^{5}({\color {blue}1}-{\color {red}5}x^{5}+{\text{terms with order higher than }}x^{5})(1-x)^{-5}$$（不同括号中 $x$ 的幂表示分配给不同属性的技能点数量。）（这里，我们对 $(1-x^{5})^{5}$ 应用牛顿广义二项式定理。）由于玩家只有 10 个技能点，因此不同的加点数量是 $x^{10}$ 在 $G(x)$ 中的系数。

根据牛顿广义二项式定理，$x^{0},x^{5}$ 在 $(1-x)^{-5}$ 中的系数分别为 ${\binom {-5}{0}}={\color {red}1},-{\binom {-5}{5}}={\color {blue}126}$。因此，构建数量，即 $x^{10}$ 在 $G(x)$ 中的系数为 $${\color {blue}126\cdot 1}-{\color {red}5\cdot 1}=121.$$

$\Box$

(b) 我们可以再次使用生成函数方法：$$G(x)=(x+x^{2}+x^{3}+x^{4}+x^{5})^{\color {darkgreen}4}\underbrace {(x^{5})} _{\text{luck}}=x^{4}(1-x^{5})^{4}(1-x)^{-4}x^{5}=x^{9}({\color {blue}1}+{\text{terms with order higher than }}x)(1-x)^{-4}$$ （我们写下高于 $x$ 的项，因为对于这些项，在乘以 $x^{9}$ 后，其阶数至少为 $x^{11}$，因此我们对此不感兴趣。）根据牛顿广义二项式定理，$(1-x)^{-4}$ 中 $x$ 的系数为 $-{\binom {-4}{1}}=4$。因此，不同构建的数量（即 $G(x)$ 中 $x^{10}$ 的系数）为 ${\color {blue}4\cdot 1}=4$。

另一种方法：或者，我们可以使用以下更“聪明”的方法。由于要分配 5 个技能点给幸运，并且每个生命值、攻击、防御和速度分别必须分配 1 个技能点。因此，只剩下 1 个技能点可以自由分配，而所有其他技能点都是固定的。这个技能点要分配给生命值、攻击、防御和速度中的一个（不能分配给幸运，因为幸运已经有了五个（最大）技能点）。因此，有四种分配方法。所以，不同构建的数量是 4。

(c) 由于对称性，攻击流派的数量与防御流派的数量相同。（每种流派基本上有相同的需求。不同的属性除了名称外，在本质上没有任何实际区别。）所以，我们只需关注攻击流派。我们再次考虑生成函数方法： $${\begin{aligned}G(x)&=\underbrace {(x^{3}+x^{4}+x^{5})^{2}} _{{\text{atk }}\&{\text{ spd}}}(x+x^{2}+x^{3}+x^{4}+x^{5})^{3}\\&=\left({\frac {x^{3}(1-x^{3})}{1-x}}\right)^{2}\left({\frac {x(1-x^{5})}{1-x}}\right)^{3}\\&=x^{9}(1-x^{3})^{2}(1-x^{5})^{3}(1-x)^{-5}\\&=x^{9}({\color {blue}1}+{\text{terms with order higher than }}x)({\color {blue}1}+{\text{terms with order higher than }}x)(1-x)^{-5}.\\\end{aligned}}$$ 根据牛顿广义二项式定理，$x$ 在 $(1-x)^{-5}$ 中的系数是 $-{\binom {-5}{1}}=5$。因此，不同流派的數量，也就是 $x^{10}$ 在 $G(x)$ 中的系数，是 5。

(d)

证明。 我们回顾生成函数 $G(x)$ 在 (a) 部分：$$G(x)=x^{5}(1-5x^{5}+{\text{terms with order higher than }}x^{5})(1-x)^{-5}.$$ 由于并非所有十个技能点都需要分配，但每个属性都必须分配至少一个技能点，因此至少分配了 5 个技能点（最多分配 10 个技能点）。因此，我们将考虑所有可能性中构建的数量（分配了 5、6、7、8、9、10 个技能点），并将它们加起来。该数量由生成函数中 $x^{5},x^{6},x^{7},x^{8},x^{9},x^{10}$ 的系数的 和 给出。 $G(x)$。

根据牛顿广义二项式定理，$$(1-x)^{-5}=(1+5x+15x^{2}+35x^{3}+70x^{4}+126x^{5}+{\text{terms with order higher than }}x^{5}).$$ 因此，生成函数由 $$G(x)=x^{5}(1-5x^{5}+{\text{terms with order higher than }}x^{5})(1+5x+15x^{2}+35x^{3}+70x^{4}+126x^{5}+{\text{terms with order higher than }}x^{5})$$ 因此，系数之和为 $$\underbrace {1\cdot 1} _{x^{5}}+\underbrace {1\cdot 5} _{x^{6}}+\underbrace {1\cdot 15} _{x^{7}}+\underbrace {1\cdot 35} _{x^{8}}+\underbrace {1\cdot 70} _{x^{9}}+\underbrace {121} _{x^{10}{\text{ by (a)}}}=247.$$

$\Box$

练习。 一组 12 人一起去茶馆共进午餐。他们点了一系列的 点心 菜肴（一种中国菜），包括：

• 三种不同的 饺子

• 虾饺
• 烧卖
• 馄饨

• 三种不同的 包点

• 叉烧包
• 奶油包
• 莲蓉包

• 四种不同的 卷

• 春卷
• 腐皮卷
• 牛肉肠粉
• 虾肠粉

圆桌。

假设点心菜肴被放置在一个圆桌子上，以圆形排列在十个位置（见下图），人们围坐在桌子旁吃这些菜肴。

                                  N
        * * *  *                  ^
      *    1     *              W<+>E
    * 10       2  *               v
   *             3 *              S
   * 9              *
   *              4 *
    *  8        5  *
     *    7  6    *
       * * * *  * 
The region bounded by "*" is the circular table, the numbers indicate the ten dishes.

使用指南针方向（N、E、S、W），十个菜肴的位置和 12 个人的座位都是可区分的。

(a) 以这种方式排列十道菜有多少种不同的方法？

(b) 以这种方式排列 12 人的座位有多少种不同的方法？

(c) 假设三个饺子必须放在一起，三个包点也必须放在一起。但饺子和包点必须分开（即，饺子和包点不能彼此相邻），用四个卷分开。证明有 25920 种方法可以根据此要求排列十道菜？ (提示: 我们将这种情况说明如下：

                                  N
        * * *  *                  ^
      *    D     *              W<+>E
    * R        D  *               v
   *             D *              S
   * B              *
   *              R *
    *  B        R  *
     *    B  R    *
       * * * *  * 
D: dumpling
B: bun
R: roll
(1 R in the gap "from B to D" (viewed clockwise). The gap "from B to D" is the upper one, and the gap "from D to B" is the lower one.)

除了上面所示的方式外，还有两种可能的方式可以将饺子和包点分开。确定它们，并计算每种情况下的排列数量。）

解决方案

(a) 方法数为 $10!=3628800$。 (将 10 道不同的菜肴放入 10 个可区分的位置)

(b) 方法数为 $12!=479001600$。 (将 12 个不同的人放置在 12 个可区分的座位上)

(c)

证明。 提示中的图表显示了一种将饺子和包点分开的

                                  N
        * * *  *                  ^
      *    R     *              W<+>E
    * R        D  *               v
   *             D *              S
   * B              *
   *              D *
    *  B        R  *
     *    B  R    *
       * * * *  * 
(2 R in the gap "from B to D" (viewed clockwise))

                                  N
        * * *  *                  ^
      *    R     *              W<+>E
    * R        D  *               v
   *             D *              S
   * R              *
   *              D *
    *  B        R  *
     *    B  B    *
       * * * *  * 
(3 R in the gap "from B to D" (viewed clockwise))

这里，我们逐一考虑三种情况。

情况 1："1 R" 情况。我们首先关注图中所示的特殊情况。排列数量为 $$\underbrace {3!} _{D}\times \underbrace {4!} _{R}\times \underbrace {3!} _{B}=864.$$ 但我们可以旋转圆桌，为每个这样的排列生成 9 个更多 的排列。因此，总数为 $$10\times 864=8640.$$

对于 "2 R" 情况和 "3 R" 情况，情况类似，因此总数也是 8640。这三种情况没有共同的排列方式。因此，总共有 $8640\times 3=25920$ 种排列。

$\Box$