The binomial coefficients forming Pascal's triangle count, among other things, the number of lower sets in a two-dimensional rectangular grid. What about three-dimensional grids?

First, let's unpack that first sentence a little bit. The binomial coefficient \( \tbinom{n}{k} \) represents the number of subsets of \( k \) items that it's possible to choose out of any set of \( n \) items. Any subset can be represented as a \( k \)-tuple \( (a,b,c,\dots) \) where the \( k \) coordinates \( a \), \( b \), \( c \), etc., are in sorted order, unequal to each other, and all in the range from 1 to \( n \). As I noted earlier, the operations of coordinatewise minimum and maximum turn this collection of \( k \)-tuples into a distributive lattice, and Birkhoff's representation theorem tells us that this is the lattice of lower sets of some partial order. It turns out that this partial order is exactly a grid of size \( k \) by \( n-k \).

So this generalizes naturally enough to three dimensions: define a partial order from any three-dimensional grid, generate all lower sets of the partial order, and count how many sets are generated. The result should give us a pyramid of numbers, a three-dimensional analogue of Pascal's triangle. And we already know of something like that: Pascal's pyramid of multinomial coefficients, right?

Wrong! Here's the pyramid one gets from this process. The \( k \)th triangle in the pyramid shows the numbers of lower sets for \( a\times b\times c \) grids, where \( a+b+c=k \). It is not Pascal's pyramid, but something else.

   1

   1    1
   1

   1    1    1
   1    1
   1

   1    1    1    1
   1    2    1
   1    1
   1

   1    1    1    1    1
   1    3    3    1
   1    3    1
   1    1
   1

   1    1    1    1    1    1
   1    4    6    4    1
   1    6    6    1
   1    4    1
   1    1
   1

   1    1    1    1    1    1    1
   1    5   10   10    5    1
   1   10   20   10    1
   1   10   10    1
   1    5    1
   1    1
   1

   1    1    1    1    1    1    1    1
   1    6   15   20   15    6    1
   1   15   50   50   15    1
   1   20   50   20    1
   1   15   15    1
   1    6    1
   1    1
   1

   1    1    1    1    1    1    1    1    1
   1    7   21   35   35   21    7    1
   1   21  105  175  105   21    1
   1   35  175  175   35    1
   1   35  105   35    1
   1   21   21    1
   1    7    1
   1    1
   1

   1    1    1    1    1    1    1    1    1    1
   1    8   28   56   70   56   28    8    1
   1   28  196  490  490  196   28    1
   1   56  490  980  490   56    1
   1   70  490  490   70    1
   1   56  196   56    1
   1   28   28    1
   1    8    1
   1    1
   1

   1    1    1    1    1    1    1    1    1    1    1
   1    9   36   84  126  126   84   36    9    1
   1   36  336 1176 1764 1176  336   36    1
   1   84 1176 4116 4116 1176   84    1
   1  126 1764 4116 1764  126    1
   1  126 1176 1176  126    1
   1   84  336   84    1
   1   36   36    1
   1    9    1
   1    1
   1

Some slices of this pyramid are in OEIS as A001263, A008793, A056939, A056940, A056941, and A103905, though I didn't find the whole thing there. From A008793 I found a formula that generalizes to the full pyramid, though:

\[ L(a,b,c)=\prod_{i=0}^{a-1}\prod_{j=0}^{b-1}\prod_{k=0}^{c-1}\frac{i+j+k+2}{i+j+k+1} \]

I don't yet understand why it works, but computationally it matches the results of generating all lower sets and counting them, so I'm convinced it's right. (ETA: This formula can be found in math.CO/9906102. Apparently its proof goes back to MacMahon's 1916 book, Combinatory Analysis.)

One can also find a nice geometrical interpretation in A008793 and A103905: interpret a lower set in a grid as a subset of grid cubes near the origin, and look at the boundary of this set of cubes from a point of view far away along the main diagonal of the Cartesian coordinate system. The faces of the cubes look from this point of view like 60-120 rhombi, so (together with the unblocked sides of the grid on the coordinate planes) what you will see is a tiling of a hexagon by rhombi. Conversely one can translate any tiling of a hexagon by rhombi back into a lower set in this way. A008793 counts tilings in which all three hexagon sides are equal, while A103905 counts tilings in which two of the three sides are equal. The pyramid of numbers I'm considering here gives the number of rhombus tilings of hexagons in which all three sides may be unequal. Equivalently, it's the number of perfect matchings in a graph formed by partitioning the hexagon into equilateral triangles and connecting pairs of adjacent triangles.

(Formatted with the help of Andrey Burkov's TeXify web site, which I found via Ars Mathematica.)