Why this polynomial represents this figure?

Question

I'm trying to understand why this figure is represented by this polynomial expression:

My goal is to prove directly why cartesian product of natural numbers is equinumerous to the natural numbers. I've already checked to the first elements of $(m,n)$ and indeed this polynomial seems to represent this figure.

I'm having problems to see why this figure is represented by this polynomial expression.

Thanks

Answer 1

You can write it as $$ J(m,n)=T(m+n)+m $$ where $T(m+n)$ denotes the number of points in the triangle below the line $x+y=m+n$ equivalent to $y=-x+(m+n)$. Then $m$ counts how many steps we have taken away from the $y$-axis on that line. Here is an example:

---

Here $T(k)$ is a well known function returning the $k$-th triangular number: $$ \begin{align} T(k)&=0+1+...+k\\ &=\tfrac12[(0+k)+(1+k-1)+...+(k+0)]\\ &=\tfrac12k(k+1) \end{align} $$

---

BTW, the inverse function of $J(m,n)=i$ is $K(i)=(m(i),n(i))$ that can be described using $$ \begin{align} mn(i)&=\lfloor\tfrac12(\sqrt{1+8i}-1)\rfloor\\ m(i)&=i-T(mn(i))\\ n(i)&=mn(i)-m(i) \end{align} $$ which seems to be confirmed for $i=0,...,14$ by the following Wolfram|Alpha-computation.

Answer 2

Well, J(m,n) gives you the number at coordinates (m,n).
If you try the J(m,n) formula with a few sample values for (m,n) e.g. (3,0), (2,1), you will see it's quite obvious. If you want to really prove it, maybe you can try induction. Or, you can consider the fact that on the N-th diagonal (these with the arrows), you have exactly (N+1) numbers, and then construct the formula yourself.

Answer 3

The $k^{th}$ downward diagonal runs from $(k,0)$ to $(0,k)$ and traverses $k+1$ points. So the indices of the points on the vertical axis are $0,1,3,6\dots=0,0+1,0+1+2,0+1+2+3\cdots$, i.e. the triangular numbers $\frac12k(k+1)$.

To get to a point $(m,n)$, you move $m$ steps along the diagonal $k=m+n$, so that the index of this point is $\frac12k(k+1)+m=\frac12(n+m)(n+m+1)+m$.