Problem: Let $m_1$, $m_2$, \dots, $m_n$ be a collection of $n$ positive integers,
not necessarily distinct.
For any sequence of integers $A = (a_1, \dots, a_n)$
and any permutation $w = w_1, \dots, w_n$ of $m_1, \dots, 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:
\begin{itemize}
  \ii $a_i \ge w_i > w_j$,
    \ii $w_j > a_i \ge w_i$, or
    \ii $w_i > w_j > a_i$.
\end{itemize}
Show that, for any two sequences of integers
$A = (a_1, \dots, a_n)$ and $B = (b_1, \dots, b_n)$,
and for any positive integer $k$, the number of permutations
of $m_1, \dots, m_n$ having exactly $k$ $A$-inversions
is equal to the number of permutations of $m_1, \dots, m_n$
having exactly $k$ $B$-inversions.

Solution: The following solution was posted by Michael Ren,
and I think it is the most natural one
(since it captures all the combinatorial ideas
using a $q$-generating function that is easier to think about,
and thus makes the problem essentially a long computation).

Denote by $M$ our multiset of $n$ positive integers.
Define an \emph{inversion} of a permutation to be pair $i < j$
with $w_i < w_j$ (which is a $(0,\dots,0)$-inversion in the problem statement);
this is the usual definition
(see \url{https://en.wikipedia.org/wiki/Inversion_(discrete_mathematics)}).
So we want to show the number of $A$-inversions
is equal to the number of usual inversions.
In what follows we count permutations on $M$ with multiplicity:
so $M = \{1,1,2\}$ still has $3!=6$ permutations.

We are going to do what is essentially recursion,
but using generating functions in a variable $q$ to do our book-keeping.
(Motivation: there's no good closed form for the number of inversions,
but there's a great generating function known --- which is even better
for us, since we're only trying to show two numbers are equal!)
First, we prove two claims.

\begin{claim*}
  For any positive integer $n$,
  the generating function for the number of permutations
  of $(1, 2, \dots, n)$ with exactly $k$ inversions is
  \[ n!_q \coloneq 1 \cdot (1+q) \cdot (1+q+q^2) \cdot \dots (1+q+\dots+q^{n-1}). \]
\end{claim*}
Here we mean that the coefficient of $q^s$ above
gives the number of permutations with exactly $s$ inversions.
\begin{proof}
  This is an induction on $n$, with $n=1$ being trivial.
  Suppose we choose the first element to be $i$, with $1 \le i \le n$.
  Then there will always be exactly $i-1$ inversions
  using the first element,
  so this contributes $q^i \cdot (n-1)!_q$.
  Summing $1 \le i \le n$ gives the result.
\end{proof}
Unfortunately, the main difficulty of the problem
is that there are repeated elements,
which makes our notation much more horrific.

Let us define the following.
We take our given multiset $M$ of $n$ positive integers,
we suppose the distinct numbers are
$\theta_1 < \theta_2 < \dots < \theta_m$.
We let $e_i$ be the number of times $\theta_i$ appears.
Therefore the multiplicities $e_i$ should have sums
\[ e_1 + \dots + e_m = n \]
and $m$ denotes the number of distinct elements.
Finally, we let
\[ F(e_1, \dots, e_m)
  = \sum_{\text{permutations } \sigma}
  q^{\text{number inversions of } \sigma} \]
be the associated generating function for the number of inversions.
For example, the first claim we proved says that $F(1, \dots, 1) = n!_q$.

\begin{claim*}
  We have the explicit formula
  \[ F(e_1, \dots, e_m) = n!_q \cdot \prod_{i=1}^m \frac{e_i!}{e_i!_q}. \]
\end{claim*}
\begin{proof}
  First suppose we perturb all the elements slightly,
  so that they are no longer equal.
  Then the generating function would just be $n!_q$.

  Then, we undo the perturbations for each group,
  one at a time, and claim that we get the above $e_i!_q$ factor each time.
  Indeed, put the permutations into classes of $e_1!$ each
  where permutations in the same classes differ
  only in the order of the perturbed $\theta_1$'s
  (with the other $n-e_1$ elements being fixed).
  Then there is a factor of $e_1!_q$ from each class,
  owing to the slightly perturbed inversions we added within each class.
  So we remove that factor and add $e_1! \cdot q^0$ instead.
  This accounts for the first term of the product.

  Repeating this now with each term of the product implies the claim.
\end{proof}

Thus we have the formula for the number of inversions in general.
We wish to show this also equals the generating function
the number of $A$-inversions, for any fixed choice of $A$.
This will be an induction by $n$, with the base case being immediate.

For the inductive step, fix $A$,
and assume the first element satisfies
$\theta_k \le a_1 < \theta_{k+1}$ (so $0 \le k \le m$;
we for convenience set $\theta_0 = -\infty$ and $\theta_m = +\infty$).
We count the permutations based on what the first element
$\theta_i$ of the permutation is.
Then:
\begin{itemize}
  \ii Consider permutations starting with
  $\theta_i \in \left\{ \theta_1, \dots, \theta_k \right\}$.
  Then the number of inversions which will
  use this first term is $(e_1 + \dots + e_{i-1})
  + (e_{k+1} + \dots + e_m)$.
  Also, there are $e_i$ ways to pick which
  $\theta_i$ gets used as the first term.
  So we get a contribution of
  \[ q^{e_1 + \dots + e_{i-1} + (e_{k+1} + \dots + e_m)}
    \cdot e_i \cdot F(e_1, \dots, e_i-1, \dots, e_m) \]
  in this case
  (with inductive hypothesis to get the last $F$-term).

  \ii Now suppose $\theta_i \in \left\{ \theta_{k+1}, \dots, \theta_m \right\}$.
  Then the number of inversions which will
  use this first term is $e_{k+1} + \dots + e_{i-1}$.
  Thus by a similar argument the contribution is
  \[ q^{e_{k+1} + \dots + e_{i-1}}
    \cdot e_i \cdot F(e_1, \dots, e_i-1, \dots, e_m). \]
\end{itemize}
Therefore, to complete the problem it suffices to prove
\begin{align*}
  &\phantom+ \sum_{i=1}^k q^{(e_1 + \dots + e_{i-1}) + (e_{k+1} + \dots + e_m)}
    \cdot e_i \cdot F(e_1, \dots, e_i-1, \dots, e_m) \\
  &+ \sum_{i=k+1}^m q^{e_{k+1} + \dots + e_{i-1}}
    \cdot e_i \cdot F(e_1, \dots, e_i-1, \dots, e_m) \\
  &= F(e_1, \dots, e_m).
\end{align*}
Now, we see that
\[ \frac{e_i \cdot F(e_1, \dots, e_i-1, \dots, e_m)}{F(e_1, \dots, e_m)}
  = \frac{1+\dots+q^{e_i-1}}{1+q+\dots+q^{n-1}}
  = \frac{1-q^{e_i}}{1-q^n} \]
so it's equivalent to show
\[ 1-q^n
  = q^{e_{k+1} + \dots + e_m} \sum_{i=1}^k q^{e_1 + \dots + e_{i-1}}(1-q^{e_i})
  + \sum_{i=k+1}^m q^{e_{k+1} + \dots + e_{i-1}} (1-q^{e_i})
\]
which is clear,
since the left summand telescopes to
$q^{e_{k+1}+\dots+e_m} - q^n$
and the right summand telescopes to
$1 - q^{e_{k+1}+\dots+e_m}$.


\begin{remark*}
  Technically, we could have skipped straight to the induction,
  without proving the first two claims.
  However I think the solution reads more naturally this way.
\end{remark*}