# Bijective Function from N to N x N [duplicate]

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?

## marked as duplicate by Ross Millikan, Xander Henderson, trancelocation, user99914, StrantsMay 15 '18 at 13:02

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

• That looks very irritating for me. If I try it with n = 1, then I get m = 1 and j = 0, means f(n) = (1,0) which is true. But if I try it with n = 2, I need to take the root of 17. But that wouldn't result in a natural number for m. Where is my error? – CoreNoob May 15 '18 at 0:33
• @corenoob Note the floor operation – Bram28 May 15 '18 at 0:35
• @Bram28. Thanks. I'm such an idiot. How do you guys come up with such functions? I'm a c.s. student in the 2nd semester but I wouldn't be able to come up with the function above. – CoreNoob May 15 '18 at 0:39
• @CoreNoob The bijection you indicated is pretty standard, even as the actual function is a pain to figure out. My guess is Robert had this function laying around in his notes somewhere ... though it's possible he figured it out on the spot! – Bram28 May 15 '18 at 0:43

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.

• Thanks for this one. But that is N x N -> N and not N -> N x N, right? f(n) would be N -> N x N. – CoreNoob May 15 '18 at 0:51
• So you can use the inverse of $F$, $F^{-1} (n,m) = 2^{n-1} \cdot (2m - 1)$ – Matheus Manzatto May 15 '18 at 0:54
• If you are concerned about the domain of $F$, is correct, this map associates every natural $n$ $\in$ $\mathbb{N}$ to a pair $(x_n,y_n)$ $\in$ $\mathbb{N}\times \mathbb{N}$ – Matheus Manzatto May 15 '18 at 0:57
• What is the inverse function of f(n,m) = 2^(n-1) * (2m-1) ? – CoreNoob May 15 '18 at 1:07
• The inverse of $f$ is the function $F$ that I explain in my answer. Just observe that $F (f (n,m)) =(n,m)$ – Matheus Manzatto May 15 '18 at 1:09