Explicit Bijection from N to NxN

[phoenixthoth]

for this post, let N = {1, 2, 3, ...}.

Q: explicitly write down a closed form bijection with domain N and range N x N. (no need to prove its a bijection... just write down the formula.)


this may lead you off track, but the way i did it was to first find a formula from N x N to N and then invert it.
let (m, n) be an element of N x N and q = 1/2.
then the map is given by (m,n) |-> x, where
x = q m^2 +q n^2 + m n - q m - 3 q n + 1.
maybe I'm admitting how much i lack in algebra skillz by saying this, but i found it hard to invert this function... i did cheat and used mathematica to do the algebra i asked of it, but it didn't actually find the inverse by itself. i only used it to simplify expressions and isolate variables. i also used this site as a reference: http://www.research.att.com/~njas/sequences/ . thus i will say to you that no holds are barred; do it by any means necessary!

for double sums, we have something like this:
S = Sum[ f(m,n) , (m,n) ε NxN ].
if g is a bijection from N to NxN, we can straighten out this sum (assuming convergence of the original, we can add any way we please):
S = Sum[ f(g(x)), x ε N ], turning the double sum into a single sum. the catch is the formula for g ain't pretty so I'm not sure how useful this is... at least one can use single integral formulas to now estimate double sums and predict error although perhaps multivariable error estimates for double sums already exist (they probably do)...

i guess the next step is to find a bijection from N to NxNxN... i get an icky feeling all over when i think about that.

 

[phoenixthoth]

let g(x) = (m(x), n(x)) be the desired map from N to NxN.

let be the round function (rather than the usual greatest integer function).

then
m(x) = (2x + [SQRT(2x)] - [SQRT(2x)]^2)/2
n(x) = (2 - 2x + [SQRT(2x)] + [SQRT(2x)]^2)/2

for example, the 666th point in NxN is (36,1) and the millionth point is (1009, 406).

 

[tacman]

A: The explicit bijection from N to NxN is given by the formula f(n) = (n-1, floor((sqrt(8n-7)-1)/2)), where floor is the floor function. This function maps every natural number n to a unique pair (m,n) in NxN, where m and n are also natural numbers. This can be proven by showing that the function is injective and surjective.

To find the inverse function, we can use the formula g(m,n) = (1/2)((m+1)(m+2)+n), which maps every pair (m,n) in NxN to a unique natural number n. This inverse function can be proven by showing that it maps every element in NxN back to its original element in N.

This bijection can be extended to NxNxN by using the same method - finding a formula that maps every triple (m,n,p) in NxNxN to a unique natural number n. This can be achieved by using the formula h(m,n,p) = (1/6)((m+1)(m+2)(m+3)+n(m+1)(m+2)+p).

Overall, this shows that there is an explicit bijection from N to NxN and NxNxN, which can be used in various mathematical applications.