Question: When showing that $\mathbb{N}\times\mathbb{N}$ is in bijection with $\mathbb{N}$, it seems standard to give a proof by picture that shows a way to systematically weave through all the points in $\mathbb{N}\times\mathbb{N}$ and label each one as you go.

![enter image description here](https://i.stack.imgur.com/okCcv.png)

I know there is a polynomial expression for this method, given by $$
J(m,n)=[1+2+\cdots+(m+n)]+m=\frac{1}{2}[(m+n)^2+3m+n]
$$
where $m$ is the usual $x$-coordinate and $n$ the usual $y$-coordinate.

But how does one "see" how this formula is arrived at? I know how to manipulate the middle expression to arrive at the rightmost expression, but how does the middle expression relate to the weaving pattern through $\mathbb{N}\times\mathbb{N}$? Thank you.

Answer: 
$J(m,n)$ is just the number of points that are before $(m, n)$ in this order. These are the points $(x,y)$ with $x+y < m+n$, and the points $(x,y)$ with $x + y = m + n$ and $x < m$.

The first type of points can be broken down into those with $x+y = 0$ (of which there is $1$), those with $x+y = 1$ (of which there are $2$), and so on up to those with $x +y = m+n-1$, of which there are $m+n$. These are $(m+n-1, 0), (m+n-2, 1), \cdots, (0, m+n-1)$. So there are $1 + 2 + \cdots + (m+n)$ of these.

The second type are just the points $(0,n), (1,n-1), \cdots, (m-1, m+n-1)$. There are $m$ of these.

So the total number of points preceding $(m,n)$ in this order is 
$$ [1 + 2 + \cdots + (m+n)] + m $$
which is what you wanted.
Say $m$ is the column, $n$ is the row. You want to know how many points you have already counted by the time you get to $(m,n)$, using the picture.

If you go up $n$ rows, you will have counted the first $n$ diagonals in full (since the count starts with $0$). These give you $1+2+3+\cdots+n$ points, since the $n$th downward diagonal has $n$ points in it.

Now, each step you move to the right to get to $(m,n)$ will add another full diagonal that you must have already "added up". This will give you the diagonals with $n+1$, $n+2,\ldots,n+m$ points. This means that, counting only downward diagonals that you have completely counted, you have 
$$1 + 2 + 3 + \cdots + n + (n+1) + \cdots + (m+n) = \frac{(m+n)(m+n+1)}{2}$$
points.

In addition, you have some points in the diagonal you are *on* that have been counted. How many? One for each column you moved to the right; there are $m$ of those. So in addition to the points you already added, there are the first $m$ points on the diagonal you are on. So once you get to that point, you have counted
$$(1+2+3+\cdots+(n+m) + m = \frac{(m+n)(m+n+1)}{2}+m = \frac{1}{2}\left((m+n)^2+(m+n) + 2m\right)$$
points, which gives the formula.