Skip to main content
Added last sentence
Source Link
Neil Strickland
  • 56.9k
  • 7
  • 142
  • 262

One can give an explicit bijection $f_n:\mathbb{N}^n\to\mathbb{N}$. In the case $n=4$ it is $$ f_4(p,q,r,s) = \left(\begin{matrix} p+q+r+s+3 \\\\ 4\end{matrix}\right)+ \left(\begin{matrix} p+q+r+2 \\\\ 3\end{matrix}\right)+ \left(\begin{matrix} p+q+1 \\\\ 2\end{matrix}\right)+p $$ The general case follows the obvious pattern. We can order $\mathbb{N}^n$ as follows: if $a_1+\dotsb+a_n\lt b_1+\dotsb+b_n$ we declare that $a\lt b$, but if we have a tie according to this test then we instead compare $a_1+\dotsb+a_{n-1}$ with $b_1+\dotsb+b_{n-1}$, and so on. Then $f_n(a)=|\{b\in\mathbb{N}^n:b \lt a\}|$. To find $f_4^{-1}(k)$ you first find the largest $u$ such that $\left(\begin{matrix}u+3\\\\ 4\end{matrix}\right)\leq k$, then the largest $v$ such that $\left(\begin{matrix}u+3\\\\ 4\end{matrix}\right)+ \left(\begin{matrix}v+2\\\\ 3\end{matrix}\right)\leq k$, and so on. This is not quite as good as a formula but at least it is a fairly straightforward algorithm. One can check that $f_4(p,q,r,s)<2^{64}$ provided that $p+q+r+s\lt 145053$, so 64 bit integers are enough for a reasonable range of values.

One can give an explicit bijection $f_n:\mathbb{N}^n\to\mathbb{N}$. In the case $n=4$ it is $$ f_4(p,q,r,s) = \left(\begin{matrix} p+q+r+s+3 \\\\ 4\end{matrix}\right)+ \left(\begin{matrix} p+q+r+2 \\\\ 3\end{matrix}\right)+ \left(\begin{matrix} p+q+1 \\\\ 2\end{matrix}\right)+p $$ The general case follows the obvious pattern. We can order $\mathbb{N}^n$ as follows: if $a_1+\dotsb+a_n\lt b_1+\dotsb+b_n$ we declare that $a\lt b$, but if we have a tie according to this test then we instead compare $a_1+\dotsb+a_{n-1}$ with $b_1+\dotsb+b_{n-1}$, and so on. Then $f_n(a)=|\{b\in\mathbb{N}^n:b \lt a\}|$. To find $f_4^{-1}(k)$ you first find the largest $u$ such that $\left(\begin{matrix}u+3\\\\ 4\end{matrix}\right)\leq k$, then the largest $v$ such that $\left(\begin{matrix}u+3\\\\ 4\end{matrix}\right)+ \left(\begin{matrix}v+2\\\\ 3\end{matrix}\right)\leq k$, and so on. This is not quite as good as a formula but at least it is a fairly straightforward algorithm.

One can give an explicit bijection $f_n:\mathbb{N}^n\to\mathbb{N}$. In the case $n=4$ it is $$ f_4(p,q,r,s) = \left(\begin{matrix} p+q+r+s+3 \\\\ 4\end{matrix}\right)+ \left(\begin{matrix} p+q+r+2 \\\\ 3\end{matrix}\right)+ \left(\begin{matrix} p+q+1 \\\\ 2\end{matrix}\right)+p $$ The general case follows the obvious pattern. We can order $\mathbb{N}^n$ as follows: if $a_1+\dotsb+a_n\lt b_1+\dotsb+b_n$ we declare that $a\lt b$, but if we have a tie according to this test then we instead compare $a_1+\dotsb+a_{n-1}$ with $b_1+\dotsb+b_{n-1}$, and so on. Then $f_n(a)=|\{b\in\mathbb{N}^n:b \lt a\}|$. To find $f_4^{-1}(k)$ you first find the largest $u$ such that $\left(\begin{matrix}u+3\\\\ 4\end{matrix}\right)\leq k$, then the largest $v$ such that $\left(\begin{matrix}u+3\\\\ 4\end{matrix}\right)+ \left(\begin{matrix}v+2\\\\ 3\end{matrix}\right)\leq k$, and so on. This is not quite as good as a formula but at least it is a fairly straightforward algorithm. One can check that $f_4(p,q,r,s)<2^{64}$ provided that $p+q+r+s\lt 145053$, so 64 bit integers are enough for a reasonable range of values.

Source Link
Neil Strickland
  • 56.9k
  • 7
  • 142
  • 262

One can give an explicit bijection $f_n:\mathbb{N}^n\to\mathbb{N}$. In the case $n=4$ it is $$ f_4(p,q,r,s) = \left(\begin{matrix} p+q+r+s+3 \\\\ 4\end{matrix}\right)+ \left(\begin{matrix} p+q+r+2 \\\\ 3\end{matrix}\right)+ \left(\begin{matrix} p+q+1 \\\\ 2\end{matrix}\right)+p $$ The general case follows the obvious pattern. We can order $\mathbb{N}^n$ as follows: if $a_1+\dotsb+a_n\lt b_1+\dotsb+b_n$ we declare that $a\lt b$, but if we have a tie according to this test then we instead compare $a_1+\dotsb+a_{n-1}$ with $b_1+\dotsb+b_{n-1}$, and so on. Then $f_n(a)=|\{b\in\mathbb{N}^n:b \lt a\}|$. To find $f_4^{-1}(k)$ you first find the largest $u$ such that $\left(\begin{matrix}u+3\\\\ 4\end{matrix}\right)\leq k$, then the largest $v$ such that $\left(\begin{matrix}u+3\\\\ 4\end{matrix}\right)+ \left(\begin{matrix}v+2\\\\ 3\end{matrix}\right)\leq k$, and so on. This is not quite as good as a formula but at least it is a fairly straightforward algorithm.