Bijective Function from N to N^2: Examples and Help

  • Thread starter Thread starter Anzewill
  • Start date Start date
AI Thread Summary
A bijective function from N to N^2 can be constructed by arranging natural numbers in a grid, where the cell at position (m,n) corresponds to the pair (m,n). The zigzag pattern starts at (1,1) and moves horizontally, then diagonally, covering all pairs systematically. An alternative formula for this function is (m,n) → 2^m(2n+1)-1. This approach ensures that every natural number is uniquely paired with a coordinate in N^2. The discussion highlights both a visual method and a mathematical formula for establishing the bijection.
Anzewill
Messages
1
Reaction score
0
Anyone can give me a example of a bijective fuction from N to N^2?
 
Physics news on Phys.org
I can't give you a simple "formula" but here is how to get a bijective function:

Write the numbers 1, 2, 3, ... horizontally and to left of "1" and slightly below write 1, 2, 3, ... vertically so that the cell below "m" and to the right of "n" is the pair (m,n). Now start at (1, 1) and "zigzag" through that array. That is, go from (1,1) horizontally to (2, 1) then diagonally, down and left, to (1,2), down to (1, 3), diagonally up and right to (2,3) and (3, 1), right to (4, 1), diagonally down to (3,2), etc.
 
Or for a simple formula try (m,n)\rightarrow 2^m(2n+1)-1.
 

Thread 'Finding the number of ways to arrange identical balls in a circle (3 different colors)'

I tried to combine those 2 formulas but it didn't work. I tried using another case where there are 2 red balls and 2 blue balls only so when combining the formula I got ##\frac{(4-1)!}{2!2!}=\frac{3}{2}## which does not make sense. Is there any formula to calculate cyclic permutation of identical objects or I have to do it by listing all the possibilities? Thanks
View full post »

Thread 'Making the denominator of a certain fraction real'

Essentially I just have this problem that I'm stuck on, on a sheet about complex numbers: Show that, for ##|r|<1,## $$1+r\cos(x)+r^2\cos(2x)+r^3\cos(3x)...=\frac{1-r\cos(x)}{1-2r\cos(x)+r^2}$$ My first thought was to express it as a geometric series, where the real part of the sum of the series would be the series you see above: $$1+re^{ix}+r^2e^{2ix}+r^3e^{3ix}...$$ The sum of this series is just: $$\frac{(re^{ix})^n-1}{re^{ix} - 1}$$ I'm having some trouble trying to figure out what to...
View full post »

Similar threads

Does there exist a surjection from the natural numbers to the reals?
Replies
4
Views
3K
Is my Proof Valid for Bijection of Finite Sets?
Replies
15
Views
3K
Where Did ##(n−r+1)^{th}## Come From in Binomial Expansion?
Replies
3
Views
1K
Find the ##r^{th}## term from beginning and end of ##(a+2x)^n##
Replies
13
Views
1K
Is f(m, n) = (m - n, n) a Bijective Function and What is its Inverse?
Replies
10
Views
3K
Prove every subset of countable set is either finite or else countable
Replies
1
Views
2K
Prove that if n^2 is a multiple of 2, then n is multiple of 2
Replies
23
Views
4K
Proving the Bijectivity of a Function: σ : Z_11 → Z_11 | Homework Solution
Replies
1
Views
1K
Express ##x^3+y^3## in terms of ##m## and ##n##
Replies
17
Views
3K
What Are the Combinatorial Possibilities of Glucose Polymers with n Monomers?
Replies
6
Views
1K

Hot Threads

Recent Insights

Back
Top