Generalization of Cantor Pairing function to triples and n-tuples Is there a generalization for the Cantor Pairing function to (ordered) triples and ultimately to (ordered) n-tuples? It's however important that the there exists an inverse function: computing z from (w, x, y) and also computing w, x and y from z. In other words:


*

*project(w, x, y) = z

*unproject(z) = (w, x, y)


Thinking about it in terms of a three-/n-dimensional coordinate system it should be possible to generalize from ordered pairs to at least ordered triples and most probably also to ordered n-tuples. Is anyone aware of any resources (papers, books, websites...) where such a function is described?
 A: Let $\varphi_2:\omega\times\omega\to\omega$ be any explicit pairing function (e.g., the Cantor pairing function), and let $\psi_0:\omega\to\omega$ and $\psi_1:\omega\to\omega$ be explicit functions such that $\psi_i\big(\varphi_2(n_0,n_1)\big)=n_i$ for $i=0,1$. Define $\varphi_k$ for $k\ge 2$ recursively by letting
$$\varphi_{k+1}:\omega^{k+1}\to\omega:\langle n_0,\ldots,n_k\rangle\mapsto\varphi_2\big(n_0,\varphi_k(n_1,\ldots,n_k)\big)$$
for each $k\ge 2$. Clearly each $\varphi_k$ can be computed simply by iterating $\varphi_2$ $k$ times on suitable arguments.
For each $k\ge 2$ and $i<k$ there is a function $\psi_i^{(k)}:\omega\to\omega$ such that 
$$\psi_i^{(k)}\big(\varphi_k(n_0,\ldots,n_{k-1})\big)=n_k$$
for $i<k$. These are easily described in terms of $\psi_0$ and $\psi_1$:
$$\psi_i^{(k)}(n)=\big(\psi_0\circ\psi_1^i\big)(n)$$
for each $n\in\omega$, where $\psi_1^i=\underbrace{\psi_1\circ\ldots\circ\psi_1}_{i\text{ copies}}$. (Of course $\psi_1^0$ is the identity function.)
Thus, given code for $\varphi_2$, $\psi_0$, and $\psi_1$, you can easily write code for $\varphi_k$ for all $k\ge 2$, and for $\psi_i^{(i)}$ for all $k\ge 2$ and $i<k$. There’s no need to work out the messy algebra.
A: The solution, in retrospect, seems "obvious" but I was having a hard time grasping it until I understood an example.
The pairing function takes two numbers as input and returns one: $ \mathbb{N} \times \mathbb{N} \to \mathbb{N}$
So what do you do with, say, a 3-tuple? Pick 2 items, use the pairing function to turn that into 1. Now use the pairing function again to turn your two remaining items into 1.
More formally

In computability we are often forced to resort to dovetailing along 3, 4 or even more dimensions. We can define "higher pairing" functions recursively, by using two-dimensional pairing functions as a base case. Formally, we define the function $  <.,.,...,.>_n$, which pairs $n$ natural numbers recursively as follows:
$<>_0 = 0$ and $<x>_1 = x$,
$<x,y>_2 = <x,y>$,
$<x_1, ..., x_{n-1}, x_n>_n = <x_1, ..., <x_{n-1}, x_n>>_{n-1}$.

https://www.cs.upc.edu/~alvarez/calculabilitat/enumerabilitat.pdf
4-tuple example ( $ \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \to \mathbb{N} \times \mathbb{N} \times \mathbb{N} \to \mathbb{N} \times \mathbb{N} \to \mathbb{N} $ )
$$
a,b,c,d
$$
$$
a,b,(c,d)
$$
$$
a,b,e
$$
$$
a,(b,e)
$$
$$
a,f
$$
$$
(a,f)
$$
$$
g
$$
A: Ok, I think I got it. Your idea is to create recursive functions for both pair and unpair and simply "assemble" the results instead of computing them with an algebraic formula. Of course this works due to the nature of pairing function. If I have time I will add the code in here.
Just one more question: Assuming I actually knew the pairing function for, let's say, triples (or n-tuples). In terms of processing speed on a regular computer, do you think it would be faster than a recursive solution? I assume it would be, because recursion requires to repeatedly create an internal stack for each recursive function call, whereas a mathematical function would just be computed once. So, if it's really about getting the most out of your processor, it would be worth trying to find the algebraic solution to this problem.
A: As you gather on your last paragraph, it is indeed possible to generalize the construction of the Cantor Pairing function to $n$-tuples.
Representing each pair in $\mathbb{N}\times\mathbb{N}$ by its coordinates on $\mathbb{R}^{2}$, we may define the pairing function $f_{1}:\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}$ by sending the pair $(a,b)$ to the number of pairs before it as we move from the origin along the lines $x+y=k$, $k\in\{0,\ldots,a+b\}$ in the upward $y$-direction.
That is, we start counting $(0,0)$, then $(1,0)$, then $(0,1)$, and so on until we arrive at $(a,b)$. The line $x+y=0$ has exactly one pair, the line $x+y=1$ has exactly $2$ pairs and, in general, the line $x+y=k$, $k\in\{0,\ldots,a+b-1\}$ has $k+1$ pairs. Hence, there are $1+2+\cdots+(a+b)=\binom{a+b+1}{2}$ pairs before the line $x+y=a+b$ containing $(a,b)$. But there are exactly $b$ pairs before $(a,b)$ on this line. Thus,
$$f_{1}(a,b) = \binom{b}{1}+\binom{b+a+1}{2}.$$
The equation above gives the impression of being the beginning of how we will define a bijective function for $n$-tuples. Indeed, defining $f_{2}:\mathbb{N}\times\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}$ builds on the previous case: send $(a,b,c)$ to the number of triples before it as we move from the origin along the planes $x+y+z=k$, $k\in\{0,\ldots,a+b+c\}$, where within each hyperplane we count triples as we did for the previous case, i.e. moving upward in the $z$-direction along the lines $y+z=r$, $r\in\{0,\ldots,k\}$.
That is, we count the origin, which is the only triple on the plane $x+y+z=0$, then we move to the plane $x+y+z=1$, where we count first $(1,0,0)$, the only triple on the line $y+z=0$, then $(0,1,0)$ followed by $(0,0,1)$, which are the two triples on the line $y+z=1$, then we move to the plane $x+y+z=2$ and so on until we arrive at $(a,b,c)$. In general, the plane $x+y+z=k$, $k\in\{0,\ldots a+b+c-1\}$ will have $\binom{k+2}{2}$ triples. Therefore, there are
$$\sum_{i=0}^{a+b+c-1}\binom{i+2}{2}=\binom{a+b+c+2}{3}$$
triples before the plane $x+y+z=a+b+c$ containing $(a,b,c)$. But there are exactly $f_{1}(b,c)$ triples before $(a,b,c)$ on this plane. Thus,
$$f_{2}(a,b,c) = \binom{c}{1}+\binom{c+b+1}{2}+\binom{c+b+a+2}{3}.$$
In general, for $n\ge 2$ (clearly, $f_{0}=\rm{id}_{\mathbb{N}}$), a bijective function $f_{n-1}:\mathbb{N}\times\overset{n}{\cdots}\times\mathbb{N}\rightarrow\mathbb{N}$ is defined on $(a_{1},\ldots,a_{n})$ analogously by counting $n$-tuples within each level of each one of the hyperplanes $x_{1}+\cdots+x_{1}=k_{1}$, $k_{1}\in\{0,\ldots,(a_{1}+\cdots+a_{n}-1)\}$. That is, for all the codimension $2$ hyperplanes $x_{2}+\cdots+x_{1}=k_{2}$, $k_{2}\in\{0,\ldots k_{1}\}$ and within these for each of the codimension $3$ hyperplanes, and so on. This adds up to
$$\binom{a_{1}+\cdots+a_{n}+(n-1)}{n}$$
$n$-tuples. Finally, we count the $n$-tuples before $(a_{1},\ldots,a_{n})$ on the hyperplane $x_{1}+\cdots+x_{1}=a_{1}+\cdots+a_{n}$ containing $(a_{1},\ldots,a_{n})$. There are $f_{n-2}(a_{2},\ldots,a_{n})$ such $n$-tuples. Therefore,
$$f_{n-1}(a_{1},\ldots,a_{n})=f_{n-2}(a_{2},\ldots,a_{n})+\binom{a_{1}+\cdots+a_{n}+(n-1)}{n}.$$
The right hand side equals
$$\binom{a_{n}}{1}+\binom{a_{n}+a_{n-1}+1}{2}+\binom{a_{n}+a_{n-1}+a_{n-2}+2}{3}+\cdots+\binom{a_{n}+\cdots+a_{1}+(n-1)}{n}.$$
In summary, the function $h:\mathbb{N}\times\overset{n}{\cdots}\times\mathbb{N}\rightarrow\mathbb{N}$ you were looking for may be given by
$$h(a_{1},\ldots,a_{n})=\sum_{i=1}^{n}\binom{(i-1)+\sum_{j=0}^{i-1}a_{n-j}}{i}.$$
This will be the fastest type of such a function for your processor. For example, in the case $n=2$ the function $h$ is quadratic, and it is not difficult to show that it is "best" in the sense that there is no linear bijection $\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}$.
