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

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.

-
Well, I guess there is always brute-force iteration of the usual bijection from $\mathbb{N} \times \mathbb{N}$ to $\mathbb{N}$ ... – Peter Smith Jan 14 at 17:17
@StevenStadnicki Fixed $k$, I can give a simple explicit formula for a bijection between $\mathbb{N}^k$ and $\mathbb{N}$. – João Júnior Jan 14 at 17:27
There is a bit of a literature on this, sorry, no references. Smorynski has some stuff on this in Logical Number Theory I. (Incidentally, very nice book. Still hoping for Logical Number Theory II.) – André Nicolas Jan 14 at 18:03
Once your paper is published, please consider add a version of it in the Arxiv so we all can see your result – leo Jan 15 at 2:46
@JoãoJúnior have been pased a few months since you said your paper was almost done. Can you please share your knowledge with us? :-) – leo Mar 25 at 23:40
show 10 more comments

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.

-
It's not an explicit formula. – João Júnior Jan 14 at 17:18
@JoãoJúnior then substitute $k(n)$ and $j(n,k)$ into $\beta(n)$ to get an explicit formula. – Jan Dvorak Jan 14 at 17:20
I'm not sure what you mean. The formula for $\beta^{-1}$ is about as closed form as I can imagine? Extending to higher dimensions is pretty straightforward. – copper.hat Jan 14 at 17:21
It is ugly as sin, however. – copper.hat Jan 14 at 17:21
@copper.hat I never said it wasn't :-) – Jan Dvorak Jan 14 at 17:23

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.

-
 I can see the bijectivity, but what about $f_2^{-1}$? This one doesn't seem closed-form. – Jan Dvorak Jan 14 at 17:24 @Martin then your function seems bijective and closed-form to me. – Jan Dvorak Jan 14 at 17:29 Is a piece-wise function considered to be a closed-form? – Git Gud Jan 14 at 17:32 @Jan: if $f_2(n_1,n_2)=k$ then I can only say that $n_1=\max\{n\in\mathbb N:2^n |(k+1)\}$ and $n_2=\frac{k+1}{n_1}$ – Adam Jan 14 at 17:38

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\,.$

-
Something in your approach is present in mine. But yours is yet very different and somewhat more complicated than mine. My formula is really very simple. – João Júnior Jan 14 at 20:43
@JoãoJúnior Well, we at MSE are anxious to see your really very simple formula. – Matemáticos Chibchas Jan 14 at 20:55
I will be back with the formula and an abstract of my work whithin a term of one week PLUS the elapsed time until the editorial decision. – João Júnior Jan 15 at 1:16

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.

-
Elementary and well-known exercises are, of course, rejected by any journal of mathematics. Now you know it and hopefully never try this again. – Martin Brandenburg May 18 at 1:09
Don't feel bad - the AMM is extremely selective with its acceptances. At least now you know that the formula is already known. – Greg Martin May 18 at 2:35
Sorry, @MartinBrandenburg, but if it is so elementary and well-known, why hadn't anybody here satisfactorily answered my question? – João Júnior May 18 at 4:46
@GregMartin, It's not clear to me from the referee's comment whether this particular formula is known. Actually, if that were the principal reason for the rejection the ref. should have provided precise coordinates. My guess is that the paper was rejected as much for stylistic reasons as anything else. – Steve May 21 at 15:59
@MartinBrandenburg, That's unecessarily harsh, and IMO wrong---the AMM publishes plenty of things that are "elementary and well-known exercises". My opinion (for what it is worth) is that the result is not suitable for publication in any mathematics research journal, but a clean&efficient exposition might well have been suitable for publication in AMM. – Steve May 21 at 16:02