题解 P5825 【排列计数】

普及一个奇妙的组合意义证明。 我们首先将答案除以 $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 $$ 一次卷积。