在 \([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.
标签：红包,aligned,frac,int,题解,sum,text,binom,P6130 From： https://www.cnblogs.com/do-while-true/p/18016306