Ordering: Difference between revisions
Created page with "Related to counting, countabiliy ==Diagonal== The goal is to get formulas for the following: <math> \begin{bmatrix} 0 & 2& 5& 9&\\ 1 & 4& 8& &\\ 3 & 7& & &\\ 6 & & & &\\ \en..." |
|||
| Line 4: | Line 4: | ||
The goal is to get formulas for the following: | The goal is to get formulas for the following: | ||
Figure 1: | |||
<math> | <math> | ||
\begin{bmatrix} | \begin{bmatrix} | ||
| Line 13: | Line 14: | ||
</math> | </math> | ||
This | This is a bijection to Figure 2 where y is shifted by x and the matrix is flipped upside down: | ||
<math> | <math> | ||
\begin{bmatrix} | \begin{bmatrix} | ||
| Line 22: | Line 23: | ||
\end{bmatrix} | \end{bmatrix} | ||
</math> | </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{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>\({0, 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 our formula is <math>z = \frac{x(x+1)}{2} + y</math> | |||
To calculate the inverse formula: | |||
Given an integer <math>z</math>, we want to find <math>(x, y)</math> | |||
The formula is figure 1 is as follows: | |||
Revision as of 18:26, 26 May 2020
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:
\(\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 \mathbb{Z}^2\) to \(\displaystyle \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 \(\displaystyle z = \frac{x(x+1)}{2} + y\)
To calculate the inverse formula:
Given an integer \(\displaystyle z\), we want to find \(\displaystyle (x, y)\)
The formula is figure 1 is as follows: