Explicit map from $\mathbb{N}^t \to \mathbb{N}$

221 Views Asked by At

I know how to proof the following map from $\mathbb{N}\times \mathbb{N} \to \mathbb{N}$ is injective :

$(n_1, n_2) \to \binom{n_{1}+n_{2}} 2 + n_{1}$.

An obvious generalization of the above map from $\mathbb{N^t} \to \mathbb{N} $ seem like as follows:

$(n_1, \dots, n_t) \to \sum_{j = 1}^t \binom{\sum_{i = 1}^j n_i} j$.

I have a feeling that this generalized map from $\mathbb{N^t} \to \mathbb{N} $ is also injective. But I don't know how to prove it. Geometrically it seems very difficult as compared to the proof for the case $t=2$. I think there should be some algebraic proof. A rough sketch of the proof or any suitable reference book where I can read proof for this general case will be a great help.

2

There are 2 best solutions below

1
On BEST ANSWER

This is connected to something called Combinatorial number system (also combinadics), which states that for a fixed integer $t>0$, every integer $k\geq 0$ can be uniquely(!) represented as $$ k=\binom{c_1}{1}+\binom{c_2}{2}+\dots+\binom{c_t}{t} $$ where $c_t>\dots>c_2>c_1\geq 0$ are integers. If we let $c_j=\sum_{i = 1}^j n_i$ in your problem, the condition above is satisfied, so we can use the uniqueness of combinadics representation of above to show injectivity. To see it better let's denote $$ f(n_1,n_2,\dots,n_t)=\binom{n_1}{1}+\binom{n_1+n_2}{2}+\dots+\binom{n_1+n_2+\dots+n_t}{t}, $$ and assume $f(a_1,a_2,\dots,a_t)=f(b_1,b_2,\dots,b_t)$ for some positive integers $a_i,b_i$. Then letting $c_j=\sum_{i = 1}^j a_i$ and $d_j=\sum_{i = 1}^j b_i$, and so $\binom{c_1}{1}+\binom{c_2}{2}+\dots+\binom{c_t}{t}=\binom{d_1}{1}+\binom{d_2}{2}+\dots+\binom{d_t}{t}$. By the uniqueness of combinadics representation, it follows $c_j=d_j$ for all $j$, which implies $a_i=b_i$ subsequently, and injectivity follows.

However $f$ will not be surjective because $n_i$ are positive and so $c_1 = n_1 \neq 0$, thus we miss values whose representation would have $c_1=0$ in the combinadics representation. Since you map to positive integers, you are allowed to ommit $0$, but that is the only one value you don't need to map to... For example, for any $t>1$, the integer $\binom{0}{1}+\binom{2}{2}+\dots +\binom{t}{t}=0+1+\dots +1=t-1$ will not be represented by your map.

So for completeness, check a proof of uniqueness of combinadics system, see for example Numbers Expressed as Sums of Binomial Coefficients, or Proof of bijection for combinatorial number system (you can find many more by yourself now).

By the way, you can use the above to turn the combinadics into an explicit bijection $g:\mathbb{N^t} \to \mathbb{N}$ (where $\mathbb{N}$ excludes $0$). The condition $c_t>\dots>c_2>c_1\geq 0$ corresponds to sums of $n_i$'s with $n_1\geq 0$ and $n_j >0$ for $j>1$. So, shifting $n_1$ and resulting value by $1$, we can see $$ g(n_1,n_2,\dots,n_t)=\binom{n_1-1}{1}+\binom{n_1+n_2-1}{2}+\dots+\binom{n_1+\dots+n_t-1}{t}+1 $$ is such bijection.

0
On

You can construct an injective map $\Bbb{N}^t \to \Bbb{N}$ via the map $(n_1, ..., n_t) \to p_1^{n_1} ... p_t^{n_t}$, where $p_i$ is the $i$th prime number. In fact, by the Fundamental Theorem of Arithmetic, this extends to a bijection of $$S := \bigcup_{t \geq 1} \Bbb{N}^t \leftrightarrow \{2, 3, 4, 5, ...\}.$$