题目描述
题意：每次抽卡时会从 \(n\) 种卡里随机获得一种，那么期望上抽到全部 \(n\) 种卡需要抽多少次？
提示：随机试验中某个变量的数学期望（简称“期望”）是指该变量所有可能的结果的概率乘以其结果的总和。例如一个理想情况下的骰子的点数的数学期望由
\[\frac16\times1+\frac16\times2+\frac16\times3+\frac16\times4+\frac16\times5+\frac16\times6=\frac72 \]给出。而投掷两个理想情况下的骰子得到的点数之和的期望由
\[\frac{1}{36}\times2+\frac{2}{36}\times3+\frac{3}{36}\times4+\frac{4}{36}\times5+\frac{5}{36}\times6+\frac{6}{36}\times7+\frac{5}{36}\times8+\frac{4}{36}\times9+\frac{3}{36}\times10+\frac{2}{36}\times11+\frac{1}{36}\times12=7 \]给出。
容易验证，当 \(n=5\) 的时候，答案为 \(137/12\)。
解答
我们用记号 \(\mathbf E(a)\) 表示随机试验中变量 \(a\) 的数学期望。已经抽卡的次数简称为时刻，例如“取出抽出 \(3\) 张不同种的卡的时刻”的意思是“取出抽出 \(3\) 张不同种的卡时已经进行的抽卡次数”。
设这 \(n\) 种卡片首次出现的时间构成的可重集合为 \(S\)，所求即为 \(\mathbf E(\max S)\)，根据容斥原理（min-max容斥），有
\[\mathbf E(\max S)=\sum_{T\subseteq S,T\neq\varnothing}(-1)^{|T|-1}\mathbf E(\min S) \]考虑 \(\mathbf E(\min T)\) 的组合意义，即为集合 \(T\) 中对应包含的卡片首次出现的时刻的期望，于是 \(\mathbf E(\min T)=n/|T|\)，代回原式，得到
\[\begin{aligned}\mathbf E(\max S)&=\sum_{T\subseteq S,T\neq\varnothing}(-1)^{|T|-1}\frac n{|T|}\\&=n\sum_{k=1}^n(-1)^{k-1}\binom nkk^{-1}\end{aligned} \]考虑右边的那个和式怎么处理，记
\[S_n=\sum_{k=1}^n(-1)^{k-1}\binom nkk^{-1} \]考虑对 \(S_n\) 应用加法公式
\[\binom nk=\binom{n-1}{k-1}+\binom{n-1}k \]以及吸收恒等式
\[\binom nk=\frac nk\binom{n-1}{k-1} \]得到
\[\begin{aligned}S_n&=\sum_{k=1}^n(-1)^{k-1}\left(\binom{n-1}{k-1}+\binom{n-1}k\right)k^{-1}\\&=\frac1n\sum_{k=1}^n(-1)^{k-1}\binom nk+\sum_{k=1}^{n-1}(-1)^{k-1}\binom{n-1}kk^{-1}\\&=S_{n-1}+\frac1n\end{aligned} \]考虑到 \(S_0=0\)，这立即得出原问题的答案是 \(n\mathrm H_n\)，其中 \(\mathrm H_n\) 为第 \(n\) 项调和级数，其公式由
\[\mathrm H_n=\sum_{k=1}^n\frac1k \]给出。
2022年12月19日 于东莞松山湖
标签：frac16,frac,组合,sum,选讲,36,mathbf,binom,杂题 From： https://www.cnblogs.com/szdytom/p/combinatorial-misc-7.html