自动搬运

查看原文

来自洛谷，原作者为

	Elegia irony

搬运于2025-08-24 22:14:42，当前版本为作者最后更新于2019-12-23 18:14:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

普及一个奇妙的组合意义证明。

我们首先将答案除以 $n!$ 这样就是概率，考虑 $n$ 个实数的均匀分布 $(a_1, a_2, \cdots, a_n) \in (0, 1)^n$，显然有两个实数相等的概率是 $0$，那么根据对称性 $a_i$ 的大小关系服从排列 $p_i$ 是等概率的。也就是说我们转而考虑 $a_i < a_{i + 1}$ 的位置有 $k$ 个的概率。

令 $a_0 = 0$，考虑差分 $b_i = (a_i - a_{i - 1}) \bmod 1$，因此 $b_i \in (0, 1)$ 且我们可以认为建立了 $(b_1, b_2, \cdots, b_n)$ 到 $(a_1, a_2, \cdots, a_n)$ 的一个“均匀”映射。

考虑 $\sum_{i = 1}^n b_i$ 的意义，如果 $a_i < a_{i + 1}$ 那么说明 $b_{i + 1}$ 没有在取模时加一，否则发生了加一。因此 $\sum b_i = a_n + n - 1 - k$，也就是说我们仅仅是在计算对于实数 $x_1, x_2, \cdots, x_n \in (0, 1)$，$\sum x_i \in (n - 1 - k, n - k)$ 的概率我们只需算出 $\sum x_i < n - k$ 的概率然后差分即可。

考虑形式上我们虽然是求概率，但是考虑扩展为“测度”，也就是对于可行的每一部分的 $n$ 维微元进行求和，我们可以先假设没有 $x_i < 1$ 的限制，那么总共的测度是 $\frac{(n-k)^n}{n!}$。进行容斥，假设有 $j (j \le n - k)$ 个数强制 $\ge 1$，那么这一部分的测度是 $\frac{(n - k - j)^n}{n!}$。

因此概率可以通过一部中间运算得到：

$$\sum_{j=0}^{n-k} (-1)^j \binom n j \frac{(n - k - j)^n}{n!} = \sum_{j = 0}^{n - k} \frac{(-1)^j}{j!(n - j)!} (n - k - j)^n $$

一次卷积。