MathDB

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

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.

Problem Statement