The numbers $2^{n(n+1)/2}$ come up in various enumerative contexts. In addition to the trivial example (bit-strings of length $n(n+1)/2$) and the old example of domino tilings of Aztec diamonds (Elkies, Kuperberg, Larsen, and Propp: see <http://www.emis.de/journals/JACO/Volume1_2/x9m7n00g384067u3.fulltext.pdf> and <http://www.emis.de/journals/JACO/Volume1_3/r261p9652890q1j7.fulltext.pdf> ) and another old example involving order ideals in a tetrahedral poset (whose details I forget; perhaps someone can remind me), there are various other examples discussed in <http://arxiv.org/abs/1103.5054> (Nordenstam and Young) as well as the example discussed in <http://arxiv.org/abs/1312.5758> (Liu and Stanley).


I'm sure some of these are in direct canonical bijection (without one having to break symmetries or make arbitrary choices), but I suspect that the whole assortment of combinatorial models splits up into two or three distinct classes, where the bijections between the classes are non-canonical (cf. the original bijection between bit-strings and domino tilings of Aztec diamonds, which is non-canonical). And I'm sure the OEIS has a couple of avatars of the sequence 1,2,8,64,1024,... that I've missed.


Can we bring some order to this situation by showing which pairs of aforementioned classes of objects are in canonical bijection?


(Note to those with moderator powers: I'm on the fence as to whether or not this question should be a community wiki; I'll leave this to your judgment. Also note that I've attempted to use the tag "bijective-combinatorics", which doesn't seem to exist. If there's a tag already in use that means the same thing, feel free to change my tag appropriately.)



Two to the power of a triangular number: bijections
"Domino-shuffling on Novak Half-Hexagons and Aztec Half-Diamonds" by Nordenstam and Young (<http://arxiv.org/abs/1103.5054>) discusses the classes AD($n$) (domino tilings of Aztec diamonds), NILP($n$) (non-intersecting lattice paths), LT($n$) (lozenge tilings of trapezoids), HH($n$) (perfect matchings of the half hexagon), IPP($n$) (interlacing particle process), and ST($n$) (staircase tableaux). The authors provide bijections between NILP and LT (page 4), HH and LT (page 4), and IPP and ST (page 5). The original problem (asked by Novak) of finding a bijection between AD and HH remains open.


