Does anyone know a closed-form expression for a bijection between $\mathbb{N}^k$ and $\mathbb{N}$?

Question

I want to publish an article and one of its results is a simple closed-form expression for a natural bijection between $\mathbb{N}^k$ and $\mathbb{N}$. I wish to know whether it is already known.

Answer 1

It's not really a closed form, but I hope it helps. Let $f_2:\mathbb N^2 \to \mathbb N$ be defined as $$f_2(n_1,n_2)=2^{n_1}(2n_2+1) - 1$$ It's clearly a bijection, because every positive integer $n$ can be expressed uniquely as $n=2^km$, where $m$ is odd integer. Now we can construct $f_3:\mathbb N^3\to\mathbb N$ as $$f_3(n_1,n_2,n_3)=f_2(n_1,f_2(n_2,n_3))$$ and for any $k\in\mathbb N$, $f_k:\mathbb N^k\to\mathbb N$ $$f_k(n_1,...,n_k)=f_{k-1}(n_1,...,n_{k-2},f_2(n_{k-1},n_k))$$ is a bijection.

Answer 2

It is well known.

Here is an ugly bijection between $\mathbb{N}\times \mathbb{N} $ and $ \mathbb{N}$.

If you let $k(n) = \left\lceil \frac{\sqrt{1+8n}-1}{2} \right\rceil$, and $j(n,k) = \frac{k (k+1)}{2}-n+1$, then $\beta:\mathbb{N} \rightarrow \mathbb{N}\times \mathbb{N}$ defined by $$\beta(n) = (j(n,k(n)), k(n)-j(n,k(n))+1)$$ is a bijection. The inverse $\beta^{-1}: \mathbb{N}\times \mathbb{N} \rightarrow \mathbb{N}$ is given by: $$ \beta^{-1}(j, l) = \frac{(l+j-1)(l+j)}{2}-j+1$$

To form a bijection between $\mathbb{N}^3$ and $ \mathbb{N} $, consider the function $(n_1,n_2,n_3) \to \beta^{-1}(n_1,\beta^{-1}(n_2,n_3))$. This can be repeated ad nauseum.

Answer 3

Here is my idea, forgive me if I am somewhat imprecise: We want to order all the $n$-tuples $I=(i_1,\dots,i_n)\in\mathbb N^n$. I am assuming $\boldsymbol{0\notin\mathbb{N}}$. For this we successively order the tuples in each one of the "shells" $S_k=\{I: \max i_j=k\}$. Note that $|S_k|=k^n-(k-1)^n$, so a possibility for our bijection $f:\mathbb N^n\to\mathbb N$ is $$f(I)=(k-1)^n+\ \text{something, whenever}\ I\in S_k\,.$$ Now look at the number of entries of $I$ equal to $k$, say $j$ with $1\leq j\leq n$. Suppose that all the tuples in $S_k$ with less than $j$ entries equal to $k$ have been ordered. Note that for $1\leq r<j$ there are $\binom nr\,(k-1)^{n-r}$ tuples in $S_k$ with exactly $r$ entries equal to $k$. Thus, we can refine our formula to $$f(I)=(k-1)^n+\sum_{r=1}^{j-1}\binom nr\,(k-1)^{n-r}+\text{something, whenever}\ I\in S_k\ \text{has exactly}\ j\ \text{entries equal to}\ k\,.$$ It remains to order such tuples in some "decent" way. First we order the subsets of $\{1,\dots,n\}$ with $j$ elements. I did this when i was undergraduate (fond memories...), obtaining the following result: the mapping $\gamma$ that sends the $j$-subset $\{c_1<c_2<\cdots<c_j\}\subseteq\{1,\dots,n\}$ to the number $$1+\sum_{i=1}^j\binom{n-c_i}{j-i+1}$$ is a bijection onto the set $\{1,2,\dots,\binom nj\}$. As before, we assume that the "previous" tuples have been numbered. More precisely: denoting by $F_I$ the set $\{\ell: i_\ell=k\}$ we assume that all tuples $J\in S_k$ with $|F_J|=j$ and $F_J<F_I$ according to the ordering above have been numbered. There are $\gamma(F_I)-1$ subsets of $\{1,\dots,n\}$ of size $j$, each one "generating" $(k-1)^{n-j}$ "previous" tuples. Therefore we have $$f(I)=(k-1)^n+\sum_{r=1}^{j-1}\binom nr\,(k-1)^{n-r}+\bigl(\gamma(F_I)-1\bigr)(k-1)^{n-j}+\text{something, whenever}\ I \cdots$$ Last stage: consider the entries of $I$ that are strictly less than $k$, and order them, say, by lexicographical order. I strongly believe that this can be done via a explicit formula, but I am tired.

Of course, this is not a closed-form analytic formula, because you need to specify $k=\max\{i_1,\dots,i_n\}$ and $F_I=\{c_1<c_2<\cdots<c_j\}$. If this don't bother you, then this is your formula (modulo fill in the details).

EDIT

Inspired by the very constructive commentary from OP, here we go again. The shells in the previous answer are actually "spheres" in the $\ell_\infty$ metric. What about the $\ell_1$ metric?

This time we assume $0\in\mathbb N$. As you can guess, this time we will order the tuples according to its $\ell_1$ norm. Given $r\in\mathbb N$, each solution $x=(x_1,\dots,x_n)\in\mathbb N^n$ of the equation $x_1+\cdots+x_n=r$ give rise to the following subset $S(x)$ of $\{1,\dots,r+n-1\}$: $$S(x)=\{c_1<c_2<\cdots<c_{n-1}\}\,, \text{where}\ c_j=j+\sum_{i=1}^jx_i\,.$$ It is easy to see that this mapping defines a bijection onto the set of $(n-1)$-subsets of $\{1,\dots,r+n-1\}$, which obviously has $\binom{r+n-1}{n-1}$ elements. As in my previous solution, we use an explicit numbering of such subsets, namely, we associate to the subset $\{c_1<\cdots<c_{n-1}\}$ the number $\sum_{i=1}^{n-1}\binom{r+n-1-c_i}{n-i}$. Finally, given any tuple $I\in\mathbb N$ and defining $k=\|I\|_1$, we number the "previous" tuples, that is, those tuples $J$ with $\|J\|_1<k$. There are $\sum_{r=0}^{k-1}\binom{r+n-1}{n-1}=\binom{k+n-1}{n}$ such tuples. Thus, our bijection can be written explicitly (modulo abbreviations) as $$(x_1,\dots,x_n)\in\mathbb N^n\mapsto\binom{k+n-1}{n}+\sum_{i=1}^{n-1}\binom{k+n-1-c_i}{n-i}\,,$$ where $k=x_1+\cdots+x_n$ and $c_j=j+\sum_{i=1}^jx_i\,.$

Answer 4

Unfortunately, my manuscript was rejected by the American Mathematical Monthly. They said the following:

"The paper concentrates on the explicit construction of a bijection between $\bf N\times N$ and $\bf N$ and similar bijections for ${\bf N}^k$. However, for me it is quite unclear what is the intended audience and what is the main point of the paper. An explicit polynomial formula for the bijection indeed is nice, but it is definitely not new (I have seen it in logical textbooks). If the main point is a nice accessible explanation (for a wide audience) why this formula is true, it is possible, but the style of the paper with a lot of formulas is quite confusing and is not suitable for this goal.

So I am sorry to say that IMHO this paper does not look suitable for AMM (and, probably, for other journals I can think of)..."

So, as I have promised, I came back here to present you my formula:

$$\Psi_k(n_1, \dots, n_k) = \sum_{i=1}^{k}\binom{i-1+n_1+\dots +n_i}{i}$$

I will still try to present my work in some colloquium, before revealing how I got this formula.