Binomial identity for bijection $\mathbb N\times\mathbb N\to\mathbb N$

Question

In a book I'm currently reading it is said (without proof) that, for an enumeration $d$ of $\mathbb N\times\mathbb N$ defined by $$d(0)=(0,0),\ d(1)=(0,1),\ d(2)=(1,0),\ d(3)=(0,2),\ d(4)=(1,1),\ d(5)=(2,0),\ d(6)=(0,3),\ \cdots$$ the inverse function can be written as $$c(x,y)=\binom{x+y+1}2+x.$$ Out of curiosity, I was trying to find a combinatorial argumentation, but I haven't succeeded so far. Maybe one of you can help.

Answer 1

I largely agree with Lance Sackless in the comments, but there is a somewhat combinatorial interpretation of the formula related to the picture that he describes. For a fixed integer $k\ge 0$ there are $k+1$ integer lattice points on the line $x+y=k$. Pick any two of them, say $p=\langle x_0,y_0\rangle$ and $q=\langle x_1,y_1\rangle$, where $x_0<x_1$; these two points uniquely determine one integer lattice point in the triangle bounded by the axes and the line $x+y=k$, namely, the point $\langle x_0,y_1\rangle$ below $p$ and to the left of $q$. Each integer lattice point in that triangle can be specified in this way, so there are $\binom{k+1}2$ integer lattice points in that triangle.

Thus, if $p=\langle x,y\rangle$ is any integer lattice point on that line, there are $\binom{k+1}2=\binom{x+y+1}2$ integer lattice points in the triangle below it that get enumerated first, and it’s the $x$-th point on that line to be enumerated, since the enumeration along that line proceeds from (upper) left to (lower) right, so $p$ gets the number $\binom{x+y+1}2+x$.