Explicit injective generalization of map $\mathbb{N}\times\mathbb{N}\to \mathbb{N}$

Question

I know a injective map from $\mathbb{N}\times \mathbb{N} \to \mathbb{N}$ given by the following explicit map:

$(m,n) \to \frac{(m+n)(m+n-1)}{2}+m$.

I am very curious to generalize it for $\mathbb{N^t} \to \mathbb{N} $

I know there is a recursive map from, $\mathbb{N^t} \to \mathbb{N} $, by using the map I have written from $\mathbb{N}\times \mathbb{N} \to \mathbb{N}$. But I am interested to find out an explicit injective map from, $ \mathbb{N^t} \to \mathbb{N} $, surjectivity is not necessary. Moreover, I do not want exponential maps. I am interested in a map that move as slow as possible.

Answer 1

With a second thought, I think it's not that complicated.

We define $f(n_1, \dots, n_t) = \sum_{j = 1}^t \binom{\sum_{i = 1}^j n_i} j$. This is a direct generalization of the $t = 2$ case given in the question.

It is "easy" to check that this map gives a bijection from $\Bbb N^t$ to $\Bbb N$.

Answer 2

Note that "as slow as possible" is ambiguous but I take it to mean a bijection between $\mathbb{N}^t$ and $\mathbb{N}$.

We can "cheat" and use an exponential map to create a bijection $f(a_1,a_2,...,a_t):\mathbb{N}^t\to\mathbb{N}$. Define

$$S=\left\{\prod_{i=1}^t p_i^{a_i}:(a_1,a_2,...,a_t)\in\mathbb{N}^t\right\}$$

Note that every element in $S$ is unique and that $S$ is a subset of $\mathbb{N}$. Thus, we can order every element of $S$ in a strictly increasing sequence. Thus, define $f(a_1,a_2,...,a_t)$ as the position in this strictly increasing sequence of $\prod_{i=1}^t p_i^{a_i}$. For example, if we define $\mathbb{N}=\{1,2,...\}$, then $f(1,1,...,1)=1$ for all $t$ (if we include $0$ in $\mathbb{N}$ then the smallest member of the sequence would clearly be the all zeros element). At this point, it is obvious that this function $f(a_1,a_2,...,a_t)$ is a bijection between $\mathbb{N}^t$ and $\mathbb{N}$ and that it grows as slowly as possible.