5,337
edits
Ordering: Difference between revisions
→Diagonal
(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: | |||