Ordering: Difference between revisions
| (3 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
Related to counting, countabiliy | Related to counting, countabiliy. | ||
==Diagonal== | ==Diagonal== | ||
| Line 28: | Line 29: | ||
The is a 1-1 mapping <math>\mathbb{Z}^2 \to \mathbb{Z}</math>. | The is a 1-1 mapping <math>\mathbb{Z}^2 \to \mathbb{Z}</math>. | ||
We first derive the function from <math>\mathbb{Z}^2</math> to <math>\mathbb{ | We first derive the function from <math>(x,y) \in \mathbb{Z}^2</math> to <math>z \in \mathbb{Z}</math> as shown in Figure 2. | ||
Let <math>(x,y)</math> be the coordinates in <math>\{(0,0), (1, 0), (1,1), ...\}</math> which will map to <math>\ | Let <math>(x,y)</math> be the coordinates in <math>\{(0,0), (1, 0), (1,1), ...\}</math> which will map to <math>\{0, 1, 2, ...\}</math>. | ||
First note that <math>\sum_{0}^{k}i = \frac{(k)(k+1)}{2}</math>. | First note that <math>\sum_{0}^{k}i = \frac{(k)(k+1)}{2}</math>. | ||
Thus the number of elements in columns <math>0, ..., x-1</math> is <math>(x)(x+1)/2</math>. | Thus the number of elements in columns <math>0, ..., x-1</math> is <math>(x)(x+1)/2</math>. | ||
| Line 40: | Line 41: | ||
To calculate the inverse formula: | To calculate the inverse formula: | ||
Given an integer <math>z</math>, we want to find <math>(x, y)</math> | Given an integer <math>z</math>, we want to find <math>(x, y)</math>. | ||
Inverting <math>\frac{x(x+1)}{2}</math>, we get: | |||
<math display="block"> | |||
\begin{align} | |||
x &= \left\lfloor \frac{-1 + \sqrt{1+8z}}{2} \right\rfloor\\ | |||
y &= z - \frac{x(x+1)}{2} | |||
\end{align} | |||
</math> | |||
The formula is figure 1 is as follows: | 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: | |||
{{ hidden | Spherical Harmonics | | |||
For spherical harmonics, we have <math>0 \leq |m| \leq l</math>. | |||
<math display="block"> | |||
\begin{equation} | |||
z = l(l+1) + m | |||
\end{equation} | |||
</math> | |||
<math display="block"> | |||
\begin{align} | |||
l &= \left\lfloor \sqrt{z} \right\rfloor\\ | |||
m &= z - x^2- x | |||
\end{align} | |||
</math> | |||
}} | |||