Return to Question

The so-called 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.

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.

The so-called 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)\\ &=\{{n\choose d}-{n-1\choose d-1}+1,\ldots,{n\choose d}\}\\ &=\{{n-1\choose d}+1,\ldots,{n\choose d}\} \end{align*} which ends the proof of the induction step.

The so-called 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.

The so-called 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 $\{1,2,3,\dotsc\}^d \longrightarrow \{1,2,3,\dotsc\}$ by considering $$(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$.)

The so-called 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)\\ &=\{{n\choose d}-{n-1\choose d-1}+1,\ldots,{n\choose d}\}\\ &=\{{n-1\choose d}+1,\ldots,{n\choose d}\} \end{align*} which ends the proof of the induction step.