# Homework Help: Find explicit bijection from N to N x N

1. Apr 27, 2010

### complexnumber

1. The problem statement, all variables and given/known data

Find a linear ordering of $$\mathbb{N} \times \mathbb{N}$$ and
use it to construct an explicit bijection $$f : \mathbb{N} \to \mathbb{N} \times \mathbb{N}$$.

2. Relevant equations

3. The attempt at a solution

I know how to find a bijection by graphically by drawing the $$\mathbb{N} \times \mathbb{N}$$ in a matrix and then traverse the elements diagonally. However, I cannot find a formula that maps an $$n$$ to a $$(x,y)$$ pair.

2. Apr 27, 2010

### hgfalling

Your idea about traversing the elements of the N X N matrix diagonally is good.

Now, we want to write down that idea in a formula form.

n=1:(1,1)
n=2:(1,2)
n=3:(2,1)
n=4:(1,3)
n=5:(2,2)
n=6:(3,1)

Now let's consider the pairs in the left column of the matrix, where the pair is (x,1). What pattern is there to these x-values: {1,3,6,10,15...}?
Next consider the pairs that make up a diagonal, for example {(1,3),(2,2),(3,1)}. What pattern is there in these?

Can you use those two patterns to write down an expression for the ordered pair that corresponds to a particular n value?

3. May 1, 2010

### complexnumber

Thanks for your reply. I found a bijection from $$\mathbb{N} \times \mathbb{N}$$ to $$\mathbb{N}$$ by
\begin{align*} n = \left(\sum^{x+y-2}_{k=1} k \right) + x \end{align*}

However, is this a bijection from $$\mathbb{N}$$ to $$\mathbb{N} \times \mathbb{N}$$ asked by the question? Given a $$n$$ I cannot use this equation to find a $$(x,y)$$ pair.