# 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.

• "Inversions" are defined for a permutation of an ordered set; you need to define a total order on $\mathbb{Z}_{pq}$. I assume you really want the function $f : \left\{0,1,\ldots,pq-1\right\} \to \left\{0,1,\ldots,pq-1\right\}$ (not $f : \mathbb{Z}_{pq} \to \mathbb{Z}_{pq}$) that sends each $x + yp$ to $qx + y$ for $x \in \left\{0,1,\ldots,p-1\right\}$ and $y \in \left\{0,1,\ldots,q-1\right\}$. – darij grinberg Mar 23 at 5:10
• Note that it does not matter whether or not $p$ and $q$ are prime or distinct. A very similar (most likely equivalent, but I am too tired) problem has been posed as Exercise 3 in UMN Fall 2017 Math 4990 homework set #8 (the link goes to a PDF that sketches a solution and contains a link to another writeup with a solution). – darij grinberg Mar 23 at 5:12
• @darijgrinberg Yes. Appreciate the comments. Thank you :) – crskhr Mar 23 at 5:25

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}$$.