# 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 '13 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 '13 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 '13 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 '13 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 '13 at 23:40

The bijection $\Psi_k$ provided by the OP is actually not very different from my other (first) answer. My proposed bijection is

\begin{align*} (x_1,\dots,x_n)\in\mathbb N^n\mapsto&\,\binom{n-1+\sum_{r=1}^nx_r}{n}+\sum_{i=1}^{n-1}\binom{n-1-i+\sum_{r=i+1}^nx_r}{n-i}\\ =&\,\sum_{i=0}^{n-1}\binom{n-1-i+\sum_{r=i+1}^nx_r}{n-i}\,. \end{align*}

Using the fact that $\sum_{i=0}^{n-1}a_i=\sum_{i=0}^{n-1}a_{n-1-i}$ (in the second sum we are summing from the last to the first summand of the original sum) we can rewrite the bijection above as

\begin{align*} \sum_{i=0}^{n-1}\binom{n-1-(n-1-i)+\sum_{r=(n-1-i)+1}^nx_r}{n-(n-1-i)}=&\,\sum_{i=0}^{n-1}\binom{i+\sum_{r=n-i}^nx_r}{i+1}\\ =&\,\sum_{i=1}^n\binom{i-1+\sum_{r=n-i+1}^nx_r}{i}\,. \end{align*}

Now consider the mapping $(y_1,\dots,y_n)\in\mathbb N^n\mapsto(y_n,y_{n-1},\dots,y_1)$, that is, we change each entry $y_r$ by $y_{n+1-r}$. This is evidently a bijection from $\mathbb N^n$ to itself. Composing this map with the map above we obtain

\begin{align*} (x_1,\dots,x_n)\in\mathbb N^n\mapsto&\,\sum_{i=1}^n\binom{i-1+\sum_{r=n-i+1}^nx_{n+1-r}}{i}\\ =&\,\sum_{i=1}^n\binom{i-1+x_1+\cdots+x_i}{i}\,, \end{align*}

which is precisely equal to $\Psi_n(x_1,\dots,x_n)$.

Here is a modified and refined version of the second argument in my other answer. I include some motivation for the definition of the bijection, as well as a reasonably complete proof which, in my opinion, avoids cumbersome calculations.

For brevity we will write $[m]=\{1,\dots,m\}, \mathbf x=(x_1,\dots,x_n)\in\mathbb N^n$ and $|\mathbf x|=x_1+\cdots+x_n$. Consider the following relation $<$ in $\mathbb N^n$: we declare $\mathbf y<\mathbf x$ if $|\mathbf y|<|\mathbf x|$, or if $|\mathbf y|=|\mathbf x|$ and for some $i$ with $1\leq i\leq n-1$ we have $y_r=x_r$ for $r>i+1$ but $y_{i+1}>x_{i+1}$. You can verify that this defines a well-ordering such that every element has only a finite number of predecessors (Hint: if $|\mathbf y|=|\mathbf x|$ and $y_r=x_r$ for all $r\geq2$, then necessarily $\mathbf y=\mathbf x$, so if $\mathbf y\neq\mathbf x$ but $|\mathbf y|=|\mathbf x|$ then $\max\{j: y_j\ne x_j\}=i+1$ with $1\leq i\leq n-1$). In particular, the mapping $f:\mathbb N\to\mathbb N$ given by $f(\mathbf x)=$ the number of predecessors of $\mathbf x$, is a bijection from $\mathbb N^n$ onto $\mathbb N$.

Let $\mathbf x$ be fixed. To each $\mathbf y$ with $|\mathbf y|<|\mathbf x|$ we associate the strictly increasing sequence $\bigl(j+\sum_{t=1}^jy_t\bigr)_{j=1}^n\subseteq[n-1+x_1+\cdots+x_n]$, and this defines a bijection between the sets of such tuples $\mathbf y$ and the set of $n$-subsets of $[n-1+x_1+\cdots+x_n]$, which has $\binom{n-1+x_1+\cdots+x_n}{n}$ elements. Similarly, for $i=1,\dots,n-1$, to each $\mathbf y$ satisfying $|\mathbf y|=|\mathbf x|, y_r=x_r$ for $r>i+1$ and $y_{i+1}>x_{i+1}$ we associate the strictly increasing sequence $\bigl[j+\sum_{t=1}^jy_t\bigr]_{j=1}^i\subseteq[i-1+x_1+\cdots+x_i]$, and this defines a bijection between the sets of such tuples $\mathbf y$ and the set of $i$-subsets of $[i-1+x_1+\cdots+x_i]$, which has $\binom{i-1+x_1+\cdots+x_i}{i}$ elements. It is not hard to show that for $i=1,\dots,n$ the $i$-th inverse mapping is given by

\begin{align*} \{c_1<\cdots<c_i\}\subseteq&\,[i-1+x_1+\cdots+x_i]\\[3mm] \mapsto&\,\bigl(\ c_1-1\ \boldsymbol,\ c_2-c_1-1\ \boldsymbol,\ c_3-c_2-1\ \boldsymbol,\ \dots\ \boldsymbol,\ c_i-c_{i-1}-1\ \boldsymbol,\\[3mm] &\,\underbrace{x_1+\cdots+x_{i+1}-c_i+i}_{(i+1)\text{-}\style{font-family:inherit;}{\text{th entry}}}\ \ \boldsymbol,\\[3mm] &\,x_{i+2}\ \boldsymbol,\ x_{i+3}\ \boldsymbol,\ \dots\ \boldsymbol,\ x_n\ \bigr)\in\mathbb N^n\,. \end{align*}

Therefore the number of predecessors of a tuple $\mathbf x$ is precisely $\sum_{i=1}^n\binom{i-1+x_1+\cdots+x_i}{i}\,.$

• ...those meddling MSE users! – Pedro Tamaroff Aug 20 '13 at 5:12
• @PeterTamaroff English is not my cradle tongue, so it is not clear to me whether or not you are referring to me when you say "meddling". Just for clarification: if you check more carefully the flame war above, you will perceive that at first I answered the question with the best of intentions, but the arrogant attitude of OP got me mad. – Matemáticos Chibchas Aug 20 '13 at 5:20
• Estaba haciendo un chiste: el OP quiere mantener las cosas misteriosas, pero ya dejaste en claro (+1) que no es tan misterioso ni complicado como quizá se pensaba, aunque de ninguna manera es trivial. De paso: agregué algo sobre los números de Bernoulli en tu prgunta, quiza te interesa. Creo que la fórmula cerrada es mejor atacarla usando funciones generatrices dobles, como $\dfrac{te^{tz}}{e^t-1}$ para los polinomios de Bernoulli, y ver como aparecen los numeros de Stirling alli. No es para nada imposible, pero requiere paciencia! – Pedro Tamaroff Aug 20 '13 at 5:30
• @PeterTamaroff Gracias Peter por responderme en español, pero creo que debemos retomar el inglés en los comentarios (en mi caso, inglés potencialmente plagado de burradas gramaticales) por una cuestión de respeto por los demás usuarios y por la regla (¿tácita?) en MSE sobre el inglés como lingua franca. I will check your addendum on Bernoulli numbers; by the way, a nice and systematic answer of yours!!! – Matemáticos Chibchas Aug 24 '13 at 23:37
• While this answer is fine, I think you should try to avoid mud-slinging. Also, an answer should not be a "commentary on the OP attitude}, but thankfully I think this answer is mostly mathematical. – Alex Becker Aug 25 '13 at 6:16

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+\ \style{font-family:inherit;}{\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}+\style{font-family:inherit;}{\text{something, whenever}}\ I\in S_k\\\ \style{font-family:inherit;}{\text{has exactly}}\ j\ \style{font-family:inherit;}{\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}+\style{font-family:inherit;}{\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}\}\,, \style{font-family:inherit;}{\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 '13 at 20:43
• @JoãoJúnior Well, we at MSE are anxious to see your really very simple formula. – Matemáticos Chibchas Jan 14 '13 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 '13 at 1:16

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. – John Dvorak Jan 14 '13 at 17:24
• @Martin then your function seems bijective and closed-form to me. – John Dvorak Jan 14 '13 at 17:29
• Is a piece-wise function considered to be a closed-form? – Git Gud Jan 14 '13 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 '13 at 17:38

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 '13 at 17:18
• @JoãoJúnior then substitute $k(n)$ and $j(n,k)$ into $\beta(n)$ to get an explicit formula. – John Dvorak Jan 14 '13 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 '13 at 17:21
• It is ugly as sin, however. – copper.hat Jan 14 '13 at 17:21
• Please DON'T repeat this ad nausuem : ) – Euler....IS_ALIVE Aug 25 '13 at 0:01

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 '13 at 1:09
• 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 '13 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. – Stephen May 21 '13 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. – Stephen May 21 '13 at 16:02
• @JoãoJúnior Probably you are the only one who thinks that the question was not "satisfactorily" answered, but at least the other solvers (me included) had the decency to justify their respective answers, unlike you that continue to bragging about your "really very simple" formula without further explanation. But don't worry, based on the referee's comments all of us can infer that your proof of the formula is, by contrast, not "really very simple" at all. – Matemáticos Chibchas Aug 20 '13 at 5:01

This answer is equivalent to the other answers, but uses a combinatorial trick to make it more intuitive.

We will assume $\mathbb N$ contains zero.

Let $X=\{(n_1,\dots,n_k)\in\mathbb N^k\mid n_1< n_2<\cdots<n_k\}$.

First show that $X$ has the same cardinality as $\mathbb N^k$ by defining the bijection and inverse:

$$f:\mathbb N^k\to X;\, (a_1,\dots,a_k)\mapsto (a_1,a_1+a_2+1,\dots,a_1+\cdots +a_k+{k-1})\\ g:X\to\mathbb N^k;\,(n_1,\dots,n_k)\mapsto(n_1,n_2-n_1-1,\dots,n_{k}-n_{k-1}-(k-1))$$

The key is that there is a nice combinatorial ordering of $X$, called "the squashed order," where $(n_1,\dots,n_k)<_s(m_1,\dots,m_k)$ if, for some $i=1,\dots,k$ $n_i<m_i$ and for all $j>i$, $n_j=m_j$.

The squashed order is nice because:

1. It is a total order: A partial order such that for any $x,y\in X$, either $x<_s y, y<_s x$ or $x=y$.
2. Every element $x\in X$ has only finitely many predecessors $y<_s x$.

From this, we see the number of predecessors is a unique index for each element of $X$. We also see every element of $X$ has a unique successor. There is always at least one $y>x$ and then we can total order the finite number of elements $z$ such that $x<z\leq y$ and find the least.) So this means our index is onto $\mathbb N$.

There is a formula for this index:

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

That's because the number of elements $(m_1,\dots,m_k)$ before $(n_1,\dots,n_k)$ where $i$ is the determining index is equal to the number of $i$-subsets of $\{0,\dots,n_i-1\}$.

But you don't really need to know the formula to prove that $X$ has a bijection with $\mathbb N$, rather, we only need the two properties above to show that the map: $X\to \mathbb N$ defined as:

$$x\mapsto \left|\left\{y\in X\mid y<_s x\right\}\right|$$

is one-to-one and onto.

The formula is just gravy.

Working it out, that formula is essentially the same as the other answers given above. The index of $(a_1,\dots,a_k)$ in $\mathbb N^k$ is the index of $(a_1,a_1+a_2+1,\dots,a_1+\cdots+a_k+(k-1))\in X$ in the squashed order, which is:

$$\sum_{i=1}^{k}\binom{a_1+\cdots +a_i+i-1}{i}$$