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

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

Answer 2

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 3

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 4

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)$.

ADDENDUM

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

Answer 5

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.

Answer 6

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}$$