The *Cantor bijection* given by
$$(x,y)\longmapsto {x+y\choose 2}-{x\choose 1}+1$$
is a bijection from $\{1,2,3,\dotsc\}^2$ onto $\{1,2,3,\dotsc\}$.


It can be generalized to bijections $\varphi\_d:\{1,2,3,\dotsc\}^d
\longrightarrow \{1,2,3,\dotsc\}$ given by
$$(x\_1,\dotsc,x\_d)\longmapsto (d+1\bmod 2)+(-1)^d\sum\_{k=1}^d(-1)^k{x\_1+\dotsb+x\_k\choose k}$$
where $(d+1\bmod 2)$ equals $1$ if $d$ is even and $0$ otherwise. (The proof is a sort of double induction on $d$ and on the sum $x\_1+x\_2+\dotsb+x\_d$.)


It is of course possible to consider compositions of the above formulæ in order to get additional, more complicated polynomial bijections.


A straightforward counting argument shows that we obtain in this way $d! s\_d$ different polynomial bijections between $\{1,2,\dotsc\}^d$ and $\{1,2,\dotsc\}$ where $s\_1,s\_2,\dotsc$
are the little Schroeder numbers with generating series
$$\sum\_{n=1}^\infty s\_nq^n=\frac{1+q-\sqrt{1-6q+q^2}}{4}\ .$$


Are there other "exotic" polynomial bijections (between $\{1,2,\dotsc\}^d\longrightarrow \{1,2,\dotsc\}$)?


(The answer is obviously "no" for $d=1$ and unknown for $d=2$.
I do not know if an "exotic" bijection is known for $d=3$.)


**Added for completeness:** Sketch of a proof that $\varphi\_d$ is a bijection:
We set
$$A\_d(n)=\{(x\_1,\ldots,x\_d)\in\{1,2,\ldots\}^d\ \vert\ x\_1+x\_2+\ldots+x\_d=n\}$$
and $A\_d(\leq n)=A\_d(d)\cup A\_d(d+1)\cup
\ldots\cup A\_d(n)$.


It is enough to prove that $\varphi\_d$
induces a bijection
between $A\_d(\leq n)$ and $\{1,\ldots,{n\choose d}\}$.


This is clearly true for $d=1$ (and arbitrary $n$) and for $n=d$ with arbitrary $d$.


Since $(x\_1,\ldots,x\_d)\longmapsto (x\_1,\ldots,x\_{d-1})$ is a bijection between $A\_d(n)$ and $A\_{d-1}(\leq n-1)$
we have (using slightly abusing notations for sets)
\begin{align\*}\varphi\_d(A\_d(n))&=
{n\choose d}-\left(\varphi\_{d-1}(A\_{d-1}(\leq n-1))-1\right)\\
&=\left\{{n\choose d}-{n-1\choose d-1}+1,\ldots,{n\choose d}\right\}\\
&=\left\{{n-1\choose d}+1,\ldots,{n\choose d}\right\}
\end{align\*}
which ends the proof of the induction step.



Are there exotic polynomial bijections from $\mathbb N^d$ onto $\mathbb N$?
[Wikipedia says](https://en.wikipedia.org/wiki/Fueter%E2%80%93P%C3%B3lya_theorem) "The generalization of the Cantor polynomial in higher dimensions" is $$(x\_1,\ldots,x\_n) \mapsto x\_1+\binom{x\_1+x\_2+1}{2}+\cdots+\binom{x\_1+\cdots +x\_n+n-1}{n}$$ Note that this is not equivalent to your generalisation $$(x\_1,\ldots,x\_d)\mapsto (d+1\bmod 2)+ \sum\_{k=1}^d(-1)^{k+d}{x\_1+\dotsb+x\_k\choose k}$$ so the word "*The*" is misleading. Lew, Morales, and Sánchez proved (*Diagonal polynomials for small dimension*, Math. Sys. Th. 29 (1996) 305–310) that these two families give the only "diagonal polynomials" up to permutation of variables for dimension 3, where a "diagonal polynomial" is a bijection $\mathbb{N}^d \to \mathbb{N}$ which orders all tuples satisfying $x\_1 + \cdots + x\_d = k$ before any tuple satisfying $x\_1 + \cdots + x\_d = k + 1$. In the same edition Morales and Lew gave $2^{d-2}$ inequivalent (i.e. not related by permutation of variables) diagonal polynomials for higher $d$ (*An enlarged family of packing polynomials on multidimensional lattices*, Math. Sys. Th. 29 (1996) 293-303).


In follow-up papers, Morales (*Diagonal polynomials and diagonal orders on multidimensional lattices*, Th. Comput. Sys. 30 (1997) 367–382) showed that this was an undercount, and in particular listed 6 inequivalent diagonal polynomials for $d=4$; and Sánchez described *A family of $(n-1)!$ diagonal polynomial orders of $\mathbb{N}^n$*, Order 12 (1997).


Fetter, Arredondo, and Morales proved in *The diagonal polynomials of dimension four*, Adv. Applied Math. 34 (2005) 316-334 that the six polynomials which Morales and Sánchez describe are all the diagonal polynomials of dimension 4 (up to permutation of variables). As far as I know it's an open question whether there are diagonal polynomials outside Sánchez's family for $d > 4$.


(Disclosure: I have not been able to read all of these papers, as I don't currently have access to a library with journal subscriptions, so I'm relying on the reports of the two I've found online).


I'm not sure to what extent these diagonal polynomials count as "exotic", but it is at least interesting to note that there's more than one per dimension, and this is far too long for a comment anyway.


