2017 USAMO 第 2 题

Let $m_1, m_2, \ldots, m_n$ be a collection of $n$ positive integers, not necessarily distinct. For any sequence of integers $A = (a_1, \ldots, a_n)$ and any permutation $w = w_1, \ldots, w_n$ of $m_1, \ldots, m_n$, define an $A$-inversion of $w$ to be a pair of entries $w_i, w_j$ with $i < j$ for which one of the following conditions holds:

$$a_i \ge w_i > w_j,$$

$$w_j > a_i \ge w_i,$$

or

$$w_i > w_j > a_i.$$

Show that, for any two sequences of integers $A = (a_1, \ldots, a_n)$ and $B = (b_1, \ldots, b_n)$, and for any positive integer $k$, the number of permutations of $m_1, \ldots, m_n$ having exactly $k$ $A$-inversions is equal to the number of permutations of $m_1, \ldots, m_n$ having exactly $k$ $B$-inversions.

令 $m_1, m_2, \ldots, m_n$ 为 $n$ 个正整数的集合，不一定是不同的。对于任何整数序列 $A = (a_1, \ldots, a_n)$ 以及 $m_1, \ldots, m_n$ 的任何排列 $w = w_1, \ldots, w_n$，将 $w$ 的 $A$ 反转定义为一对条目 $w_i, w_j$，且 $i < j$ 满足以下条件之一：

$$a_i \ge w_i > w_j,$$

$$w_j > a_i \ge w_i,$$

或

$$w_i > w_j > a_i。$$

证明，对于任意两个整数序列 $A = (a_1, \ldots, a_n)$ 和 $B = (b_1, \ldots, b_n)$，以及对于任何正整数 $k$，恰好具有 $k$ $A$ 反转的 $m_1, \ldots, m_n$ 的排列数等于恰好具有 $k$ $A$ 反转的 $m_1, \ldots, m_n$ 的排列数$k$ $B$-反转。