2022年阿里巴巴全球数学竞赛四名金牌得主可获得4万美元的奖金。任何人都可以参加资格赛。奖牌获得者往往是专业数学家或IMO奖牌获得者。本文的问题来自2022年阿里巴巴全球数学竞赛资格赛，可以编程。

问题

一家牛奶公司在新年举办促销活动，每盒牛奶赠送一个红包（卡片）。每个卡片都有一个汉字，汉字可能是虎 、生、威 ，且概率相等。人们试图收集两个虎，一个生和一个威，这样他们就可以组成幸运短语“虎虎生威”。

问：获得“虎虎生威”所需的牛奶盒数的期望值是多少？

A)19/3B) 22/3C) 25/3D) 28/3E)以上都不是

为了计算期望值，我们需要将每一个（无限个）可能的结果乘以其概率并取其和。

在从数学上求得这个无限和之前，我决定使用Python运行一个模拟。字母“H”，“S”，“W”代表三个汉字虎，生和威：

随机选择“H”，“S”，“W”，并将其添加到列表中；

重复，直到列表有所需的[' H '， ' H '， ' S '， ' W ']；

计算它进行了多少次选择并记录结果；

重复一万次。

这10,000次试验的平均值为7.3236。为10000个结果可视化直方图，

样本均值为7.3236，这让我猜测答案是B。但也有可能是E，我们应该从数学上推导出结果。

所以我用计数的方法来计算n张牌“获胜（HHSW）”的概率。我想找出包含HHSW的n张卡片的总排列数，然后用这个数除以n张卡片的总排列数。分母上的总数是3^n。

下面是一个Python程序，用于计算n的前几个值的情况。

输出为：

共4张卡，81个选项中，有12个包含HHSW

共5张卡，243个选项中，有80个包含HHSW

共6张卡，729个选项中，有360个包含HHSW

共7张卡，2187个选项中，有1372个包含HHSW

共8张卡，6561个选项中，有4788个包含HHSW

4张卡的情况下，获得HHSW的概率是12/81并不难，

在4个地方中有2个地方需要放置H牌，所以有6种方法可以做到这一点。那么剩下的两张牌必须是SW或WS，那么分子上的数就是6×2=12。

但如果是5张牌获胜，“HHSW”的概率就不是80/243了。尽管有80种方法将HHSW安排在5张卡中，但其中12种HHSW将出现在前4张纸牌中，在这种情况下“游戏”便会停止。

因此，我改进了这个程序，然后只对HHSW之前没有出现过的列表进行计数。下面是使用递归方法的代码：

输出:

共4张卡，81个选项中，有12个包含HHSW

共5张卡，207个选项中，有44个包含HHSW

共6张卡，489个选项中，有120个包含HHSW

共7张卡，1107个选项中，有292个包含HHSW

共8张卡，5319个选项中，有1500个包含HHSW

推导一个显式公式

现在这些计数可以用来正确地给出每一步的“获胜（HHSW）”概率。但要记住，要拿到第5张牌，我们还需要第4张牌“失败”。为了在第6张牌上获胜，需要在第4张和第5张牌上失败，以此类推。

但是为了继续计算这个无穷和，我们需要理解这些数字的由来。

在5张卡片中，应该有44种方法能够获得HHSW。我们把它们分为三种情况，因为最后一张牌必须是H、S或W中的一张。

情形1：第5张牌是H

这意味着前4张卡片必须包含一个H，然后至少包含一个S和w。将H放在前面有4个选项。对于剩下的3张卡，有2^3种情况只包含S, W卡，但其中两种（SSS和WWW）排除。所以总排列数是4(2^3−2)= 24。

情形2：第5张牌是S

所以前4张卡必须只包含H, W卡，至少有两张H卡和一张W卡。有2^4种情况只包含H, W张牌，但需要删除HHHH, WWWW和没有H的4种情况，所以总排列的数量是2^4 − 2 − 4 = 10。

情形3：第5张牌是W

这与情形2是对称的，所以排列的数量是10。

令人高兴的是，这3种情况总共提供了44种用5张纸牌“获胜（集齐HHSW）”的方法。

概括以上3种情况可以帮助我们给出第n张牌获胜的公式，

情形1：第n张牌是H

这意味着前面（n−1）个卡片必须包含一个H，然后至少包含一个S和w。将H放在前面有（n−1）个选项。对于剩下的（n-2）个卡，有2^（n−2）种排列只包含S, W卡，但其中两个（SSS…S和WWW...W）要排除。所以排列的总数是

情形2：第n张牌是S

所以前面（n−1）卡必须只包含H, W卡，至少有两张H卡和一张W卡。有2^(n−1)种排列只包含H, W张卡片，但需要删除HHH…H, WWW...W和只有一个H的（n−1）种排列，因此排列的数量为

情形3：第5张牌是W

这和情形二是对称的，所以排列的次数是

对这三种情况的总结得到了第n张牌获胜的总概率的公式。我现在将它定义为p_n：

回到期望值表达式，我们还需要包括之前未获胜的概率：

看起来挺复杂的。但是我们注意到，分母也可以写成p_n的形式，这就简化了很多。每个分母都是

无穷级数就变成了

将p_n替换为n的表达式，得到

如何计算这个无穷级数？我在维基百科上找到了以下公式:

最后两个公式正是我所需要的。取前两项z = 2/3，后一项z = 1/3：

注意，这些和的下限是1。对于我们的期望值，下限是4，但是计算n = 1，2，3的和并减去并不太难：

因此，答案为B。你有更好的解题方法吗？