「题解」P6130 随机红包
do_while_true
·
·
题解
在 [0,1] 上随机撒 (n-1) 个点划分成 n 段，求第 k 大的段长的期望。
从 Appleblue17 老师的题解中学的，大概详细写很多一笔带过但是我不认为很简单的步骤。
Part 1
令随机变量 X 为第 k 大的段长。E(X)=\int_0^1P(X=x)x\text dx=\int_0^1P(X\geq x)\text dx=1-\int_0^1P(X<x)\text dx，现在来计算 P(X<x)．
第 k 大 <x 当且仅当恰好有 t 个 \geq x 其中 t<k．
运用二项式反演，令 f_t 表示恰好 t 个 \geq x 的概率，g_t 表示钦定 t 个 \geq x 的概率，那么有：
g_t=\sum_{i=t}^n\binom{i}{t}f_t
\\
f_t=\sum_{i=t}^n(-1)^{i-t}\binom{i}{t}g_t
而 P(X<x) 就是 \sum_{t=0}^{k-1}f_t．
Part 2
考虑计算 g_t，首先乘上组合数 \binom{n}{t} 选出钦定的段，使得“钦定的段”与“未钦定的段”之间没有顺序区分，这样就能将钦定段按顺序放到最前面。
通过用 \binom{n}{t} 去除掉“钦定的段”与“未钦定的段”之间的顺序，我们来构建《[0,1] 随机放点，前 t 个段段长 \geq x》与《[0,1] 随机放点，所有点均落在 [tx,1] 中》这两个问题的双射。
前者映射到后者：将前 t 段每段劈成长为 x 和长为 len-x 的两部分，再把长为 len-x 的部分移动到这 t 个长为 x 段的右侧。这样就是最前面有 t 个长为 x 的段，然后剩下 (1-tx) 的长度分了 n 段。
后者映射到前者：将 [tx,1] 被劈开的 n 部分中的前 t 部分分配给前面那 t 个 x．
通过这个双射，得到 g_t=(1-tx)^{n-1}．
注：我不知道有没有更好的处理方式，我能想到的比较严谨的证明就是这个。
Part 3
组合上的手法到此结束了，现在就能列出答案进行推式子了。答案是：
\begin{aligned}
&1-\int_0^1 P(X<x)\text dx
\\
=&1-\int_0^1 \sum_{t=0}^{k-1}\sum_{i=t}^n[ix\leq 1](-1)^{i-t}\binom{i}{t}\binom{n}{i}(1-ix)^{n-1}\text dx
\end{aligned}
想通过交换求和号与积分号通过将积分的上界改写成 \frac{1}{i} 来去掉 [ix\leq 1] 的限制，将 t=i=0 的那一项单独拿出来就能往下写了。
\begin{aligned}
=&1-\int_0^1 \sum_{t=0}^{k-1}\sum_{i=t}^n[i>0](-1)^{i-t}\binom{i}{t}\binom{n}{i}(1-ix)^{n-1}-1
\\
=&-\sum_{t=0}^{k-1}\sum_{i=t}^n[i>0](-1)^{i-t}\binom{i}{t}\binom{n}{i}{\color{Red}\int_0^1(1-ix)^{n-1}\text dx}
\\
=&-{\color{Red}\frac{1}{n}}\sum_{t=0}^{k-1}\sum_{i=t}^n[i>0](-1)^{i-t}\binom{i}{t}\binom{n}{i}{\color{Red}\frac{1}{i}}
\end{aligned}
最后一步需要求 (1-ix)^{n-1} 的不定积分：
\begin{aligned}
&\int(1-ix)^{n-1}\text dx
\\
=&\int(1-ix)^{n-1}(-i)\text dx/(-i)
\\
=&\int (1-ix)^{n-1}\text d(1-ix)/(-i)
\\
=&\frac{(1-ix)^n}{-in}
\end{aligned}
这个就是第一换元积分法，(1-ix)^{n-1}=u^{n-1} 换元，利用 \frac{\text du}{\text dx}=u'\Rightarrow u'\text dx=\text du，把 \text du 凑出来，这样就转化成了求 \int u^{n-1}\text du．
Part 4
然后将 t=0 这一项单独拿出来看，先不去管 -\frac{1}{n}：
\sum_{i=1}^n(-1)^i\binom{n}{i}\frac{1}{i}
两种解法。
第一种解法的思路大概是这个形式看上去就很想去吸收，但是不能直接用吸收恒等式，那么就沿用吸收恒等式的思路去想办法把 \frac{1}{i} 凑到某个阶乘里面形成另一个组合数，从而想到去运用上指标求和：
\begin{aligned}
=&\sum_{i=1}^n(-1)^i\sum_{j=0}^{n-1}\binom{j}{i-1}\frac{1}{i}
\\
=&\sum_{i=1}^n(-1)^i\sum_{j=0}^{n-1}\binom{j+1}{i}\frac{1}{j+1}
\\
=&\sum_{j=0}^{n-1}\frac{1}{j+1}\sum_{i=1}^{j+1}(-1)^i\binom{j+1}{i}
\\
=&-\sum_{j=1}^{n}\frac{1}{j}
\end{aligned}
最后一步是将后面的求和号写成 (1-1)^{j+1}-1．
第二种解法的思路是去凑二项式定理的形式，那就需要把 \frac{1}{i} 这里的 i 放到指数上，把它写成一个定积分 \frac{1}{i}=\int_0^1 t^{i-1}\text dt
\begin{aligned}
=&\sum_{i=0}^n(-1)^i\binom{n}{i}\int_0^1 t^{i-1}\text dt
\\
=&\int_0^1\text dt\frac{1}{t}\sum_{i=0}^n(-1)^i\binom{n}{i} t^i
\\
=&\int_0^1\text dt\frac{(1-t)^n}{t}
\\
=&\int_0^1\text dt\frac{(1-t)^n}{1-(1-t)}
\\
=&\int_0^1\text dt\sum_{i=0}^{n-1}(1-t)^i
\\
=&\sum_{i=0}^{n-1}\int_0^1\text dt(1-t)^i
\\
=&-\sum_{i=1}^{n}\frac{1}{i}
\end{aligned}
第三行到第四行是去凑等比数列求和，然后再对等比数列每一项积分。最后一步省略的就是前面说的第一类换元积分法（凑微分）。
所以 t=0 这部分对答案的贡献是 \frac{1}{n}\sum_{i=1}^n\frac{1}{i}．
Part 5
看 t>0 的那些：
\begin{aligned}
=&-\frac{1}{n}\sum_{t=1}^{k-1}\sum_{i=t}^n(-1)^{i-t}\binom{i}{t}\binom{n}{i}\frac{1}{i}
\\
=&-\frac{1}{n}\sum_{t=1}^{k-1}\sum_{i=t}^n(-1)^{i-t}\frac{1}{t}\binom{i-1}{t-1}\binom{n}{i}
\\
=&-\frac{1}{n}\sum_{t=1}^{k-1}\frac{1}{t}\sum_{i=0}^{n-t}(-1)^i\binom{i+t-1}{t-1}\binom{n}{i+t}
\end{aligned}
发现 (-1)^i\binom{i+t-1}{t-1} 形式太好看了，它就是 [x^i]\frac{1}{(1+x)^t}（广义二项式定理之后上指标反转），那就把两个组合数都去写成生成函数的某一项系数：
\begin{aligned}
=&-\frac{1}{n}\sum_{t=1}^{k-1}\frac{1}{t}\sum_{i=0}^{n-t}\left([x^i]\frac{1}{(1+x)^t}\right)\left([x^{n-i-t}](1+x)^{n}\right)
\end{aligned}
这正是个卷积的形式，那么：
\begin{aligned}
=&-\frac{1}{n}\sum_{t=1}^{k-1}\frac{1}{t}[x^{n-t}](1+x)^{n-t}
\\
=&-\frac{1}{n}\sum_{t=1}^{k-1}\frac{1}{t}
\end{aligned}
加上 t=0 的 \frac{1}{n}\sum_{i=1}^n\frac{1}{i}，我们得到了最终的答案：
\frac{1}{n}\sum_{i=k}^{n}\frac{1}{i}
End.