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:
Used in the proof of:
- The Cartesian product of two countable sets is countable
Variations:
- For spherical harmonics:
For spherical harmonics, we have \(\displaystyle 0 \leq |m| \leq l\).
\[ \begin{equation} z = l(l+1) + m \end{equation} \]
\[ \begin{align} l &= \left\lfloor \sqrt{z} \right\rfloor\\ m &= z - x^2- x \end{align} \]