组合数学
§4.1 基本组合原理
我们需要掌握的一个重要方法是分情况讨论(casework)。分情况讨论就是把计数问题拆分成若干不同情形，分别计算每种情形，最后把所有结果相加。这种方法在AMC和AIME中都非常常见。
定义 4.1.1
补集计数(Complementary Counting)是先计算我们不想要的情况的数量，再用总数减去它。例如，若想知道一个40人的班级里有多少男生，可以先数出女生人数，再用40减去女生人数，就得到男生人数。
\( \left( \begin{array}{l} n \\ k \end{array}\right) \) 表示从1到 \( n \) 的集合中选出大小为k的子集的数量，也表示从 \( n \) 个人中选出 \( k \) 个人的方法数。
集合 \( 1,2,\ldots n \) 的排列数为 \( n! \) (!表示阶乘)
定理 4.1.2
当单词中有重复字母时，有多少种不同的排列方式？
假设总共有 \( n \) 个字母，其中字母 \( a,{x}_{b} \) 出现 \( {x}_{a} \) 次，字母 \( b,{x}_{c} \) 出现 \( a,{x}_{b} \) 次，字母 \( c \) 出现 \( b,{x}_{c} \) 次，依此类推，直到字母 \( z \) 出现 \( {x}_{z} \) 次。
由此得到方程 \( {x}_{a} + {x}_{b} + {x}_{c} + \ldots + {x}_{z} = n \)
字母的排列方式共有 \( \frac{n!}{{x}_{a}! \cdot {x}_{b}! \cdot {x}_{c}! \cdot \ldots \cdot {x}_{b}!} \) 种
例 4.1.3
a. 单词SANDWICH的字母有多少种不同的排列方式？
b. 单词SYNONYMS的字母有多少种不同的排列方式？
a的解答:单词sandwich共有8个字母，且所有字母均不重复，因此无需除以任何重复因子。故其排列数为8!，即40320。
b的解答。在单词SYNONYMS(共8个字母)中，S重复出现(出现2次)， \( \mathrm{Y} \) 重复出现(出现2次)， \( \mathrm{N} \) 重复出现(出现2次)。重新排列这些字母的方法数就是 \( \frac{8!}{2! \cdot 2! \cdot 2!} \) ，即 \( \frac{8!}{8} \) ，结果为7!。
问题4.1.4——某数学组织正在制作一套纪念车牌。每块车牌包含一个由五个字符组成的序列，这些字符选自AIME中的四个字母和2007中的四个数字。任何字符在序列中出现的次数都不能超过它在AIME四个字母或2007四个数字中出现的次数。若一套车牌中每个可能的序列恰好出现一次，则该套车牌共有
\( \mathrm{N} \) 块车牌。求 \( \frac{N}{10} \) 。
来源:2007 AIME
解答:本题中，我们需要从AIME和2007中选取5个字符。已知每个字母在车牌中最多出现一次，而数字0最多可出现两次。我们按0出现的次数分三种情况讨论。
情况1:不含0。
此时，5个字符必须来自AIME和27。因此，我们只需从6个字符的池中选出5个。
\( \left( \begin{array}{l} 6 \\ 5 \end{array}\right) = 6 \)
然而，我们必须乘以5!，即排列数。6×5!等于720。
情况2:含一个0。
此时，由于已知一个字符是0，我们只需从AIME和27中再选4个字符。然后乘以5!，即排列数。 \( \left( \begin{array}{l} 6 \\ 4 \end{array}\right) \cdot 5! = {1800} \)
情况3:含两个 \( 0\mathrm{\;s} \)
现在已有两个0，我们只需再从AIME和27中选3个字符。 \( \left( \begin{array}{l} 6 \\ 3 \end{array}\right) \)
但此时不能直接乘以5!，因为并非所有待排列的数字都互不相同！0重复了，因此必须除以0出现次数的阶乘，即2!。
\( \left( \begin{array}{l} 6 \\ 3 \end{array}\right) \cdot \frac{5!}{2!} = {1200} \)
将各情况结果相加得 \( {720} + {1800} + {1200} \) ，即3720。
再除以10得到372。
问题4.1.5——有多少个四位正整数至少含有一个数字2或3？
(C) 4903 (D) 4904 (E) 5416
来源:2006 AMC 10
解答:本题我们将采用补集计数(complementary counting)技巧。当题干出现“至少一个”这类短语时，往往是使用补集计数的信号。
与其直接求含有至少一个2或3的数字个数，不如先求其反面——不含2也不含3的数字个数，再用总数减去
这个数即可。
数字0–9共10个，千位不能为0，且也不能为2或3，因此千位有7种可能。
其余三位每位均可取0–9，但排除2和3，故每位有8种可能。
各位独立，直接相乘得 \( 7 \cdot 8 \cdot 8 \cdot 8 \) ，即3584。
四位数的总数也可用类似方法求得:千位有9种可能，其余三位各有10种可能，共9000个。
因此答案为 \( {9000} - {3584} = \mathbf{{5416}}\left( \mathbf{E}\right) \) 。
问题4.1.6:有多少个由1和3组成的有序序列之和为16？(例如1,3,3,3,3,3和1,3,1,3,1,3,1,3)
来源:2012 SMT
解答:设1出现 \( x \) 次，3出现 \( y \) 次，则总和可写为 \( x + {3y} = {16} \)
总共有 \( x + y \) 个元素，其中1出现 \( x \) 次，3出现 \( y \) 次，排列方式数为 \( \frac{\left( {x + y}\right) !}{x! \cdot y!} \) ，即 \( \left( \begin{matrix} x + y \\ y \end{matrix}\right) \) 。
利用方程 \( x + {3y} = {16} \) ，可能的解为
| \( x \) | \( y \) | 重排数 |
| 1 |  | |
| 4 | ||
| 2 | ||
| 1 | ||
| 0 |
现在我们将最右列的所有数值相加，得到277。
问题4.1.7 定义一个有限整数集合的和为该集合中所有元素的和。设 \( \mathrm{D} \) 为700的所有正因数(positive divisors)的集合。问:D有多少个非空子集的和为偶数？(请尽可能化简)
来源:2015 MMATHS
解答:本题中，我们首先对700进行质因数分解，得到 \( {2}^{2} \cdot {5}^{2} \cdot 7 \)
接下来，我们将所有因数分为偶数和奇数两类。一个偶因数必须包含2的幂次，即2的指数只能是1或2(共2种可能)。再乘以 \( {5}^{2} \cdot 7 \) 的因数个数6，得到700共有12个偶因数和6个奇因数。
由此可知，要使子集的和为偶数，其中奇因数的个数必须为偶数。这意味着子集中奇因数的个数可以是0、2、4或6。对于偶因数则没有限制，因为任意数量的偶数相加结果仍为偶数。
情况1:0个奇因数:此时我们只需计算从奇因数中选取0个的方法数 \( \left( \begin{array}{l} 6 \\ 0 \end{array}\right) \) ，再乘以从偶因数中任意选取的方法数 \( {2}^{12} \) ，得到 \( {2}^{12} \cdot \left( \begin{array}{l} 6 \\ 0 \end{array}\right) \)
情况2:2个奇因数:此时我们只需计算从奇因数中选取2个的方法数 \( \left( \begin{array}{l} 6 \\ 2 \end{array}\right) \) ，再乘以从偶因数中任意选取的方法数 \( {2}^{12} \) ，得到 \( {2}^{12} \cdot \left( \begin{array}{l} 6 \\ 2 \end{array}\right) \)
情况3:4个奇因数:此时我们只需计算从奇因数中选取4个的方法数 \( \left( \begin{array}{l} 6 \\ 4 \end{array}\right) \) ，再乘以从偶因数中任意选取的方法数 \( {2}^{12} \) ，得到 \( {2}^{12} \cdot \left( \begin{array}{l} 6 \\ 0 \end{array}\right) \)
情况4:6个奇因数:此时我们只需计算从奇因数中选取6个的方法数 \( \left( \begin{array}{l} 6 \\ 6 \end{array}\right) \) ，再乘以从偶因数中任意选取的方法数 \( {2}^{12} \) ，得到 \( {2}^{12} \cdot \left( \begin{array}{l} 6 \\ 6 \end{array}\right) \)
我们将以上所有情况的数值相加，得到 \( {2}^{12}\left( {\left( \begin{array}{l} 6 \\ 0 \end{array}\right) + \left( \begin{array}{l} 6 \\ 2 \end{array}\right) + \left( \begin{array}{l} 6 \\ 4 \end{array}\right) + \left( \begin{array}{l} 6 \\ 6 \end{array}\right) }\right) \) ，即 \( {2}^{17} \) 。
然而，由于子集必须非空，我们需要减去既不含奇因数也不含偶因数的空集情况，最终答案为 \( {2}^{17} - 1 \) ，即131071。
问题4.1.8 - 求 \( \{ 1,2,3,4,5,6,7,8\} \) 的子集中，有多少个既不是 \( \{ 1,2,3,4,5\} \) 的子集，也不是 \( \{ 4,5,6,7,8\} \) 的子集。
来源:2017 AIME
解答:本题中，我们再次使用补集计数(complementary counting)的技巧。
任何大小为 \( \mathrm{N} \) 的集合的子集数量为 \( {2}^{N} \) 。因此，在本例中，1到8的集合共有 \( {2}^{8} \) 个子集，即256个。
现在我们将从另外两个集合中减去所有子集。由于它们各有5个元素，每个集合可形成 \( {2}^{5} \) 即32个可能的子集。我们将该数乘以2得到64。
我们现在用256减去64得到192。然而，我们尚未完成。需要记住，所列的两个大小为5的集合有2个共同元素(4和5)。我们必须把由4和5构成的所有可能集合加回来，因为我们减了两次。这两个元素可构成4个子集，因此我们将它们加回。
最终答案为 \( {192} + 4 \) ，即196。
问题4.1.9 设 \( a, b, c, d \) 为从集合 \( 0,1,\ldots ,{2019} \) 中选取的四个不一定互不相同的整数。 \( \left( {a + b}\right) \left( {c + d}\right) + \left( {a + c}\right) \left( {b + d}\right) + \) \( \left( {a + d}\right) \left( {b + c}\right) \) 能被4整除的概率是多少？
来源:2019 CMC 10
解答:本题中，我们先展开表达式 \( \left( {a + b}\right) \left( {c + d}\right) + \left( {a + c}\right) (b + \) \( d) + \left( {a + d}\right) \left( {b + c}\right) \) 得到 \( 2\left( {{ab} + {ac} + {ad} + {bc} + {bd} + {cd}}\right) \) 。
由此，若要让4整除该表达式，只需检查2是否整除 \( {ab} + {ac} + {ad} + {bc} + {bd} + {cd} \) ，因为2已整除整个表达式。
我们可以为变量 \( a, b, c, d \) 代入模2的数值，观察何时结果为0 \( {\;\operatorname{mod}\;2} \) 。
情况1:所有4个变量模2均为0
此时，我们将这4个变量均代入0，得到表达式结果为0 \( {\;\operatorname{mod}\;2} \) 。
所有数模2为0的概率即为 \( {\left( \frac{1}{2}\right) }^{4} \) ，即 \( \frac{1}{16} \) 。我们求得单个数模2为0的概率为 \( \frac{1}{2} \) ，因为总共有2020个数，其中1010个为偶数，故概率为 \( \frac{1}{2} \) 。
情况2:3个变量模2为0，1个变量模2为1
此时，可设 \( a, b, c \) 模2为0，而 \( d \) 模2为1。代入表达式后， \( {ab} + {ac} + {ad} + {bc} + {bd} + {cd} \) 模2为0。
此情况发生的概率即为 \( \frac{1}{16} \) 。然而，需乘以排列方式数，因为 \( a, b, c \) 或 \( d \) 均可为模2为0的那个。排列方式共有4种，因此总概率为 \( 4 \cdot \frac{1}{16} \) ，即 \( \frac{1}{4} \) 。
情况3:当2个数模2为0或仅1个数模2为0时， \( {ab} + {ac} + {ad} + {bc} + {bd} + {cd} \) 的最终表达式模2为1，故该情况概率为0。
情况4:当所有4个变量模2余1时，我们的最终表达式 \( {ab} + {ac} + {ad} + {bc} + {bd} + {cd} \) 模2余0。
任一变量模2余1的概率就是 \( \frac{1}{2} \) ，因为有4个变量，我们将其取4次方得到 \( \frac{1}{16} \) 。
总概率为 \( \frac{1}{16} + \frac{1}{4} + \frac{1}{16} = \frac{3}{8}\left( \mathbf{C}\right) \) 。
问题4.1.10——合唱团指挥要从6名男高音和8名男低音中选出若干人组成一个小组。唯一的要求是男高音与男低音的人数之差必须是4的倍数，且小组中至少要有1人。设 \( N \) 为可选取的不同小组数。求 \( N \) 除以100的余数。
(A) 47 (B) 48
来源:2021 AMC
解答:本题的主要情况取决于男高音与男低音的人数之差。
情况1:男高音与男低音的人数之差为0。这意味着男高音与男低音的人数必须相等。此情形下所有可能情况的总和为 \( \left( \begin{array}{l} 6 \\ 1 \end{array}\right) \cdot \left( \begin{array}{l} 8 \\ 1 \end{array}\right) + \left( \begin{array}{l} 6 \\ 2 \end{array}\right) \cdot \left( \begin{array}{l} 8 \\ 2 \end{array}\right) + \left( \begin{array}{l} 6 \\ 3 \end{array}\right) \cdot \left( \begin{array}{l} 8 \\ 3 \end{array}\right) + \left( \begin{array}{l} 6 \\ 4 \end{array}\right) \cdot \left( \begin{array}{l} 8 \\ 4 \end{array}\right) + \left( \begin{array}{l} 6 \\ 5 \end{array}\right) \cdot \left( \begin{array}{l} 8 \\ 5 \end{array}\right) + \left( \begin{array}{l} 6 \\ 6 \end{array}\right) \cdot \left( \begin{array}{l} 8 \\ 6 \end{array}\right) \) 。
上述总和为3002。
情况2:男高音与男低音的人数之差为4。
这意味着男高音与男低音的人数可分别为 \( \left( {0,4}\right) ,\left( {1,5}\right) ,\left( {2,6}\right) \) 、 \( \left( {3,7}\right) ,\left( {4,8}\right) ,\left( {4,0}\right) ,\left( {5,1}\right) \) 以及(6,2)。
上述情形下所有可能情况的总和为 \( \left( \begin{array}{l} 6 \\ 0 \end{array}\right) \cdot \left( \begin{array}{l} 8 \\ 4 \end{array}\right) + \left( \begin{array}{l} 6 \\ 1 \end{array}\right) \cdot \left( \begin{array}{l} 8 \\ 5 \end{array}\right) + \left( \begin{array}{l} 6 \\ 2 \end{array}\right) \cdot \left( \begin{array}{l} 8 \\ 6 \end{array}\right) + \)
\[ \left( \begin{array}{l} 6 \\ 3 \end{array}\right) \cdot \left( \begin{array}{l} 8 \\ 7 \end{array}\right) + \left( \begin{array}{l} 6 \\ 4 \end{array}\right) \cdot \left( \begin{array}{l} 8 \\ 8 \end{array}\right) + \left( \begin{array}{l} 6 \\ 4 \end{array}\right) \cdot \left( \begin{array}{l} 8 \\ 0 \end{array}\right) + \left( \begin{array}{l} 6 \\ 5 \end{array}\right) \cdot \left( \begin{array}{l} 8 \\ 1 \end{array}\right) + \left( \begin{array}{l} 6 \\ 6 \end{array}\right) \cdot \left( \begin{array}{l} 8 \\ 2 \end{array}\right) . \]
上述总和为1092。
情况3:男高音与男低音的人数之差为8。
这意味着男高音(tenor)的数量必须为0，而男低音(bass)的数量为8。这种情况的数量就是 \( \left( \begin{array}{l} 6 \\ 0 \end{array}\right) \cdot \left( \begin{array}{l} 8 \\ 8 \end{array}\right) \) ，即1。
因此，最终答案为 \( {3002} + {1092} + 1 \) ，即4095。我们的答案(模100)就是95(D)。
问题延伸:上面展示的解法是一个典型的分类讨论(casework)示例。然而，这并非唯一解法。等你后续学到组合恒等式(combinatorial identities)后，请尝试用更简洁的方法解决此题！
§4.2 集合与容斥原理(PIE)
定义 4.2.1
PIE是AMC中一个极其重要的主题，它代表容斥原理(Principal of Inclusion and Exclusion)。
让我们假设有两个集合A和B。集合A中的数字是3、4、5和6，而集合 \( \mathrm{B} \) 中的数字是5、6、8、9。求这两个集合的并集的方法是 \( \left| {{A}_{1} \cup {A}_{2}}\right| = \left| {A}_{1}\right| + \left| {A}_{2}\right| - \left| {{A}_{1} \cap {A}_{2}}\right| \)
|| 表示这些集合中的元素个数。最右侧的符号 \( \cap \) (交集符号)表示两个集合共有的元素个数。在我给出的示例中，这意味着两个集合的并集等于集合 A 的元素个数加上集合 B 的元素个数，然后再减去两个集合共有的元素个数。
当集合数量超过两个时同样适用。下方展示了存在3个集合时的表示方法。
\[ \left| {{A}_{1} \cup {A}_{2} \cup {A}_{3}}\right| = \left| {A}_{1}\right| + \left| {A}_{2}\right| + \left| {A}_{3}\right| - \left| {{A}_{1} \cap {A}_{2}}\right| - \left| {{A}_{2} \cap {A}_{3}}\right| - \left| {{A}_{3} \cap {A}_{1}}\right| + \left| {{A}_{1} \cap {A}_{2} \cap {A}_{3}}\right| \]
问题4.2.2 - 设 \( \mathcal{S} \) 为集合 \( \{ 1,2,3,\ldots ,{10}\} \) ，设 \( n \) 为 \( \mathcal{S} \) 的两两非空且互不相交子集的对数(互不相交集合定义为没有共同元素的集合)。求 \( n \) 除以1000所得的余数。来源:2002 AIME
解法:在本题中，由于数字1到10中的每一个都可以被归入第一集合、第二集合，或都不属于；因此每个数字有三种去向。又因为每个数字的归属彼此独立，我们只需将3的10次方即可。
然而， \( {3}^{10} \) 包含了第一种集合为空或两个集合都为空的情况。如果第一种集合为空，那么放置其余数字的方法共有 \( {2}^{10} \) 种，因为这些数字只能进入第二种集合或根本不被放置。
\( {3}^{10} - 2 \cdot {2}^{10} \)
我将2乘以 \( {2}^{1}0 \) ，因为 \( {2}^{1}0 \) 表示当第一组或第二组为空时的重排数。
然而，由于容斥原理(PIE)，我们必须给这个答案加1，因为我们把“两者皆空”的情况减了两次。
\( {3}^{10} - 2 \cdot {2}^{10} + 1 = {57002} \) 即 \( \mathbf{2}\left( {\;\operatorname{mod}\;{100}}\right) \) 。
§4.3 路径计数与双射(Bijections)
在计算正方形网格上必须向上走 \( \mathrm{m} \) 格、向右走 \( \mathrm{n} \) 格的路径数量时，我们可以使用双射(bijection)技巧来求出所有可能的方式。
例4.3.1
若要从(0,0)移动到(m, n)，且只能向上或向右移动，共有多少种走法？
由于我们知道终点是(m, n)，因此在路径中必须向上走1格共n次，向右走1格共 \( \mathrm{m} \) 次。于是我们有UUU…(共n次)和RRRRR(共 \( \mathrm{m} \) 次)，其中 \( \mathrm{U} \) 表示向上， \( \mathrm{R} \) 表示向右。
这相当于对一个单词的字母进行重排。我们共有 \( \mathrm{m} + \mathrm{n} \) 个字母，再除以重复字母的数量，并对其取阶乘。
利用重排单词并考虑字母重复的公式，我们得到
\( \frac{\left( {m + n}\right) !}{m! \cdot n!} = \left( \begin{matrix} m + n \\ m \end{matrix}\right) \)
双射(bijection)的精髓在于把一个复杂问题提炼成一个更简单的思想，从而更容易求解。接下来我们将通过大量练习来掌握这一主题，因为最好的学习方法就是不断实践。这里没有简单的公式可以一蹴而就。
问题4.3.2——一枚公平骰子掷四次。后三次掷出的点数均不小于前一次掷出的点数的概率可表示为 \( m/n \) ，其中 \( m \) 与 \( n \) 为互质的正整数。求 \( m + n \) 。来源:2001 AIME
解:在本题中，由于每次掷出的点数必须递增，这意味着随着掷骰次数“向右”增加，点数也必须“向上”增加。这相当于一个宽4格(对应第1到第4次掷骰)、高6格(对应点数1到6)的网格。
我们从点(0,1)出发，它表示第0次掷骰且最小点数为1。现在只需计算到点(4,6)的路径数，即上述矩形。该矩形长5格、宽4格，因此共有 \( \left( \begin{array}{l} 9 \\ 5 \end{array}\right) \) 即(126)种走法。
由于每次掷骰有6种可能结果，四次掷骰共有 \( {6}^{4} \) 种结果，这就是我们的分母。
我们的答案为 \( \frac{126}{{6}^{4}} = \frac{7}{72} \) ，分子与分母之和为79。
在本题中，我们把骰子掷出的序列与简单网格建立了双射(bijection)。这类问题通常需要比平常更深入的思考，并在重要数学概念之间建立联系。
问题4.3.3 设 \( \left( {{a}_{1},{a}_{2},{a}_{3},\ldots ,{a}_{12}}\right) \) 为 \( \left( {1,2,3,\ldots ,{12}}\right) \) 的一个排列，满足
\( {a}_{1} > {a}_{2} > {a}_{3} > {a}_{4} > {a}_{5} > {a}_{6} \) 且 \( {a}_{6} < {a}_{7} < {a}_{8} < {a}_{9} < {a}_{10} < {a}_{11} < {a}_{12}. \)
一个这样的排列示例为(6,5,4,3,2,1,7,8,9,10,11,12)。求满足条件的排列总数。
来源:2006 AIME 解答:在本题中，由于 \( {a}_{6} \) 在两个不等式中均为最小值，因此它必须是集合中的最小数，即1。
由此我们注意到，只需从剩余的11个数(2到12)中选出5个数。无论选择哪5个数的组合，总能恰好有一种排列方式使其满足 \( {a}_{1} > {a}_{2} > {a}_{3} > {a}_{4} > {a}_{5} > {a}_{6} \) 。
因此，答案就是 \( \left( \begin{matrix} {11} \\ 5 \end{matrix}\right) \) ，即462。
问题 4.3.4——一个运动粒子从点(4,4)出发，直到首次碰到某条坐标轴为止。当粒子位于点(a, b)时，它以概率 \( \frac{1}{3} \) 随机移动到 \( \left( {a - 1, b}\right) ,\left( {a, b - 1}\right) \) 或(a-1, b-1)之一，且与之前移动无关。粒子在(0,0)处首次碰到坐标轴的概率为 \( \frac{m}{{3}^{n}} \) ，其中 \( m \) 和 \( n \) 为正整数，且 \( m \) 不能被3整除。求 \( m + n \) 。
来源:2019 AIME
解答:共有3种移动方式。
移动到(a-1, b)记为L(向左)
移动到(a, b-1)记为 \( \mathrm{D} \) (向下)
移动到(a-1, b-1)记为 \( \mathrm{C} \) (交叉，即同时向下并向左)
从(4,4)到(0,0)总共需要向下4次、向左4次。然而，我们可以通过(a-1, b-1)的交叉移动来减少选择 \( \mathrm{L} \) 或 \( \mathrm{D} \) 移动的次数。
由于要求首次碰到 \( x \) 或 \( y \) 轴的点必须是(0,0)，因此不能经过(1,0)或(0,1)。这意味着必须从(1,1)通过 \( \mathrm{C} \) 移动到达(0,0)。
现在需要求从(4,4)到(1,1)的概率，再乘以 \( \frac{1}{3} \) ，因为从(1,1)到(0,0)只需一步且概率为 \( \frac{1}{3} \) 。
可通过分类讨论求从(4,4)到(1,1)的概率。例如，可包含3次L和3次D移动，或 \( 2\mathrm{\;L},2\mathrm{D} \) 和 \( 1\mathrm{C} \) 移动。
情况1: \( 3\mathrm{\;L} \) 和 \( 3\mathrm{\;D} \) 移动的概率
此情况即分别向左和向下各3次。如同之前提到的单词重排问题:共6个字母，两种各重复3次(LLLDDD)。
重排方式数为 \( \frac{6!}{3! \cdot 3!} \) 。任意一种移动序列的概率为 \( \frac{1}{3} \) ，共8步，因此总概率为 \( \frac{1}{{3}^{6}} \) 。再乘以重排方式数即可。
\[ \frac{6!}{3! \cdot 3!} \cdot \frac{1}{{3}^{6}} = \frac{20}{{3}^{6}} \]
情况2: \( 2\mathrm{\;L} \) 步、b1步和 \( 1\mathrm{C} \) 步的概率
这再次等同于重新排列5字母单词LLDDC。
排列方式共有 \( \frac{5!}{2! \cdot 2! \cdot 1} \) 种，其中任一种排列的概率为 \( \frac{1}{{3}^{5}} \)
总概率为 \( \frac{30}{{3}^{5}} \) ，即 \( \frac{10}{{3}^{4}} \)
情况3: \( 1\mathrm{\;L} \) 、 \( 1\mathrm{D} \) 步及 \( 2\mathrm{C} \) 步的概率
这相当于对4字母单词LDCC进行重排。
重排方式共有 \( \frac{4!}{2! \cdot 1! \cdot 1!} \) 种，每种重排的概率为 \( \frac{1}{{3}^{4}} \) 。
总概率为 \( \frac{12}{{3}^{4}} \) ，即 \( \frac{4}{{3}^{3}} \)
情况4: \( 0\mathrm{\;L} \) 、 \( 0\mathrm{\;D} \) 步及 \( 3\mathrm{C} \) 步的概率
这相当于对3字母单词CCC进行重排。
重排方式共有 \( \frac{3!}{3! \cdot 0! \cdot 0!} \) 种，即1种；每种重排的概率为 \( \frac{1}{{3}^{3}} \) (因为到达(1,1)需3步)。此情况的总概率为 \( \frac{1}{{3}^{3}} \) 。
这4种情况的概率之和为 \( \frac{20}{{3}^{6}} + \frac{10}{{3}^{4}} + \frac{4}{{3}^{3}} + \frac{1}{{3}^{3}} = \frac{245}{{3}^{6}} \) 。
我们将其乘以 \( \frac{1}{3} \) ，即从(1,1)到(0,0)的概率。我们的概率 \( \frac{1}{3} \cdot \frac{245}{{3}^{6}} \) 为 \( \frac{245}{{3}^{7}} \)
按题目要求格式给出的答案为 \( {245} + 7 \) ，即252。
§4.4 星与条(Stars and Bars)
这是最重要的组合数学主题之一，回报率极高。
一个基础的星与条问题是:将 \( \mathrm{n} \) 个相同物品分给 \( k \) 个人，有多少种分法？
例4.4.1
假设我们有10颗完全相同的糖果，要分给4个孩子，且每个孩子至少得到一颗。我们该如何着手？
解法:我们的相同糖果块就是“星”。星的数量就是糖果的数量。
\( * * * * * * * * * \)
在上面这10颗星中，我们要把它们分给4个人。我们发现只要在任意位置插入3根“棒”，就能把糖果块分成4个独立组(每人一组)。
现在需要找出可以放置棒的位置。我们注意到不能把棒放在两端，否则会产生一个含0颗糖果的组，而每人至少得1颗。因此只能在星与星之间的9个空隙里放棒(最左星左侧和最右星右侧除外)。
从这9个空隙中只需选3个，因此分发糖果的方法数为 \( \left( \begin{array}{l} 9 \\ 3 \end{array}\right) \) ，即84种。
“星与棒”方法现在给出两个公式
定理 4.4.2
方程 \( {x}_{1} + {x}_{2} + \ldots + {x}_{k} = n \) 的正整数解 \( \left( {{x}_{1},{x}_{2},\ldots ,{x}_{k}}\right) \) 的个数为 \( \left( \begin{array}{l} n - 1 \\ k - 1 \end{array}\right) \)
方程 \( {x}_{1} + {x}_{2} + \ldots + {x}_{k} = \) \( n \) 的非负整数解 \( \left( {{x}_{1},{x}_{2},\ldots ,{x}_{k}}\right) \) 的个数为 \( \left( \begin{matrix} n + k - 1 \\ k - 1 \end{matrix}\right) \)
问题 4.4.3 —— 给定8枚可区分的戒指，设 \( n \) 为一只手(不含拇指)的4根手指上佩戴5枚戒指的可能方式数。每根手指上戒指的顺序重要，但不要求每根手指都戴戒指。求 \( n \) 的最左三位非零数字。
来源:2000 AIME
解法:本题有8枚戒指，需从中选5枚戴到4根手指上。首先，从8枚中选5枚，有 \( \left( \begin{array}{l} 8 \\ 5 \end{array}\right) \) 种选法。接着，这5枚戒指有5!种排列方式。
这5枚戒指要分配到4根手指上，可借助“星与棒”模型，假设4根手指上共有 \( {x}_{1},{x}_{2},{x}_{3},{x}_{4} \) 枚戒指
\( {x}_{1} + {x}_{2} + {x}_{3} + {x}_{4} = 5 \)
这是非负整数情形的“星与棒”，因此总数为 \( \left( \begin{matrix} 5 + 4 - 1 \\ 4 - 1 \end{matrix}\right) = \left( \begin{array}{l} 8 \\ 3 \end{array}\right) = {56} \)
将这三个数相乘: \( \left( \begin{array}{l} 8 \\ 5 \end{array}\right) \) 、5!和56，得到376320，前三位数字为376
问题 4.4.4 —— 当投掷7颗公平的6面骰子时，朝上面数字之和为10的概率可写成
\[ \frac{n}{{6}^{7}} \]
其中 \( n \) 为正整数。 \( n \) 是多少？
\( \textbf{(A)}\;{42}\;\textbf{(B)}\;{49}\;\textbf{(C)}\;{56}\;\textbf{(D)}\;{63}\;\textbf{(E)}\;{84} \)
来源:2018 AMC 10
解答:在本题中，假设我们掷出的点数分别为 \( {x}_{1},{x}_{2},{x}_{3},{x}_{4},{x}_{5},{x}_{6} \) 和 \( {x}_{7} \) ，我们知道
\( {x}_{1} + {x}_{2} + {x}_{3} + {x}_{4} + {x}_{5} + {x}_{6} + {x}_{7} = {10} \)
利用上述信息，由于每次掷出的点数当然都是正数(我们无法掷出 \( 0) \) )，根据隔板法(stars and bars)，该方程的解的数量为 \( \left( \begin{matrix} {10} - 1 \\ 7 - 1 \end{matrix}\right) = \left( \begin{array}{l} 9 \\ 6 \end{array}\right) \) ，即84。
接下来，我们检查是否有需要减去的解。这种情况会在某个掷出的点数大于6时出现，因为这不合法。我们注意到，即使有一个点数是7，这种情况也不可能，因为剩下的6个点数至少为1，这样总和就是13，显然大于10。因此，我们无需减去任何情况。
最终答案为84。
问题4.4.5 - 对于某个特定的 \( N \) 值，当 \( {\left( a + b + c + d + 1\right) }^{N} \) 展开并合并同类项后，所得表达式中恰好有1001项包含全部四个变量 \( a, b, c \) 和 \( d \) ，且每个变量的指数均为正整数。求 \( N \) 的值？
(C) 16 (D) 17 (E) 19
来源:2016 AMC 10
解答:在本题中，我们需要知道，对于任何被提升到某次幂的表达式中的项，该项中各个变量部分的指数之和必须等于该表达式的主指数。
乍一听可能有些困惑，因此我将用一个更简单的例子来解释。假设我们有 \( {\left( a + b + c\right) }^{3} \) ，该表达式中任何项的所有变量的指数之和始终为3。我们可以自行验证，因为
\( {\left( a + b + c\right) }^{3} = {a}^{3} + {b}^{3} + {c}^{3} + 3{a}^{2}b + 3{a}^{2} + 3{b}^{2}a + 3{b}^{2}c + 3{c}^{2}a + 3{c}^{2}b + {6abc} \)
在上述展开式中，我们可以看到，对于任何单独的项，如 \( 3{a}^{2} \) 或 \( {6abc} \) ，每个变量的指数之和等于我们将 \( a + b + c \) 提升到的幂次。
利用这些观察，如果本题中a、 \( b, c, d \) 和1的指数分别为 \( {x}_{1},{x}_{2},{x}_{3},{x}_{4},{x}_{5} \) ，那么 \( {x}_{1} + {x}_{2} + {x}_{3} + {x}_{4} + {x}_{5} = N \) 。由于我们希望找到始终包含变量 \( a, b, c, d \) 的项数，这意味着 \( {x}_{1},{x}_{2},{x}_{3},{x}_{4} \) 必须大于或等于1。然而， \( {x}_{5} \) 可以是任何大于或等于0的数。
当出现这种情况时，我们可以做一个巧妙的代换。我们现在可以进行4个代换。
\[ {x}_{1}^{\prime } = {x}_{1} - 1 \]
\[ {x}_{2}^{\prime } = {x}_{2} - 1 \]
\[ {x}_{3}^{\prime } = {x}_{3} - 1 \]
\[ {x}_{4}^{\prime } = {x}_{4} - 1 \]
现在我们可以将其代入原方程 \( {x}_{1} + {x}_{2} + {x}_{3} + {x}_{4} + {x}_{5} = N \) ，使其变为 \( {x}_{1}^{\prime } + {x}_{2}^{\prime } + {x}_{3}^{\prime } + {x}_{4}^{\prime } + {x}_{5} = N - 4 \)
对于新方程，所有5个变量现在都可以大于或等于0。
该方程的解的数量为 \( \left( \begin{matrix} N - 4 + 5 - 1 \\ 5 - 1 \end{matrix}\right) = \left( \begin{matrix} N \\ 4 \end{matrix}\right) \)
由于 \( \left( \begin{array}{l} N \\ 4 \end{array}\right) \) 为1001，从答案选项 \( \mathrm{N} \) 中代入几个数字后得到14(B)。
问题 4.4.6 - 有多少组正整数 (a, b, c) 满足 \( a \downarrow b \downarrow c \downarrow 0 \) 和 \( a + b + c = {103} \) ？
来源:2014年普林斯顿大学数学竞赛(PUMAC)
解:在本题中，已知这三个数均为正数，因此在忽略 \( a \downarrow b \downarrow c \downarrow 0 \) 条件后，由“星与条”(stars and bars)方法得到的解数即为 \( \left( \begin{matrix} {102} \\ 2 \end{matrix}\right) \) ，也就是5151。
然而，现在我们需要减去重复计算的情况。我们注意到，只要三个加起来等于102的数互不相同(DISTINCT)，就恰好有一种排列方式满足 \( a > b > c > 0 \) 。然而，由于在用“星与条”方法计数时我们忽略了所有限制条件，因此需要减去出现重复数字的情况(因为103不能被3整除，所以不可能三个数都相同)。
假设重复的数字是 \( x \) ，另一个数字是 \( y \) ，我们想求出满足 \( {2x} + y = {103} \) 的情况数
由于 \( x \) 可以是1到51之间的任意数，且对于这些数中的每一个， \( y \) 也大于或等于1，这意味着共有51种情况。然而，我们必须乘以3，以考虑 \( x, x, y \) 的重新排列。
总共需要减去153。
\( {5151} - {153} = {4998} \)
从这里开始，我们只剩下和为103且互不相同的数字 \( a, b, c \) 。然而，由于重复计数，我们必须除以6。这是因为像1、2、100这样的数字可以重新排列6次，尽管根据我们的限制 \( a > b > c > 0 \) ，它只对应1个解。
因此，最终答案是 \( \frac{4998}{6} \) ，即833。
问题 4.4.7 - 一位园丁将三棵枫树、四棵橡树和五棵桦树排成一行。他随机种植，每种排列方式等可能。设 \( \frac{m}{n} \) 为最简分数表示的“任意两棵桦树都不相邻”的概率。求 \( m + n \) 。
来源:1984年AIME解答:在本题中，我们可以将非桦树视为相同。此时，我们有7棵非桦树和5棵桦树。我们可以把非桦树看作“星”，把桦树看作“条”。
如果我们先摆放非桦树，只需画出7个星号
\( * * * * * * * \)
现在，在每颗星星之间以及左右两侧共有8个空位。我们要从中选出5个空位来种植桦树(birch trees)。这样我们就得到了 \( \left( \begin{array}{l} 8 \\ 5 \end{array}\right) \) 种排列方式，使得任意两棵桦树都不相邻。
分母中的总组合数就是 \( \left( \begin{matrix} {12} \\ 5 \end{matrix}\right) \) ，它表示从12个位置中随机选取5个来种植桦树(birch trees)，其余位置则种植非桦树。
我们的答案是 \( \left( \begin{array}{l} 8 \\ 5 \end{array}\right) \) 除以 \( \left( \begin{matrix} {12} \\ 5 \end{matrix}\right) = \frac{7}{99} \) 。最终答案是106。
问题 4.4.8 - Connie 发现一块白板，上面用磁性字母拼出 MISSISSIPPI。她可以重新排列这些字母，其中相同的字母不可区分。如果她使用全部字母且不希望任何 I 相邻，有多少种不同的排列方式？
来源:2019 SMT
解答:在本题中，由于我们要把 I 分开且不让它们相邻，不妨把 4 个 I 视为“分隔符”。可以写成 HIII。这样就为其他字母创造了 5 个可插入的位置(每对 I 之间以及最左和最右)。
接下来，我们可以使用“星与棒”方法，并假设每个位置有 \( a, b, c, d, e \) 个字母。
aIbIcIdIe(其中 \( a, b, c, d, e \) 表示字母的数量，而 I 是实际的字母)
由此可知 \( a + b + c + d + e = 7 \) ，因为共有 7 个非 I 字母(有 \( 1\mathrm{M},4\mathrm{\;S} \) 和 \( 2\mathrm{P} \) 个)。
\( b, c, d \) 至少为 1。我们现在可以使用之前见过的技巧。
\( {b}^{\prime } = b - 1 \)
\( {c}^{\prime } = c - 1 \)
\[ {d}^{\prime } = d - 1 \]
将其代入我们之前见过的涉及 \( a, b, c, d, e \) 的方程，方程变为 \( a + {b}^{\prime } + {c}^{\prime } + {d}^{\prime } + e = 4 \) 。由此可知 \( n \) 为 4， \( k \) 为 5。由于之前的替换，这些数必须非负，因为 \( b, c, d \) 至少为 1，否则 I 会相邻。
将其代入 \( \left( \begin{matrix} n + k - 1 \\ k - 1 \end{matrix}\right) \) 得到 \( \left( \begin{array}{l} 8 \\ 4 \end{array}\right) \) ，即 70。
除去 I 后剩下的字母是 MSSSSPP。共有 7 个字母，因此有 7! 种排列方式。需要除以 4! 和 2!，因为 S 重复 4 次， \( \mathrm{P} \) 重复 2 次。
最终答案为 \( {70} \cdot \frac{7!}{4!2!} \) ，即 7350。
§4.5 二项式
你需要了解二项式定理才能推导出这些系数。
我们知道 \( {\left( x + y\right) }^{2} \) 就是 \( {x}^{2} + {2xy} + {y}^{2} \) 。我相信要得到答案，你会把每一项相乘。这种方法很好，但如果你想计算 \( {\left( x + y\right) }^{6} \) ，手算就很痛苦了。这时就需要二项式定理。
定理 4.5.1
二项式定理 \( {\left( x + y\right) }^{n} = {x}^{n} + \left( \begin{array}{l} n \\ 1 \end{array}\right) {x}^{n - 1}y + \left( \begin{array}{l} n \\ 2 \end{array}\right) {x}^{n - 2}{y}^{2} + \ldots + \left( \begin{matrix} n \\ n - 1 \end{matrix}\right) x{y}^{n - 1} + \) \( {y}^{n} \)
重要的是要注意每一项的系数如何按某种规律变化。
定理4.5.2
\[ \left( \begin{array}{l} n \\ 0 \end{array}\right) + \left( \begin{array}{l} n \\ 1 \end{array}\right) + \left( \begin{array}{l} n \\ 2 \end{array}\right) + \left( \begin{array}{l} n \\ 3 \end{array}\right) + \ldots + \left( \begin{matrix} n \\ n - 2 \end{matrix}\right) + \left( \begin{matrix} n \\ n - 1 \end{matrix}\right) + \left( \begin{array}{l} n \\ n \end{array}\right) = {2}^{n} \]
你有时可以在代数问题中使用上面展示的组合恒等式。例如，我们已经知道，如果有一个多项式 \( f\left( x\right) \) ，并且我们想求它的系数之和，只需代入1即可得到 \( f\left( 1\right) \) 。
有时你会将这一思路与本定理中展示的组合恒等式结合，以求出系数之和。
定理4.5.3
帕斯卡恒等式(Pascal's Identity)
\( \left( \begin{array}{l} n \\ k \end{array}\right) + \left( \begin{matrix} n \\ k + 1 \end{matrix}\right) = \left( \begin{array}{l} n + 1 \\ k + 1 \end{array}\right) \)
上述定理对正整数 \( n \) 成立，且当 \( 0 \leq k \leq n - 1 \) 时。
定理4.5.4
曲棍球棒恒等式(Hockey Stick Identity)
\( \mathop{\sum }\limits_{{i = k}}^{n}\left( \begin{array}{l} i \\ k \end{array}\right) = \left( \begin{array}{l} k \\ k \end{array}\right) + \left( \begin{matrix} k + 1 \\ k \end{matrix}\right) + \left( \begin{matrix} k + 2 \\ k \end{matrix}\right) + \ldots + \left( \begin{array}{l} n \\ k \end{array}\right) = \left( \begin{array}{l} n + 1 \\ k + 1 \end{array}\right) \)
只要 \( 0 \leq k \leq n \) ，上述定理就成立。
定理4.5.5
范德蒙德恒等式(Vandermonde's Identity)
这个恒等式相对少见，但仍值得了解，以防万一出现。
\[ \mathop{\sum }\limits_{{k = 0}}^{r}\left( \begin{matrix} m \\ k \end{matrix}\right) \left( \begin{matrix} n \\ r - k \end{matrix}\right) = \left( \begin{matrix} m + n \\ r \end{matrix}\right) \]
问题4.5.6 - 已知 \( \frac{1}{2!{17}!} + \frac{1}{3!{16}!} + \frac{1}{4!{15}!} + \frac{1}{5!{14}!} + \frac{1}{6!{13}!} + \frac{1}{7!{12}!} + \frac{1}{8!{11}!} + \frac{1}{9!{10}!} = \frac{N}{1!{18}!} \) ，求小于 \( \frac{N}{100} \) 的最大整数。
来源:2000年AIME
解法:在本题中，我们注意到方程左侧的分母有两个阶乘，且去掉阶乘符号后的数字之和为19。因此，为了尝试一些变形，我们将两边同时乘以19!。这样做得到
\[ \frac{{19}!}{2!{17}!} + \frac{{19}!}{3!{16}!} + \frac{{19}!}{4!{15}!} + \frac{{19}!}{5!{14}!} + \frac{{19}!}{6!{13}!} + \frac{{19}!}{7!{12}!} + \frac{{19}!}{8!{11}!} + \frac{{19}!}{9!{10}!} = \frac{{19}!N}{1!{18}!} \]
我们认识到诸如 \( \frac{{19}!}{2!{17}!} \) 这样的项仅仅是 \( \left( \begin{matrix} {19} \\ 2 \end{matrix}\right) \) 。利用这一点，我们重写剩余项，得到
\[ \left( \begin{matrix} {19} \\ 2 \end{matrix}\right) + \left( \begin{matrix} {19} \\ 3 \end{matrix}\right) + \left( \begin{matrix} {19} \\ 4 \end{matrix}\right) + \left( \begin{matrix} {19} \\ 5 \end{matrix}\right) + \left( \begin{matrix} {19} \\ 6 \end{matrix}\right) + \left( \begin{matrix} {19} \\ 7 \end{matrix}\right) + \left( \begin{matrix} {19} \\ 8 \end{matrix}\right) + \left( \begin{matrix} {19} \\ 9 \end{matrix}\right) = N \cdot \left( \begin{matrix} {19} \\ 1 \end{matrix}\right) \]
由恒等式 \( \left( \begin{array}{l} n \\ 0 \end{array}\right) + \left( \begin{array}{l} n \\ 1 \end{array}\right) + \left( \begin{array}{l} n \\ 2 \end{array}\right) + \left( \begin{array}{l} n \\ 3 \end{array}\right) + \ldots + \left( \begin{matrix} n \\ n - 2 \end{matrix}\right) + \left( \begin{matrix} n \\ n - 1 \end{matrix}\right) + \left( \begin{array}{l} n \\ n \end{array}\right) = {2}^{n} \) 可知 \( \left( \begin{matrix} {19} \\ 0 \end{matrix}\right) + \left( \begin{matrix} {19} \\ 1 \end{matrix}\right) + \left( \begin{matrix} {19} \\ 2 \end{matrix}\right) + \left( \begin{matrix} {19} \\ 3 \end{matrix}\right) + \ldots + \left( \begin{matrix} {19} \\ {17} \end{matrix}\right) + \left( \begin{matrix} {19} \\ {18} \end{matrix}\right) + \left( \begin{matrix} {19} \\ {19} \end{matrix}\right) = {2}^{19} \)
我们知道所有项都是对称的(即首项等于末项)，因此可将等式两边同除以2，得到
\[ \left( \begin{matrix} {19} \\ 0 \end{matrix}\right) + \left( \begin{matrix} {19} \\ 1 \end{matrix}\right) + \left( \begin{matrix} {19} \\ 2 \end{matrix}\right) + \left( \begin{matrix} {19} \\ 3 \end{matrix}\right) + \ldots + \left( \begin{matrix} {19} \\ 7 \end{matrix}\right) + \left( \begin{matrix} {19} \\ 8 \end{matrix}\right) + \left( \begin{matrix} {19} \\ 9 \end{matrix}\right) = {2}^{18} \]
我们将前两项相减，其和为20，得到 \( {2}^{18} - {20} \)
现在我们可以将方程重写为
\[ {2}^{18} - {20} = \mathrm{N} \cdot \left( \begin{matrix} {19} \\ 1 \end{matrix}\right) \]
化简后得到 \( \frac{262124}{19} \) ，其中 \( \mathrm{N} \) ，并以我们期望的形式写出答案137。
问题4.5.7——表达式
\( {\left( x + y + z\right) }^{2006} + {\left( x - y - z\right) }^{2006} \)
通过展开并合并同类项进行化简。化简后的表达式中有多少项？
化简后的表达式中有多少项？
(A)6018(B)671,676(C)1,007,514(D)1,008,016(E)2,015,028
来源:2006年AMC 12
解法:本题首先需使用星与棒(stars and bars)方法。我们已知，对于任意代数表达式，其项数可通过星与棒求得，因为每一项的次数之和等于原表达式被提升到的幂次。
假设 \( {x}_{1},{x}_{2} \) 和 \( {x}_{3} \) 分别为 \( x, y, z \) 的系数，则 \( {x}_{1} + {x}_{2} + {x}_{3} = \) 2006。这三个数均为非负整数。
应用星与棒方法得到 \( \left( \begin{matrix} {2006} + 3 - 1 \\ 3 - 1 \end{matrix}\right) = \left( \begin{matrix} {2008} \\ 2 \end{matrix}\right) = {2015028} \)
然而，我们现在必须减去若干情况，因为当我们减去两个代数项 \( {\left( x + y + z\right) }^{2006} \) 和 \( {\left( x - y - z\right) }^{2006} \) 时，某些项会相互抵消。
只有当右侧项的系数为负时，该项才会被抵消(来自 \( {\left( x + y + z\right) }^{2006} \) 的项系数始终为正)。
假设 \( {y}_{1},{y}_{2} \) 和 \( {y}_{3} \) 是构成 \( x, - y, - z \) 的项的指数，那么我们知道 \( {y}_{1} + {y}_{2} + {y}_{3} = {2006} \)
然而，要使这一项在此部分为负， \( {y}_{2} + {y}_{3} \) 必须是奇数，因为任何负数取奇次幂后仍为负数。
这意味着，如果 \( {y}_{2} + {y}_{3} \) 的总和为奇数， \( {y}_{1} \) 也必须是奇数。
| \( {y}_{1} \) | 病例数 |
| 1 | |
| 3 | |
| 5 | |
| 7 | |
| 9 | |
| 11 ... | ... |
| 2005 | \( \left( \begin{array}{l} 2 \\ 1 \end{array}\right) \) |
我们只需把各列右侧的数值(即情况数)相加即可。这个和就是从2到1006的所有奇数之和，等于1007012(利用前 \( \mathrm{n} \) 个偶数之和公式)。
用2015028减去1007012得到1008016(D)
问题4.5.8 — 求所有满足 \( 5{x}^{4} - {10}{x}^{3} + {10}{x}^{2} - \) \( {5x} - {11} = 0 \) 的实数 \( \mathrm{x} \) 之和
来源:2014年HMMT
解答:本题中，看到系数5、10、10、5应联想到帕斯卡数(Pascal numbers)，如 \( \left( \begin{array}{l} 5 \\ 1 \end{array}\right) \) 和 \( \left( \begin{array}{l} 5 \\ 2 \end{array}\right) \) 。
我们尝试将 \( {\left( x - 1\right) }^{5} \) 引入问题，因为该多项式的系数与题目一致。
可将原多项式改写为
\[ {x}^{5} - {x}^{5} + 5{x}^{4} - {10}{x}^{3} + {10}{x}^{2} - {5x} - 1 + {12} = 0 \]
\[ {x}^{5} + 5{x}^{4} - {10}{x}^{3} + {10}{x}^{2} - {5x} - 1 - {x}^{5} + {12} = 0 \]
前5项恰好是 \( {\left( x - 1\right) }^{5} \)
\[ {\left( x - 1\right) }^{5} - {x}^{5} + {12} = 0 \]
上述多项式中，若 \( r \) 是根，则 \( 1 - r \) 也必为根，因为 \( x \) 与 \( x - 1 \) 具有对称性。进一步观察可知本题仅有2个实根。已知若 \( r \) 是根，则 \( 1 - r \) 必为另一根。因此只需确定 \( r \) 的值。但题目要求的是根之和，我们只需将 \( 1 - r \) 与 \( r \) 相加，由于 \( r \) 项抵消，最终答案为1。
问题4.5.9 - 某俱乐部有11名男性和12名女性成员，需从中选出委员会，要求女性人数比男性多1人。委员会规模可从1人到23人不等。设 \( N \) 为可组成的委员会总数，求 \( N \) 的所有素因数之和。来源:2020年AIME
解答:由于女性必须比男性多1人，可按情况列举:1名女性对应0名男性，2名女性对应1名男性，3名女性对应2名男性……
选择 \( k \) 名女性的方式数为 \( \left( \begin{matrix} {12} \\ k \end{matrix}\right) \) ，选择 \( k - 1 \) 名男性(比女性少1人)的方式数为 \( \left( \begin{matrix} {11} \\ k - 1 \end{matrix}\right) \) 。需将这两个数相乘，其中 \( k.\mathrm{k} \) 的取值范围显然为1(仅1名女性时)至12(选择全部女性时)。
可将其表示为求和形式
\( \mathop{\sum }\limits_{{k = 1}}^{{12}}\left( \begin{matrix} {11} \\ k - 1 \end{matrix}\right) \left( \begin{matrix} {12} \\ k \end{matrix}\right) \)
展开各项如下(我将全部列出，但无需刻意观察后续规律):
\( {(\frac{11}{0})} \cdot {(\frac{12}{1})} + {(\frac{11}{1})} \cdot {(\frac{12}{2})} + {(\frac{11}{2})} \cdot {(\frac{12}{3})} + {(\frac{11}{3})} \cdot {(\frac{12}{4})} + {(\frac{11}{4})} \cdot {(\frac{12}{5})} + {(\frac{11}{5})} \cdot {(\frac{12}{6})} + {(\frac{11}{6})} \cdot {(\frac{12}{7})} \)
\( + \left( \begin{matrix} {11} \\ 7 \end{matrix}\right) \cdot \left( \begin{matrix} {12} \\ 8 \end{matrix}\right) + \left( \begin{matrix} {11} \\ 8 \end{matrix}\right) \cdot \left( \begin{matrix} {12} \\ 9 \end{matrix}\right) + \left( \begin{matrix} {11} \\ 9 \end{matrix}\right) \cdot \left( \begin{matrix} {12} \\ {10} \end{matrix}\right) + \left( \begin{matrix} {11} \\ {10} \end{matrix}\right) \cdot \left( \begin{matrix} {12} \\ {11} \end{matrix}\right) + \left( \begin{matrix} {11} \\ {11} \end{matrix}\right) \cdot \left( \begin{matrix} {12} \\ {12} \end{matrix}\right) \)
可识别此为范德蒙德恒等式(Vandermonde's identity)，其表述为 \( \mathop{\sum }\limits_{{k = 0}}^{r}\left( \begin{matrix} m \\ k \end{matrix}\right) \left( \begin{matrix} n \\ r - k \end{matrix}\right) = \left( \begin{matrix} m + n \\ r \end{matrix}\right) \)
在将若干项如 \( \left( \begin{array}{l} n \\ k \end{array}\right) \) 转换为 \( \left( \begin{matrix} n \\ n - k \end{matrix}\right) \) 后应用范德蒙德恒等式(Vandermonde’s identity)可得 \( \left( \begin{array}{l} {23} \\ {12} \end{array}\right) \) ，并按题目要求的形式写出答案，得到81。
问题4.5.10——设 \( \mathrm{S} \) 为集合 \( 1,2,3,\ldots ,{2018} \) 的所有1000元子集构成的集合。若从中均匀随机选取一个集合，其最小元素的期望值是多少？
来源:2018 SMT
解:假设最小值为1，则此时子集数量为 \( \left( \begin{matrix} {2017} \\ {999} \end{matrix}\right) \) 。
若最小值为2，则有 \( \left( \begin{matrix} {2016} \\ {999} \end{matrix}\right) \) 个子集；依此类推，直到最小值为1019，此时有 \( \left( \begin{array}{l} {999} \\ {999} \end{array}\right) \) 个子集。
由于期望值等于每种可能情况的发生方式数乘以该情况的取值，再除以总发生方式数。
分母即为 \( \left( \begin{matrix} {2018} \\ {1000} \end{matrix}\right) \) ，因为我们只需从2018个数中选出1000个数作为子集。
分子为 \( 1 \cdot \left( \begin{matrix} {2017} \\ {999} \end{matrix}\right) + 2 \cdot \left( \begin{matrix} {2016} \\ {999} \end{matrix}\right) \ldots + {1019} \cdot \left( \begin{matrix} {999} \\ {999} \end{matrix}\right) \) 。
可将该分子写成
\[ \left( \begin{matrix} {2017} \\ {999} \end{matrix}\right) + \left( \begin{matrix} {2016} \\ {999} \end{matrix}\right) + \ldots + \left( \begin{matrix} {999} \\ {999} \end{matrix}\right) = \left( \begin{matrix} {2018} \\ {1000} \end{matrix}\right) \]
\[ \left( \begin{matrix} {2016} \\ {999} \end{matrix}\right) + \left( \begin{matrix} {2015} \\ {999} \end{matrix}\right) + \ldots + \left( \begin{matrix} {999} \\ {999} \end{matrix}\right) = \left( \begin{matrix} {2017} \\ {1000} \end{matrix}\right) \]
\[ \left( \begin{matrix} {2015} \\ {999} \end{matrix}\right) + \left( \begin{matrix} {2014} \\ {999} \end{matrix}\right) + \ldots + \left( \begin{matrix} {999} \\ {999} \end{matrix}\right) = \left( \begin{matrix} {2016} \\ {1000} \end{matrix}\right) \]
\[ \left( \begin{matrix} {1000} \\ {999} \end{matrix}\right) + \left( \begin{matrix} {999} \\ {999} \end{matrix}\right) = \left( \begin{matrix} {1001} \\ {1000} \end{matrix}\right) \]
\[ \left( \begin{array}{l} {999} \\ {999} \end{array}\right) = \left( \begin{array}{l} {1000} \\ {1000} \end{array}\right) \]
我们将范德蒙德恒等式 \( \left( {\mathop{\sum }\limits_{{i = k}}^{n}\left( \begin{array}{l} i \\ k \end{array}\right) = \left( \begin{array}{l} k \\ k \end{array}\right) + \left( \begin{matrix} k + 1 \\ k \end{matrix}\right) + \left( \begin{matrix} k + 2 \\ k \end{matrix}\right) + \ldots + \left( \begin{array}{l} n \\ k \end{array}\right) = }\right. \) \( \left. \left( \begin{array}{l} n + 1 \\ k + 1 \end{array}\right) \right) \) 应用于这些单独求和，得到
\[ \left( \begin{array}{l} {2018} \\ {1000} \end{array}\right) + \left( \begin{array}{l} {2017} \\ {1000} \end{array}\right) + \left( \begin{array}{l} {2016} \\ {1000} \end{array}\right) + \ldots + \left( \begin{array}{l} {1001} \\ {1000} \end{array}\right) + \left( \begin{array}{l} {1000} \\ {1000} \end{array}\right) \]
再次对该求和式应用范德蒙德恒等式，此时 \( k \) 为1000， \( n \) 为2018，得到 \( \left( \begin{array}{l} {2019} \\ {1001} \end{array}\right) \) 。
这是所有可能值的总和，但还需除以子集总数 \( \left( \begin{array}{l} {2018} \\ {1000} \end{array}\right) \) 。
于是得到
\( \frac{{2019}!}{{1001}!{1018}!} \cdot \frac{{1000}!{1018}!}{{2018}!} \) ，结果为 \( \frac{2019}{1001} \)
§4.6 递归
递归是AMC乃至AIME中的关键主题。对于资深程序员而言，这一主题与动态规划或他们见过的诸多算法颇为相似。
递归(Recursion)将一个更难的问题化简为一个更小的问题，并通过建立关系将其与更大的数联系起来。
斐波那契数列(Fibonacci sequence)是递推关系(recurrence relation)的经典示例，其中当前项由前两项相加得到。
在斐波那契数列中， \( {F}_{n} \) 表示第 n 项，且在该数列中 \( {F}_{0} = 0 \) 和 \( {F}_{1} = 1 \) 。递推关系为 \( {F}_{n} = {F}_{n} - 1 + {F}_{n} - 2 \) 。
例 4.6.1
鲍勃想爬 8 级台阶。他每次可以爬 1 级或 2 级。他有多少种不同的方法爬完这 8 级台阶？
解法:在本题中，一种可行的路径是连续四次每次爬 2 级。或者，他也可以按 1、2、2、2、1 的顺序爬。
然而，用这种方式逐一计数会非常耗时。这时就轮到递归登场了。
设 \( {a}_{n} \) 表示爬 \( \mathrm{n} \) 级台阶的方法数。我们尝试将其与前面的项(如 \( {a}_{n - 1},{a}_{n - 2},{a}_{n - 3} \) 等)建立联系。
我们注意到，如果鲍勃在到达 \( {a}_{n} \) 之前一步位于 \( {a}_{n} - 1 \) 或 \( {a}_{n} - 2 \) ，那么他总能到达 \( {a}_{n} \) 。
因此，这意味着 \( {a}_{n} = {a}_{n - 1} + {a}_{n} - 2 \) 。现在我们需要先求出前几项，才能利用上述关系求出其余项。显然 \( {a}_{1} \) 为 1，因为爬 1 级台阶只有 1 种方法。同理， \( {a}_{2} \) 为 2，因为爬 2 级台阶有 2 种方法(要么一次跨 2 级，要么两次各跨 1 级)。
\[ {a}_{1} = 1 \]
\[ {a}_{2} = 2 \]
\[ {a}_{3} = {a}_{2} + {a}_{1} = 3 \]
\[ {a}_{4} = {a}_{3} + {a}_{2} = 5 \]
\[ {a}_{5} = {a}_{4} + {a}_{3} = 8 \]
\[ {a}_{6} = {a}_{5} + {a}_{4} = {13} \]
\[ {a}_{7} = {a}_{6} + {a}_{5} = {21} \]
\[ {a}_{8} = {a}_{7} + {a}_{6} = {34} \]
既然我们求得 \( {a}_{8} \) 为 34，那么最终答案就是 34。
问题 4.6.2——每天上学时，乔要爬一段 6 级台阶。乔每次可以跨 1、2 或 3 级。例如，乔可以先跨 3 级，再跨 1 级，再跨 2 级。乔有多少种不同的爬法？
\( \textbf{(A)}{13}\;\textbf{(B)}{18}\;\textbf{(C)}{20}\;\textbf{(D)}{22}\;\textbf{(E)}{24} \)
来源:2010 AMC 8 第 25 题
解法:本题有许多更简单的解法，但我们将使用递归。
\( {a}_{n} \) 表示乔爬 n 级台阶的方法数。
显然 \( {a}_{1} \) 为 1。
\( {a}_{2} \) 为 2，因为他可以一次跨 1 级台阶两次，也可以一次跨 2 级台阶。
同理， \( {a}_{3} \) 为 \( 4\left( 3\right) ,\left( {1,2}\right) ,\left( {2,1}\right) ,\left( {1,1,1}\right) \)
我们注意到这与之前讨论的例子类似，可以再次将其与更小的项如 \( {a}_{n - 1} \) 联系起来。
只要 Joe 到达第 n 级台阶之前的位置是 \( n - 1, n - 2 \) 或 \( n - 3 \) ，他就总有办法到达第 n 级。
这意味着 \( {a}_{n} = {a}_{n - 1} + {a}_{n - 2} + {a}_{n - 3} \)
现在我们可以用前面的项来求出其余项。我们直接算出 \( {a}_{6} \) 为 24。
问题 4.6.3——若一个整数集合中任意三个连续整数至多出现一个，则称该集合为“稀疏(spacy)”。 \( \{ 1,2,3,\ldots ,{12}\} \) 有多少个子集(含空集)是稀疏的？
(A) 121 (B) 123 (C) 125 (D) 127 (E) 129
来源:(2007 AMC 12)
解法:本题我们再次尝试使用递推。
\( {a}_{n} \) 表示在 1 到 \( n \) 的范围内满足稀疏条件的子集数量。
我们先求前几项。 \( {a}_{1} \) 显然为 2，因为子集可以包含 1 或为空。
同理， \( {a}_{2} \) 为 3，因为子集可以包含 1、2 或为空。
同理，对于 \( {a}_{3} \) ，子集可以包含 1、2、3 或为空，因此 \( {a}_{3} \) 为 4。
现在为 \( {a}_{n} \) 寻找关系，我们分两种情况:一是统计包含 \( n \) 的子集数量，二是统计不包含 \( n \) 的子集数量。
情况 1:子集包含 \( n \)
在这种情况下，数字 \( n - 1 \) 和 \( n - 2 \) 不能作为子集的候选。然而，任何在 \( n - 3 \) 之前且包含该数字的数都可以。因此，这里的可能情况数为 \( {a}_{3} \)
情况2:我们的子集不包含 \( n \)
在这种情况下， \( n - 1 \) 是子集中可能的最大元素。因此，这里的总数就是 \( {a}_{n - 1} \) ，表示从1到 \( n - 1 \) 可以构成的子集数量。
这告诉我们 \( {a}_{n} = {a}_{n - 1} + {a}_{n - 3} \)
现在使用我们在开始时为 \( {a}_{1},{a}_{2},{a}_{3} \) 找到的项，我们可以找到剩余的项，并发现 \( {a}_{12} \) 为129。
问题4.6.4 - 有多少个长度为19的0和1序列，以0开头，以0结尾，不包含两个连续的0，且不包含三个连续的1？
(E) 75
来源:2019 AMC 10
在这个问题中，我们假设 \( {a}_{n} \) 表示长度为 \( n \) 且以0开头和结尾的序列数量。我们知道在0之后不能有另一个0，因为这违反了不包含连续0的条件。因此，其后必须出现1。
一些观察表明，我们可以在0后添加10或110。由于这些字符串长度为2和3，这意味着
\( {a}_{n} = {a}_{n - 2} + {a}_{n - 3} \) (如果你仍对此步骤感到困惑，请返回复习本节)
我们知道 \( {a}_{3} \) 必须为1，因为唯一可能的序列是010
\( {a}_{4} \) 必须为1，因为唯一可能的序列是0110
\( {a}_{5} \) 必须为1，因为唯一可能的序列是01010
使用这3个项，我们可以计算其余项，并发现 \( {a}_{19} \) 为 \( \mathbf{{65}}\left( \mathbf{C}\right) \) 。
问题4.6.5 - 通过 \( {t}_{1} = {20},{t}_{2} = {21} \) 递归定义一个序列，且
\[ {t}_{n} = \frac{5{t}_{n - 1} + 1}{{25}{t}_{n - 2}} \]
对于所有 \( n \geq 3 \) 。那么 \( {t}_{2020} \) 可以表示为 \( \frac{p}{q} \) ，其中 \( p \) 和 \( q \) 是互质的正整数。求 \( p + q \) 。
来源:2020 AIME
解法:在本题中，尽管给出了一个递推公式，但有时你可以通过观察各项的重复规律来找到答案。各项会开始循环，从而简化问题。
在这种情况下，我们将尝试找出其中的一些数字，并观察其周期。
\[ {t}_{1} = {20} \]
\[ {t}_{2} = {21} \]
\[ {t}_{3} = \frac{5{t}_{2} + 1}{{25}{t}_{1}} = \frac{53}{250} \]
\[ \begin{array}{l} {t}_{4} = \frac{5{t}_{3} + 1}{{25}{t}_{2}} = \frac{103}{26250} \end{array} \]
\[ \begin{array}{l} {t}_{5} = \frac{5{t}_{4} + 1}{{25}{t}_{3}} = \frac{101}{525} \end{array} \]
\[ {t}_{6} = \frac{5{t}_{5} + 1}{{25}{t}_{4}} = {20} \]
\[ {t}_{7} = \frac{5{t}_{6} + 1}{{25}{t}_{5}} = {21} \]
由此我们注意到，位于 \( {t}_{1} \) 的项在 \( {t}_{6} \) 处重复出现。这意味着周期为5。显然 \( {t}_{1} = {t}_{6} = {t}_{1}1\ldots = {t}_{2}{016} \) 。
从那里开始，我们只需从 \( {t}_{1} \) 往上数4个数，因为这等同于 \( {t}_{2}{016} \) ，而往上数4就得到 \( {t}_{5} \) ，这就是答案。我们将分子与分母相加得到626。
§4.7 条件概率(Conditional Probability)
条件概率是一个重要主题，在AMC和AIME中频繁出现。它研究的是在已知某一条件成立的前提下，某事件发生的概率。
示例4.7.1
已知骰子掷出的点数为偶数，求该点数为2的概率。
解法:从某种程度上说，本题所求为P(偶数且为2)/P(偶数)
给定条件是该数为偶数，而可能的偶数有3个，即2、4、6。因此，我们的概率就是 \( \frac{1}{3} \)
定理 4.7.2
贝叶斯定理(Bayes Theorem)的数学表示 \( P\left( {A \mid B}\right) = \frac{P\left( {A \cap B}\right) }{P\left( B\right) } \)
上述陈述试图表达的是:在事件 \( \mathrm{B} \) 已经发生的条件下，事件A发生的概率为 \( \mathrm{P}\left( {\mathrm{A}\text{and}\mathrm{B}}\right) /\mathrm{P}\left( \mathrm{B}\right) \)
如果 \( \mathrm{A} \) 和 \( \mathrm{B} \) 是独立事件，那么 \( P\left( {A \mid B}\right) = P\left( A\right) \) 。
我们可以确认上述命题的有效性，因为如果A与B相互独立，那么B是否发生都不会影响A发生的概率。
问题4.7.3 设 \( S \) 为序列1,2,3,4,5的所有排列中首项不为1的排列集合。现从 \( S \) 中随机选取一个排列。第二项为2的概率(最简分数形式)为 \( a/b \) 。求 \( a + b \) ？
来源:2003 AMC 12
解答:本题已知首项不为1，条件是第二项为2。可在此处使用 \( P\left( {A \mid B}\right) = \frac{P\left( {A \cap B}\right) }{P\left( B\right) } \) 命题，并用我们的术语改写。
\( \mathrm{P} \) (第二项为2)在首项不为1的条件下
P(第二项为2且首项不为1)/P(首项不为1)
第二项为2且首项不为1的情况数就是 \( 3 \cdot 3! \) ，因为我们有3个位置可放1
同理，首项不为1的情况数为 \( 4 \cdot 4! \) ，因为1有4个可放位置(除首项外)，其余4!种排列
答案即为 \( \frac{3 \cdot 3!}{4 \cdot 4!} = \frac{3}{16} \) ，最终答案为 \( 3 + {16} \) ，即 \( {19}\left( \mathbf{E}\right) \)
问题4.7.4 一只虫子从等边三角形的一个顶点出发。每一步，它随机选择当前所在顶点之外的另两个顶点之一，并沿边爬向该顶点。已知第十步时虫子回到起点的概率为 \( m/n \) ，其中 \( m \) 与 \( n \) 为互质正整数，求 \( m + n \) 。
来源:2003 AIME
解答:本题已知条件为共走10步，要求回到起点。
先计算分母中10步的总路径数。每步有2种选择，故共有 \( {2}^{10} \) 种走法。
设CW表示顺时针移动，CCW表示逆时针移动。令 \( \mathrm{X} \) 为 \( \mathrm{{CW}} \) 步数， \( \mathrm{Y} \) 为CCW步数。
已知 \( \mathrm{X} + \mathrm{Y} = {10} \)
且 \( \mathrm{X} - \mathrm{Y} \equiv 0\left( {\;\operatorname{mod}\;3}\right) \) ，因所有移动后需回到起点。
\[ \mathrm{X} \equiv \mathrm{Y}\left( {\;\operatorname{mod}\;3}\right) \]
假设 \( \mathrm{X} \) 与 \( \mathrm{Y} \) 均为0 mod 3，其和为0 mod 3，但两数之和为10≡1 mod 3。同理，二者不能同为1 mod 3，必为2 mod 3。
因 \( \mathrm{X} \) 与 \( \mathrm{Y} \) 均为2 mod 3且和为10，可能的(X, Y)为 \( \left( {2,8}\right) ,\left( {5,5}\right) \) 及(8,2)。计算每种情况的排列数，即10个字母(如XXYYYYYYYY)的排列，得
\[ \left( \begin{matrix} {10} \\ 2 \end{matrix}\right) + \left( \begin{matrix} {10} \\ 5 \end{matrix}\right) + \left( \begin{matrix} {10} \\ 8 \end{matrix}\right) = {342} \]
我们的总概率是 \( \frac{342}{{2}^{10}} = \frac{171}{512} \) 。我们的答案是 \( {171} + {512} \) ，即683
§4.8 期望值(Expected Value)
定理4.8.1
期望值(Expected value)是所有概率乘以对应取值的和。某种意义上，它是所有结果的平均值。你可能对此感到困惑，所以请继续阅读以理解其含义。
期望值是某一组结果的平均值。例如，假设我有 \( \frac{1}{3} \) 的概率赢得1美元，也有 \( \frac{1}{2} \) 的概率损失2美元，还有 \( \frac{1}{6} \) 的概率不赚不赔。那么，我们将每种结果的概率与其对应值相乘，再把所有乘积相加，就得到期望值。在此例中，第一个结果是赢得1美元，其概率为 \( \frac{1}{3} \) ；第二个结果是损失2美元，其概率为 \( \frac{1}{2} \) 。我们为三种结果写出方程: \( \left( {\frac{1}{3} \cdot 1}\right) + \left( {\frac{1}{2} \cdot \left( {-2}\right) }\right) + \left( {\frac{1}{6} \cdot 0}\right) \) 。写出期望值的表达式后，现在进行计算。记住，我写-2是因为你有 \( \frac{1}{2} \) 的概率损失2美元。各项相乘后得到 \( \frac{1}{3} + - 1 + 0 \) ，将它们相加得到 \( \frac{-2}{3} \) ，这就是期望值。
例4.8.2
如果我们有一个6面骰子，掷一次骰子的期望值是多少？
我们可能掷出的点数是1、2、3、4、5和6，每个点数出现的概率都是 \( \frac{1}{6} \) 。因此，我们只需将每个点数的概率与其值相乘，即可求出掷一次骰子的期望值。
\( = \frac{7}{2} \)
于是，一次掷骰的期望值就是简单的 \( \frac{7}{2} \)
如果我们想求50个骰子或25个骰子同时掷出的点数之和的期望值，现在该怎么做？如果逐个列出所有可能的和，将耗费极长时间。
定理4.8.3
期望的线性性(Linearity of Expectation)
如果我们有随机变量 \( \mathrm{X} \) 和 \( \mathrm{Y} \) ，那么 \( \mathrm{E}\left\lbrack {\mathrm{X} + \mathrm{Y}}\right\rbrack = \mathrm{E}\left\lbrack \mathrm{X}\right\rbrack + \mathrm{E}\left\lbrack \mathrm{Y}\right\rbrack \) (即使它们相关)。
你也可以对大量事件这样做，不限于两个。
例4.8.4
如果我们一次掷出六个骰子，求其点数之和的期望值。
在本题中，我们将使用期望的线性性质。
\( \mathrm{E}\left\lbrack {{X}_{1} + {X}_{2} + {X}_{3} + {X}_{4} + {X}_{5} + {X}_{6}}\right\rbrack = \mathrm{E}\left\lbrack {X}_{1}\right\rbrack + \mathrm{E}\left\lbrack {X}_{2}\right\rbrack + \mathrm{E}\left\lbrack {X}_{3}\right\rbrack + \mathrm{E}\left\lbrack {X}_{4}\right\rbrack + \mathrm{E}\left\lbrack {X}_{5}\right\rbrack + \mathrm{E}\left\lbrack {X}_{6}\right\rbrack \) \( = 6 \cdot \mathrm{E}\left\lbrack \text{One roll}\right\rbrack = 6 \cdot \frac{7}{2} = {21} \)
因此，根据期望的线性性质，6次掷骰子点数之和的期望值为21。
问题4.8.5——随机选取一个含四个1的13位二进制数，其期望值是多少？
解:最左边的数字显然必须是1。这意味着所有数字都会有一个 \( {2}^{12} \) 部分。
由于期望值就是各可能值与其概率乘积之和，我们可以求出每一位为1的概率。除去最左边那一位，还剩12位，因此其中任意一位为1的概率就是 \( \frac{3}{12} \) ，即 \( \frac{1}{4} \) (因为还需再选3个1)。
这意味着期望值为 \( {2}^{12} + \frac{1}{4}\left( {{2}^{11} + {2}^{10} + {2}^{9} + {2}^{8} + {2}^{7} + {2}^{6} + {2}^{5} + }\right. \) \( {2}^{4} + {2}^{3} + {2}^{2} + {2}^{1} + {2}^{0} \) 。
利用等比数列求和可得 \( {2}^{11} + {2}^{10} + {2}^{9} + {2}^{8} + {2}^{7} + \) \( {2}^{6} + {2}^{5} + {2}^{4} + {2}^{3} + {2}^{2} + {2}^{1} + {2}^{0} \) 等于 \( \frac{{2}^{12} - 1}{2 - 1} \) ，即4095。
我们的期望值为 \( {2}^{12} + \frac{4095}{4} \) ，即 \( \frac{20479}{4} \) 。
问题4.8.6——设 \( \mathcal{S} \) 为所有可表示为循环小数 \( 0.\overline{abc} \) 的实数集合，其中 \( a, b, c \) 为互不相同的数字。求 \( \mathcal{S} \) 中所有元素之和。
来源:2006 AIME
解:本题中，我们首先把 \( 0.\overline{abc} \) 化为分数。 \( x = 0.\overline{abc} \)
两边同乘1000得
\( {1000x} = {abc} \cdot \overline{abc} \)
两式相减得
\( {999x} = {abc} \)
最终得到 \( x = \frac{{100} \cdot a + {10} \cdot b + \cdot c}{999} \) (且 \( \mathrm{x} \) 也等于 \( 0.\overline{abc} \) )
由此可知， \( a, b, c \) 可以是0到9中的任意数字。与其逐一求和，不如计算每一位的期望值。每一位的期望值为4.5。于是
\( \mathrm{E}\left\lbrack \mathrm{x}\right\rbrack = \frac{{100} \cdot {4.5} + {10} \cdot {4.5} + \cdot {4.5}}{999}. \)
我们需将此结果乘以可能的数字总数 \( {10} \cdot 9 \cdot 8 \) (因所有数字必须互不相同)，即720。
\[ {720} \cdot \frac{{100} \cdot {4.5} + {10} \cdot {4.5} + \cdot {4.5}}{999} = \mathbf{{360}}. \]
§4.9 状态(马尔可夫链)
在马尔可夫链方程中，你根据可能到达的前一状态为当前点写出一个方程。你用前一状态的概率来表示每个状态的概率。
我强烈推荐观看这个视频以获得基础介绍:
https://www.youtube.com/watch?v=i3AkTO9HLXo
问题 4.9.1 —— 一只青蛙从点(1,2)开始连续跳跃，每次跳跃平行于坐标轴之一且长度为1，每次跳跃方向(上、下、右或左)独立随机选择。当青蛙到达顶点为 \( \left( {0,0}\right) ,\left( {0,4}\right) ,\left( {4,4}\right) \) 和(4,0)的正方形的任一边时，序列结束。求跳跃序列在正方形的垂直边上结束的概率。
\( \textbf{(A) }\frac{1}{2}\;\textbf{(B) }\frac{5}{8}\;\textbf{(C) }\frac{2}{3}\;\textbf{(D) }\frac{3}{4}\;\textbf{(E) }\frac{7}{8} \)
来源:2020 AMC 10
解答:从点(1,2)出发，青蛙可以移动到 \( \left( {1,1}\right) ,\left( {1,3}\right) ,\left( {0,2}\right) \) 和(2,2)。
青蛙落在这些位置中的每一个的概率都是 \( \frac{1}{4} \) 。如果它落在(0,2)，就到达了垂直边，这正是我们想要的。这种情况发生的概率是 \( \frac{1}{4} \) 。
如果它跳到点(1,1)或(1,3)，那么根据对称性，击中垂直边的概率是 \( \frac{1}{2} \) (想想对称性就知道为什么)。
青蛙落在其中一个点的概率是 \( \frac{1}{4} \cdot \frac{1}{2} \) ，即 \( \frac{1}{8} \) 。由于这个概率适用于两个点，我们必须乘以2，得到 \( \frac{1}{4} \) 。
最后一种情况是青蛙从起点跳到(2,2)。同样根据对称性，落在垂直边上的概率是 \( \frac{1}{2} \) 。这意味着这种情况的概率是 \( \frac{1}{4} \cdot \frac{1}{2} \) ，即 \( \frac{1}{8} \) 。
将我们的概率相加得到 \( \frac{1}{4} + \frac{1}{4} + \frac{1}{8} \) ，即 \( \frac{5}{8} \) (B)。
问题 4.9.2 —— Dave掷一枚公平的六面骰子，直到第一次出现6为止。Linda独立地掷一枚公平的六面骰子，直到第一次出现6为止。设 \( m \) 和 \( n \) 为互质的正整数，使得 \( \frac{m}{n} \) 是Dave掷骰子次数与Linda掷骰子次数相等或相差不超过1的概率。求 \( m + n \) 。
来源:2009 AIME
解答:设 \( {p}_{n} \) 表示在第 \( n \) 次掷骰子时第一次出现6的概率。容易看出 \( {p}_{n} = {\left( \frac{5}{6}\right) }^{n - 1} \cdot \frac{1}{6} = \frac{{5}^{n - 1}}{{6}^{n}} \) 。
容易看出我们的总概率是 \( {p}_{1}\left( {{p}_{1} + {p}_{2}}\right) + {p}_{2}\left( {{p}_{1} + {p}_{2} + {p}_{3}}\right) + {p}_{3}\left( {{p}_{2} + {p}_{3} + {p}_{4}}\right) \) …
代入几项后我们发现，从 \( {p}_{2}\left( {{p}_{1} + {p}_{2} + {p}_{3}}\right) \) 开始的每一项都是一个无穷等比数列的一部分。其公比为 \( \frac{25}{36} \) 。
我们的总概率可以通过使用无穷几何级数求得。因此，总概率为 \( {p}_{1}\left( {{p}_{1} + {p}_{2}}\right) + \frac{{p}_{2}\left( {{p}_{1} + {p}_{2} + {p}_{3}}\right) }{1 - \frac{25}{36}} \) 。
计算后得到答案 \( \frac{8}{33} \) ，于是得到 \( 8 + {33} = {41} \) 。
问题4.9.3——池塘里一排睡莲叶 \( 1,2,3,\ldots \) 。一只青蛙从第1片叶子开始连续跳跃。从任意一片叶子 \( k \) ，青蛙以概率 \( \frac{1}{2} \) 随机且独立地跳到叶子 \( k + 1 \) 或 \( k + 2 \) 。青蛙到达第7片叶子的概率为 \( \frac{p}{q} \) ，其中 \( p \) 与 \( q \) 为互质的正整数。求 \( p + q \) 。
来源:2019 AIME
解法:设到达第 \( n \) 片叶子的概率为 \( {p}_{n} \) 。
已知从第 \( k \) 片叶子只能跳到 \( k + 1 \) 或 \( k + 2 \) ，易得 \( {p}_{n} = \frac{1}{2}\left( {{p}_{n - 1} + {p}_{n - 2}}\right) \) 。
我们可以为 \( n = 3,4,5,6 \) 和7列出方程。
\( {p}_{3} = \frac{1}{2}\left( {{p}_{1} + {p}_{2}}\right) \)
\[ {p}_{4} = \frac{1}{2}\left( {{p}_{2} + {p}_{3}}\right) \]
\[ {p}_{5} = \frac{1}{2}\left( {{p}_{3} + {p}_{4}}\right) \]
\[ {p}_{6} = \frac{1}{2}\left( {{p}_{4} + {p}_{5}}\right) \]
\[ {p}_{7} = \frac{1}{2}\left( {{p}_{5} + {p}_{6}}\right) \]
由于我们从第 \( 1,{p}_{1} = 1 \) 片叶子出发，且 \( {p}_{2} = \frac{1}{2} \) 。将这两个值代入上述5个方程，可得 \( {p}_{7} = \frac{43}{64} \) ，于是答案为 \( {43} + {64} = \mathbf{{107}} \) 。
§4.10 几何概率
如果你曾遇到目标情况数量无限的问题，只需“作图”或画成图形即可。例如，假设我有两个数 \( x \) 和 \( y \) ，均在0到1之间。我们想知道满足 \( x + y < 1 \) 的概率。此时有无限多种可能，但可为此问题构造单位正方形并绘制 \( x + y = 2 \) 。然后，我们取该区域
这表明，当所需结果无法计数时，就将其作图，用目标区域面积除以整个区域面积。
问题4.10.1——两位数学家每天上午喝咖啡休息。他们独立地在上午9点到10点之间随机到达食堂，并停留 \( m \) 分钟。其中一人在另一人仍在食堂时到达的概率为 \( {40}\% \) ，且 \( m = a - b\sqrt{c} \) ，其中 \( a, b \) 和 \( c \) 为正整数，且 \( c \) 不被任何素数的平方整除。求 \( a + b + c \) 。来源:1998 AIME
解法:可绘制图形，使 \( x \) 轴和 \( y \) 轴范围均为0到60分钟。
有两种情况。第一位数学家在时刻 \( {M}_{1} \) 到达，第二位在 \( {M}_{2} \) 到达。若 \( {M}_{1} \) 早于 \( {M}_{2} \) ，则 \( {M}_{1} - {M}_{2} \leq m \) 。
若 \( {M}_{2} \) 早于 \( {M}_{1} \) ，则 \( {M}_{2} - {M}_{1} \leq m \) 。
将这两个不等式作图可得
显然，这两条直线围成的区域正是我们要计算的区域。与其直接求阴影面积，不如先求白色部分的面积，再用总面积减去它。
我们有两个等腰直角三角形，其直角边长度为 \( {60} - m \) 。一个直角三角形的面积为 \( \frac{\left( {{60} - m}\right) \left( {{60} - m}\right) }{2} \) ，乘以2得到两个三角形的总面积 \( \left( {{60} - m}\right) \left( {{60} - m}\right) \) 。
整个正方形的总面积为 \( {60} \cdot {60} \) ，即3600。已知未阴影部分所占面积的比例为 \( 1 - {0.4} = {0.6} \) 。
将其写成方程即 \( \frac{\left( {{60} - m}\right) \left( {{60} - m}\right) }{3600} = {0.6} \)
解得 \( m = {60} - {12}\sqrt{15} \) 。
因此，答案为 \( {60} + {12} + {15} \) ，即87。
问题4.10.2——设 \( S \) 为边长为1的正方形。在其四条边上独立随机地各取一点，这两点之间的直线距离不小于 \( \frac{1}{2} \) 的概率为 \( \frac{a - {b\pi }}{c} \) ，其中 \( a, b \) 、 \( c \) 为正整数且 \( \gcd \left( {a, b, c}\right) = 1 \) 。求 \( a + b + c \) 。
(B) 60
来源:2015 AMC
来源:本题中，可将正方形的一条边上的某一点固定。设点 \( \mathrm{A} \) 固定在该边上，则点 \( \mathrm{B} \) 可落在相邻边、同一边或对边上。
情况1:两点落在同一条边上。由于同一条边上有无穷多个位置，可通过作图观察此情况发生的概率。
易见两点在同一边且距离大于 \( \frac{1}{2} \) 的概率为 \( \frac{1}{4} \) 。然而，还需乘以 \( \frac{1}{4} \) ，因为这是点 \( \mathrm{B} \) 落在点 \( \mathrm{A} \) 所在边的概率。此情况的总概率为 \( \frac{1}{16} \) 。
情况2:点B落在与A相邻的边上。设点A位于(x,0)，点B位于(0, y)，则两点间距离为 \( \sqrt{{x}^{2} + {y}^{2}} \) ，且该距离需满足 \( \geq \frac{1}{2} \) 。
两边平方得 \( {x}^{2} + {y}^{2} \geq \frac{1}{4} \) 。该圆的半径为 \( \frac{1}{2} \) ，总面积为 \( \frac{\pi }{4} \) 。然而，我们只需四分之一圆的面积，因为要从正方形面积中减去它。通过作图可见，四分之一圆的面积为整个圆面积的1/4，即 \( \frac{\pi }{16} \) 。用1减去该面积得 \( \frac{{16} - \pi }{16} \) 。
再乘以 \( \frac{1}{2} \) ，即点落在与点 \( \mathrm{A} \) 所在边相邻的边的概率。
此情况的总概率为 \( \frac{{16} - {pi}}{32} \) 。
情况3:现在点B位于与点A相对的一侧。我们选择与点 \( \mathrm{A} \) 所在边相对的那一侧的概率为 \( \frac{1}{4} \) 。无论点 \( \mathrm{B} \) 位于与点 \( \mathrm{A} \) 所在边相对的那一侧的何处，它们之间的距离始终为 \( \geq \frac{1}{2} \) 。因此，此情况的总概率为 \( \frac{1}{4} \) 。
将所有概率相加得到 \( \frac{1}{16} + \frac{{16} - \pi }{32} + \frac{1}{4} \) ，即 \( \frac{{26} - \pi }{32} \) 。
我们的最终答案是 \( {26} + 1 + {32} \) ，即 \( \mathbf{{59}\left( A\right) } \) 。