Ordering

Related to counting, countabiliy

Diagonal

The goal is to get formulas for the following:

Figure 1: \(\displaystyle \begin{bmatrix} 0 & 2& 5& 9&\\ 1 & 4& 8& &\\ 3 & 7& & &\\ 6 & & & &\\ \end{bmatrix} \)

This is a bijection to Figure 2 where y is shifted by x and the matrix is flipped upside down:

Figure 2: \(\displaystyle \begin{bmatrix} & & & &\\ & & 5& &\\ & 2& 4& &\\ 0 & 1 & 3& ... &\\ \end{bmatrix} \)

The is a 1-1 mapping \(\displaystyle \mathbb{Z}^2 \to \mathbb{Z}\).

We first derive the function from \(\displaystyle (x,y) \in \mathbb{Z}^2\) to \(\displaystyle z \in \mathbb{Z}\) as shown in Figure 2. Let \(\displaystyle (x,y)\) be the coordinates in \(\displaystyle \{(0,0), (1, 0), (1,1), ...\}\) which will map to \(\displaystyle \{0, 1, 2, ...\}\).
First note that \(\displaystyle \sum_{0}^{k}i = \frac{(k)(k+1)}{2}\). Thus the number of elements in columns \(\displaystyle 0, ..., x-1\) is \(\displaystyle (x)(x+1)/2\).
Thus our formula is \[ \begin{equation} z = \frac{x(x+1)}{2} + y \end{equation} \]

To calculate the inverse formula:
Given an integer \(\displaystyle z\), we want to find \(\displaystyle (x, y)\).
Inverting \(\displaystyle \frac{x(x+1)}{2}\), we get: \[ \begin{align} x &= \left\lfloor \frac{-1 + \sqrt{1+8z}}{2} \right\rfloor\\ y &= z - \frac{x(x+1)}{2} \end{align} \]

The formula is figure 1 is as follows: