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