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.)

  • 2
    $\begingroup$ Maybe you are thinking to Jessica Striker's work ? arxiv.org/abs/0905.4495 (it indeed involves order ideals and tournaments) $\endgroup$
    – F. C.
    May 25, 2014 at 18:55
  • 3
    $\begingroup$ "Can we bring some order to this situation?" Please formulate a proper question. While likely not a propblem in itself and isolation, such formulations from established users set a bad example. Also, you should use a top-level tag. $\endgroup$
    – user9072
    May 25, 2014 at 19:20
  • 2
    $\begingroup$ I think it means "Which pairs of these equinumerous objects are known to be in canonical bijection with each other?" $\endgroup$ May 25, 2014 at 19:50
  • 2
    $\begingroup$ I've reformulated my question as quid asked (along the lines I had in mind, as correctly guessed by Benjamin Young). Was quid's use of the word "propblem" a typo or a pun? :-) $\endgroup$ May 26, 2014 at 4:28
  • 1
    $\begingroup$ Thanks. It was a typo. I do not do such puns in general, but I do a lot of typos. $\endgroup$
    – user9072
    May 26, 2014 at 9:59

1 Answer 1


"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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.