这里我不会严谨证明公式 $(2)$,但是我们可以感性地理解这个公式:
对于第 $i$ 位数字,只考虑其及其右边的部分排列.我们来考虑有多少种排列比当前排列的序数小.
第 $i$ 位数字右侧有 $a_i$ 位比它小的数字,代表任取这 $a_i$ 个数字中任意一个与 $k_i$ 交换位置,都只会得到比当前排列更小的排列序数(字典序).因此,不妨随意取一个,考虑这样交换后会获得多少种排列?
注意到我们只是考虑了 $i$ 位对应的 $a_i$ ,其后具体的排列并没有引入这里,因此可以对其右侧继续进行这样的计算并累加到最终结果.最终,就可以得到公式 $(2)$.