Bijective Function from N to N x N

Question

I have an idea but I don't know how to formalize my idea in a function. That's what n should give me back as (x,y):

n = 0 -> (0,0)
n = 1 -> (1,0)
n = 2 -> (0,1)
n = 3 -> (2,0)
n = 4 -> (1,1)
n = 5 -> (0,2)
n = 6 -> (3,0)
n = 7 -> (2,1)
n = 8 -> (1,2)
n = 9 -> (0,3)
n = 10 -> (4,0)

How do I formulate a function for this one? I also need one for N -> N x {1,...,n) but I think it's the same function, is it?

Answer 1

Each $n \in \mathbb N$ can be uniquely written as $n=m(m+1)/2 + j$ with $0 \le j \le m$, namely $m = \left\lfloor \dfrac{\sqrt{8n+1}-1}{2} \right\rfloor$. Then take $f(n) = (m-j,j)$.

It's simpler, though, to write the inverse function from $\mathbb N \times \mathbb N$ to $\mathbb N$:

$$ (i,j) \mapsto \frac{(i+j)(i+j+1)}{2}+j $$

Answer 2

There is an easier bijection between $\mathbb{N}$ and $\mathbb{N}\times\mathbb{N}$. If $n$ $\in$ $\mathbb{N}$, there is a unique pair $(x_n,y_n)$ $\in$ $\mathbb{N}\times\mathbb{N} $ such that $n = 2^{x_n-1}\cdot (2y_n - 1)$ (using fundamental theorem of arithmetic), defining the map

\begin{align*}F:&\mathbb{N}\rightarrow\mathbb{N}\times\mathbb{N}\\ &n\rightarrow (x_n,y_n) \end{align*} you get a bijection.