Counting the number of inversions for the function $f(x+yp)=qx+y$ Let $p,q$, $(p\neq q)$ be odd primes. Define the function $f:\{0,1,\ldots,pq-1\}\to \{0,1,\ldots,pq-1\}$ by $f(x+yp)=qx+y$, where $x\in \{0,1,\ldots,p-1\}$ and $y\in\{0,1,\ldots,q-1\}$. How does one calculate the number of inversions for $f$?
A complete solution would be quite helpful.
 A: We will consider the case $p=3, q=5$ which is easy to draw.  Hopefully you agree the ideas generalize.  Consider these matrices:
$$
A = \begin{bmatrix}
0 & 1 & 2 & 3 & 4 \\
5 & 6 & 7 & 8 & 9 \\
10 & 11 & 12 & 13 & 14
\end{bmatrix},
\ \ \ \ \ \ \ \ \ \ \ \ \
B = \begin{bmatrix}
0 & 3 & 6 & 9 & 12 \\
1 & 4 & 7 & 10 & 13 \\
2 & 5 & 8 & 11 & 14
\end{bmatrix}
$$
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 \mathbb{Z}_{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 \mathbb{Z}_{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 = \begin{bmatrix}
\color{red}{0} & \color{red}{1} & \color{red}{2} & \color{red}{3} & \color{red}{4} \\
\color{red}{5} & \color{blue}{6} & 7 & 8 & 9 \\
10 & 11 & 12 & 13 & 14
\end{bmatrix},
\ \ \ \ \ \ \ \ \ \ \ \ \
B = \begin{bmatrix}
0 & 3 & \color{red}{6} & \color{red}{9} & \color{red}{12} \\
1 & \color{blue}{4} & \color{red}{7} & \color{red}{10} & \color{red}{13} \\
2 & \color{red}{5} & \color{red}{8} & \color{red}{11} & \color{red}{14}
\end{bmatrix}
$$
E.g. $j=6 > i=4$ and $f(j) = f(0 + 2\cdot 3) = 5\cdot 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 2}{q \choose 2}$.
