求置换逆序数交替和为零的初等计数证明

首先明确问题背景：

设$a_1a_2\ldots a_n$是${1,\ldots,n}$的一个置换，逆序指满足$i<j$但$a_i>a_j$的有序对$(a_i,a_j)$。例如置换1 4 3 5 2的逆序为$(4,3)$、$(4,2)$、$(3,2)$、$(5,2)$，共4个。记$I_{n,k}$为恰有$k$个逆序的$n$元置换的个数，求证：
$$\sum_{k=0}^{\binom{n}{2}} (-1)^k I_{n,k} = 0$$

核心思路：构造对合映射配对置换 #

咱们用初等计数里的对合映射（即满足$f(f(\sigma))=\sigma$的映射）来搞定这个证明，思路很直观：把所有置换两两配对，让每一对的交替和抵消为0，最后总和自然就是0。

具体构造这个映射$f$：

• 对于任意$n$元置换$\sigma$（$n \geq 2$），找到元素1在$\sigma$中的位置：
  1. 如果1不在最后一个位置，就把1和它右侧相邻的元素交换，得到新置换$f(\sigma)$；
  2. 如果1在最后一个位置，就把1和它左侧相邻的元素交换，得到新置换$f(\sigma)$。

验证映射的关键性质 #

1. 对合性：对任意置换$\sigma$，$f(f(\sigma))=\sigma$。因为交换1的位置一次后，再交换一次必然回到原置换，这是显然的。
2. 改变逆序数的奇偶性：
   • 元素1是${1,\dots,n}$中最小的元素，假设1在$\sigma$中的位置是$m$：
     • 若$m < n$，交换1到$m+1$位置后，原本有$(m-1)$个逆序包含1（左边的$m-1$个元素都比1大），交换后包含1的逆序变为$m$个（左边的$m$个元素都比1大），逆序数增加1，奇偶性翻转；
     • 若$m = n$，交换1到$n-1$位置后，原本有$(n-1)$个逆序包含1，交换后变为$(n-2)$个，逆序数减少1，奇偶性同样翻转。
   • 所有不涉及1的逆序在交换前后完全不变，因此整个置换的逆序数奇偶性必然改变。
3. 无不动点：当$n \geq 2$时，不存在置换$\sigma$使得$f(\sigma)=\sigma$——因为交换1的位置必然改变它的位置，不可能和原置换相同。

推导结论 #

所有$n$元置换（$n \geq 2$）可以被分成若干两两配对的组$(\sigma, f(\sigma))$，每组中两个置换的逆序数奇偶性相反，对应的$(-1)^{k$项分别为$(-1)}k$和$(-1)^{{k+1}$，两者相加为$(-1)}k + (-1)^{k+1} = 0$。

把所有组的贡献加起来，总和自然就是0，即：
$$\sum_{k=0}^{\binom{n}{2}} (-1)^k I_{n,k} = 0$$

注：当$n=1$时，左边的和为1，不符合等式，但题目显然默认$n \geq 2$（毕竟$n=1$时逆序的概念没有实际意义）。

内容的提问来源于stack exchange，提问作者StefanH