1
$\begingroup$

I've been stuck for a couple of hours on how to prove that $C(m,n)=\frac{(m+n)(m+n+1)}{2}+m$ is a bijection from $\mathbb{N}^2$ to $\mathbb{N}$.

I read in another question that in order to prove that it is injective, you have to show: $$m+n<m'+n'\Rightarrow C(m,n)<C(m',n')$$

From where $C(m,n)=C(m',n')\Rightarrow m+n=m'+n'$, and then $m=m',n=n'$.

However, I failed to show the first implication, and I also couldn't understand how to go from $m+n=m'+n'$ to $m=m',n=n'$.

Would someone be kind enough to give me some tips on how to proceed?

$\endgroup$
  • $\begingroup$ Are you using $\mathbb{N}$ to represent the nonnegative integers? $\endgroup$ – user84413 Jul 17 '15 at 18:09
  • $\begingroup$ This is false: $C(0,m+1)=C(m,0)$ for all $m=0,1,2,\ldots$. $\endgroup$ – Batominovski Jul 17 '15 at 19:06
  • $\begingroup$ @user84413 Yes, $\mathbb{N}=\{0,1,2,3,\cdots\}$. There's an equivalent function if you want $\mathbb{N}=\{1,2,3,\cdots\}$, in fact, I think it is $f(x,y)=\frac{(x+y-1)(x+y-2)}{2}+x$. In any case, there's a natural bijection between $\{0,1,2,\cdots\}$ and $\{1,2,3,\cdots\}$. $\endgroup$ – Guilherme Salomé Jul 17 '15 at 19:14
  • $\begingroup$ @Batominovski Please correct me if I am wrong, but $C(0,m+1)=\frac{(m+1)(m+2)}{2}$, while $C(m,0)=\frac{m(m+1)}{2}+m=\frac{m(m+3)}{2}$, so they are different. If you meant to say $f$ instead of $C$, then you are probably right, but remember that $f$ was an example for when $0$ is not considered a natural number. $\endgroup$ – Guilherme Salomé Jul 17 '15 at 19:18
  • 1
    $\begingroup$ This question and answer may also be helpful. $\endgroup$ – Brian M. Scott Jul 17 '15 at 21:12
2
$\begingroup$

For the first implication, notice that $$ C(m,n) = m + \sum_{k=0}^{m+n} k$$ If $m+n < m' + n'$, this implies that \begin{align} C(m',n') - C(m,n) &= m' - m + \sum_{k=m+n+1}^{m'+n'} k \\ &\ge m' + n + 1 \end{align}

For the second implication, use the fact that $m = C(m,n) - \frac{(m+n)(m+n+1)}{2}$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The first equation is obtained by noticing that $0+1+2+\cdots +(m+n-1)+(m+n)=(m+n)\frac{(m+n+1)}{2}$, which is the summation of $\frac{(m+n+1)}{2}$ elements equal to $m+n$. $\endgroup$ – Guilherme Salomé Jul 17 '15 at 21:16

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