\( \newcommand{\P}[]{\unicode{xB6}} \newcommand{\AA}[]{\unicode{x212B}} \newcommand{\empty}[]{\emptyset} \newcommand{\O}[]{\emptyset} \newcommand{\Alpha}[]{Α} \newcommand{\Beta}[]{Β} \newcommand{\Epsilon}[]{Ε} \newcommand{\Iota}[]{Ι} \newcommand{\Kappa}[]{Κ} \newcommand{\Rho}[]{Ρ} \newcommand{\Tau}[]{Τ} \newcommand{\Zeta}[]{Ζ} \newcommand{\Mu}[]{\unicode{x039C}} \newcommand{\Chi}[]{Χ} \newcommand{\Eta}[]{\unicode{x0397}} \newcommand{\Nu}[]{\unicode{x039D}} \newcommand{\Omicron}[]{\unicode{x039F}} \DeclareMathOperator{\sgn}{sgn} \def\oiint{\mathop{\vcenter{\mathchoice{\huge\unicode{x222F}\,}{\unicode{x222F}}{\unicode{x222F}}{\unicode{x222F}}}\,}\nolimits} \def\oiiint{\mathop{\vcenter{\mathchoice{\huge\unicode{x2230}\,}{\unicode{x2230}}{\unicode{x2230}}{\unicode{x2230}}}\,}\nolimits} \)

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:
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} \]