Fdtxjr

Let $p,q$, $(pneq q)$ be odd primes. Define the function $f:0,1,ldots,pq-1to 0,1,ldots,pq-1$ by $f(x+yp)=qx+y$, where $xin 0,1,ldots,p-1$ and $yin0,1,ldots,q-1$. How does one calculate the number of inversions for $f$?

A complete solution would be quite helpful.

We will consider the case $p=3, q=5$ which is easy to draw. Hopefully you agree the ideas generalize. Consider these matrices:

$$
A = beginbmatrix
0 & 1 & 2 & 3 & 4 \
5 & 6 & 7 & 8 & 9 \
10 & 11 & 12 & 13 & 14
endbmatrix,

B = beginbmatrix
0 & 3 & 6 & 9 & 12 \
1 & 4 & 7 & 10 & 13 \
2 & 5 & 8 & 11 & 14
endbmatrix
$$

Let the rows be numbered $x = 0, 1, 2$ from top to bottom and the columns be numbered $y = 0, 1, 2, 3, 4$ from left to right. Then $A_xy = qx+y$ and $B_xy = x+py$.

So here's a recipe for evaluating $f(i)$ where $i in mathbbZ_pq$:

• First, find location $(x,y)$ where $B_xy= i$




• Then, look up the same location in matrix $A$ and we have $f(i) = A_xy$.

If I may abuse notation a bit, the chain of mapping that just happened was something like this:

$$i = x+py = B_xy rightarrow (x,y) rightarrow A_xy = qx+y = f(i) = f(x+py)$$

which has an overall effect of $x + py rightarrow qx+y$ as desired.

OK, so how does this help? Consider $(i,j) in mathbbZ_pq^2$. It is an inversion if $i < j$ and $f(i) > f(j)$. Let their locations be $(x_i, y_i), (x_j, y_j)$, i.e. $i = x_i + p y_i = B_x_i y_i$ and $f(i) = q x_i + y_i = A_x_i y_i$, and similarly for $j$.

• From matrix $B$, it is obvious that $i = B_x_i y_i < j = B_x_j y_j$ iff $y_j > y_i$ ($j$'s column is to the right of $i$'s column), or, $y_j = y_i$ and $x_j > x_i$ ($j$ is in the same column and below $i$).




• From matrix $A$, similarly, $f(i) = A_x_i y_i > f(j) = A_x_j y_j$ iff $x_j < x_i$ ($j$'s row is above $i$'s row), or, $x_j = x_i$ and $y_j < y_i$ ($j$ is in same row and to the left of $i$).

Since we need both conditions above to be true, this means $(i,j)$ is an inversion iff $y_j > y_i$ and $x_j < x_i$, i.e. $(x_j, y_j)$ must be strictly to the right and above $(x_i, y_i)$.

E.g. in the following colored matrices, the blue cell represents $i=4, f(i) = f(1 + 1 cdot 3) = 5 cdot 1 + 1 = 6$. The red area in the $B$ matrix represents $j> i$ and the red area in the $A$ matrix represents $f(j) < f(i)$. Clearly the only overlap (for this choice of $i$) are the $3$ cells corresponding to $x=0, y=2,3,4$. These are the values of $j$ which form inversions with this choice of $i$.

$$
A = beginbmatrix
colorred0 & colorred1 & colorred2 & colorred3 & colorred4 \
colorred5 & colorblue6 & 7 & 8 & 9 \
10 & 11 & 12 & 13 & 14
endbmatrix,

B = beginbmatrix
0 & 3 & colorred6 & colorred9 & colorred12 \
1 & colorblue4 & colorred7 & colorred10 & colorred13 \
2 & colorred5 & colorred8 & colorred11 & colorred14
endbmatrix
$$

E.g. $j=6 > i=4$ and $f(j) = f(0 + 2cdot 3) = 5cdot 0 + 2 = 2 < f(i) = 6$.

So each $(i,j)$ pair that is an inversion is a pair of cells which form the top-right and bottom-left corners of a rectangle, where the rectangle has $c>1$ columns and $r>1$ rows. To count such rectangles, simply pick any $2$ distinct columns, and any $2$ distinct rows. So the final answer, i.e. the total number of inversion pairs, is $p choose 2q choose 2$.