2
$\begingroup$

I need some help proving the following function is one-to-one and onto for $\mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$.

$F(i, j) = {i + j - 1 \choose 2} + j$

I know you guys like to see some attempt at a problem but I honestly have no idea where to start. A naive attempt simply making $F(i, j) = F(n, m)$ seems like it will have way too many cases to prove and I'm not even sure if that will prove 1-1. Is the best approach to define some sort of function and show it is invertible?

$\endgroup$
  • $\begingroup$ Did you try proving it is one-one? $\endgroup$ – Jorge Fernández Hidalgo Feb 6 '14 at 2:17
  • $\begingroup$ Yes, thats where the $F(i, j) = F(n, m)$ comes into play. $\endgroup$ – John Feb 6 '14 at 2:19
  • $\begingroup$ By the way, this is Cantor's pairing function. Logicians use it to code finite sequences of numbers by single numbers. $\endgroup$ – Andrés E. Caicedo Feb 6 '14 at 3:04
  • $\begingroup$ proving surjectivity is actually quite fun, maybe you could read at [ juanmarqz.wordpress.com/2011/02/17/… ] $\endgroup$ – janmarqz Feb 6 '14 at 3:19
  • $\begingroup$ what's up @John? could you tell now what are $(i,j)$, positive integers, such that $F(i,j)=100,000$ for example? Kudos for your problem that made me sweat :D $\endgroup$ – janmarqz Feb 6 '14 at 15:39
5
$\begingroup$

You could start by listing the function values out in a grid. You might see something like the following:

$$ \begin{array}{cccccccccc} 1 & 3 & 6 & 10 & 15 & 21 & 28 & 36 & 45 & 55 \\ 2 & 5 & 9 & 14 & 20 & 27 & 35 & 44 & 54 & 65 \\ 4 & 8 & 13 & 19 & 26 & 34 & 43 & 53 & 64 & 76 \\ 7 & 12 & 18 & 25 & 33 & 42 & 52 & 63 & 75 & 88 \\ 11 & 17 & 24 & 32 & 41 & 51 & 62 & 74 & 87 & 101 \\ 16 & 23 & 31 & 40 & 50 & 61 & 73 & 86 & 100 & 115 \\ 22 & 30 & 39 & 49 & 60 & 72 & 85 & 99 & 114 & 130 \\ 29 & 38 & 48 & 59 & 71 & 84 & 98 & 113 & 129 & 146 \\ 37 & 47 & 58 & 70 & 83 & 97 & 112 & 128 & 145 & 163 \\ 46 & 57 & 69 & 82 & 96 & 111 & 127 & 144 & 162 & 181 \\ \end{array} $$

Now, can you explain that? One hint might be to look up triangular numbers.

$\endgroup$
  • $\begingroup$ I guess I'm tired or something but I still don't quite get where this is going. $\endgroup$ – John Feb 6 '14 at 2:26
  • 3
    $\begingroup$ Can you see the pattern in @Mark's table? If so then you could try two steps: (1) assuming the pattern continues, explain why $F$ is one-to-one and onto; (2) explain why the pattern does in fact continue. $\endgroup$ – David Feb 6 '14 at 2:31
0
$\begingroup$

I would like to point out I love Mark's answer. Triangular numbers are these ones. and they are of the form $\binom{n+1}{2}$

enter image description here

$\endgroup$
  • $\begingroup$ Does this help you? $\endgroup$ – Jorge Fernández Hidalgo Feb 6 '14 at 2:33
  • $\begingroup$ Would it be helpful to express the binomial coefficient in summation notation and then handle the cases where i + j - 1 < 2 separately? $\endgroup$ – John Feb 6 '14 at 2:37
  • $\begingroup$ yes, I believe that is another approach. $\endgroup$ – Jorge Fernández Hidalgo Feb 6 '14 at 2:38
  • $\begingroup$ Is it different than what you are trying to show me here? I see that the triangular numbers correspond to the expression I have but I'm unsure how it helps. $\endgroup$ – John Feb 6 '14 at 2:39
  • $\begingroup$ This is a visual proof $\endgroup$ – Jorge Fernández Hidalgo Feb 6 '14 at 2:41
0
$\begingroup$

Surjectivity of $F(i, j) = {i + j - 1 \choose 2} + j$.

Here it goes an algorithm to find for a given natural $\lambda$, a pair $(i,j)$ of natural numbers such that $F(i, j) = \lambda$:

For,

1) Find a couple $(1,m)$ such that $F(1,m)\approx\lambda$

2) Then you are lead to consider ${m\choose 2}+m\approx\lambda$ which is a quadratic $m^2+m-2\lambda\approx0$

3) Seek $m_+=\frac{-1+\sqrt{1+8\lambda}}{2}$

4) Verify that $F(1,\lfloor m_+\rfloor)\le\lambda$, where $\lfloor m_+\rfloor$ is the positive integer $\le$ than $m_+$.

5) Take $r=\lambda-F(1,\lfloor m_+\rfloor)$

6) Then $F(\lfloor m_+\rfloor+2-r,r)=\lambda$

Check the next exemplification:

Do you need $i,j\in{\Bbb{N}}$ such that $F(i,j)=308$?

-- Find the greatest solution for $m^2+m-616=0$:

-- this is $m_+=\frac{-1+\sqrt{1+2464}}{2}=24.3243...$

-- so $\lfloor m_+\rfloor=24$

-- then $F(1,24)={24\choose 2}+24=300$

-- so $r=8$

-- Then $F(18,8)={25\choose 2}+8=308$.

Injectivity of $F(i, j) = {i + j - 1 \choose 2} + j$.

(Pending)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.