Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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.

share|improve this question
    
Perhaps it's worth mentioning that this function is called Cantor pairing function. en.wikipedia.org/wiki/Pairing_function –  Martin Sleziak Jul 28 '11 at 10:54

4 Answers 4

up vote 3 down vote accepted

To weave all the way to $(m,n)$, you first have $m+n$ complete top-left to bottom-right passes, of which the first contains 1 point $(0,0)$, the second two points $(0,1)$ and $(1,0)$, ..., the $m+n$'th $m+n$ points $(0,m+n-1)$ to $(m+n-1,0)$, and then the $m+1$'th point on the next pass is $(m,n)$.

share|improve this answer

Looking at the diagram, the order is lexicographic, first in $m+n$, then in $m$. The motivation is that it is easy to see you get all the points of $\mathbb{N} \times \mathbb{N}$, so now you just need to figure out what $J(m,n)$ is.

share|improve this answer
    
But that's my question, I have no problem believing that the path gets all points of $\mathbb{N}\times\mathbb{N}$, but I can't figure out what $J(m,n)$ is. –  Hobbie Mar 28 '11 at 4:12
    
There is a triangle with side $(m+n)$ all filled up-that is $(m+n)(m+n+1)/2$ points before you start the down-right diagonal, which you travel $m+1$ steps on. So I would claim $J(m,n)=(m+n)(m+n+1)/2+m+1$, slightly different from yours. –  Ross Millikan Mar 28 '11 at 4:27

$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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.