note[15]

题：数论函数 $F(x)$ ，在 $1$ 到 $n$ 里随机选 $k$ 个数，可以重复选/不可以重复选，$F$ 值之和的期望？

解：

1. 不可以重复选：

   $$\begin{aligned} \mathbb{E}(X) & =\mathbb{E}\left(\sum_{i=1}^k F\left(c_i\right)\right) \\ & =\sum_{i=1}^k \mathbb{E}\left(F\left(c_i\right)\right) \\ & =k \sum_{i=1}^n \frac{1}{n} \cdot F(i) \\ & =\frac{k}{n} \sum_{i=1}^n F(i) \end{aligned}$$

2. 可以重复选：

   $$\begin{aligned} \mathbb{E}(X) & =\mathbb{E}\left(\sum_{i=1}^n c_i \cdot F(i)\right) \\ & =\sum_{i=1}^k \mathbb{E}\left(c_{t_i} \cdot F(t_i)\right) \\ & =\sum_{i=1}^n \frac{\binom{n-1}{k-1}}{\binom{n}{k}} F(i) \\ & =\frac{k}{n} \sum_{i=1}^n F(i) \end{aligned}$$

   这里第三步钦定当前数必定被选，于是从剩下的 $n-1$ 个数中选 $k-1$​ 个数。

---

参考文献：

[1] https://www.cnblogs.com/CDOI-24374/p/16703380.html