Bijection between tetrahedron of side length $n$ and three objects from a list of length $n + 1$.

57 Views Asked by At

Jeremy Kun gives a canonical bijection between a triangle of side length $n$ and the ways to choose $2$ objects from a list of $n + 1$ objects:

Natural bijection from triangle number to n choose 2

Is there a similarly nice bijection between a tetrahedron of side length $n$ and choosing $3$ objects from a list of $n + 2$, both of which are the $n$th tetrahedral number $\binom{n + 2}{3}$.

Also, are there bijections to the $k$-simplex and ways to choose $k$ objects from a list of $n + k - 1$?

1

There are 1 best solutions below

0
On BEST ANSWER

One way to interpret the bijection in this picture is to say that the orange cell is specified by which positive-slope diagonal and which negative-slope diagonal of the triangle it's in.

But for generalizing to higher dimensions, a different system of coordinates is useful. In this picture, we can locate the orange cell by saying "It's $2$ steps away from the bottom, $2$ steps away from the left side of the triangle, and $1$ step away from the right side."

In general, any cell in the triangle can be given coordinates by saying "It's $x$ steps away from the bottom, $y$ steps away from the left side of the triangle, and $z$ steps away from the right side" for some integers $x, y, z \ge 0$ with $x+y+z = n-1$. There are $\binom{n+1}{2}$ ways to choose such $x$, $y$, and $z$. (This is no longer as obvious, but it follows from the well-known stars and bars method.)

A $k$-dimensional simplex has $k+1$ faces, and we can uniquely specify each cell of the simplex by saying "It's $x_0$ steps away from the $0^{\text{th}}$ face, $x_1$ steps away from the $1^{\text{st}}$ face, ..., $x_k$ steps away from the $k^{\text{th}}$ face." The coordinates of each cell are now integers $x_0, x_1, \dots, x_k \ge 0$ with $x_0 + x_1 + \dots + x_k = n-1$, and there are $\binom{n+k-1}{k}$ ways to find such a partition (again, by stars and bars).

This coordinate system, by the way, is nothing more than identifying the $k$-simplex with the subset $$\{(x_0, x_1, \dots, x_k) \in \mathbb R^{k+1} : x_0 + x_1 + \dots + x_k = n-1, x_0, x_1, \dots, x_k \ge 0\}$$ (a scaled version of the standard $k$-simplex) and identifying the cells inside it with the lattice points contained in the simplex.