MacMahon gave a formula for the number of ways of tiling an a,b,c,a,b,c semiregular hexagon with unit rhombuses. One of the most direct and down-to-earth way of verifying the formula is the result of work done by Eric Kuo when he was an undergrad at MIT. Specifically, he found a simple combinatorial proof of the recurrence relation (*) T(a,b,c) * T(a,b-1,c-1) = T(a+1, b-1, c-1) * T(a-1, b, c) + T(a, b-1, c) * T(a, b, c-1) , where T(a,b,c) is the number of tilings of the a,b,c,a,b,c semiregular hexagon (from which MacMahon's formula follows easily by induction). (The method also gives proofs of the Mills-Robbins-Rumsey-Elkies-Kuperberg-Propp formula for Aztec diamonds (powers of 2), the Yang formulas for fortresses (powers of 5), the Ciucu formulas for dungeons (powers of 13), and many others.) Here is a modified version of Eric's posting on the subject from early this year, in which he illustrates his proof for the case (a,b,c) = (3,6,4). In reading it, you should keep in mind that Eric is really thinking of a lozenge tiling of a hexagon as a perfect matching of the dual graph; hence when he describes a face as being of degree one, he is referring to the associated vertex of the dual graph, and when he talks about "paths", he is talking about what you get when you superimpose two matchings of the graph. > We superimpose a matching of a 3,5,3-hexagon on top of a > 3,6,4-hexagon so that the triangles on only four of the sides > are degree one. In the following figure, the X's are the 3,5,3-hexagon > while the AVs are the rest of the 3,6,4-hexagon. > > 1 AVXXXXXXXXXXX > AVXXXXXXXXXXXXX > AVXXXXXXXXXXXXXXX > VAXXXXXXXXXXXXXXXA > VAXXXXXXXXXXXXXAV > VAXXXXXXXXXXXAV 4 > 2 VAVAVAVAVAVAV > 3 > > We then see two lattice paths connecting in one of two ways: > > (1) From side 1 to side 2, and from 3 to 4. We then partition the > matching to two submatchings, one for the 3,6,3, and the other for > the 3,5,4-hexagon. > > (2) From side 1 to side 4, and from 2 to 3. We partition the matching > to two submatchings, one for the 4,5,3, and the other for the 2,6,4. There's an extra wrinkle that comes from closed loops, each of which can be partitioned in 2 ways. Hence, Kuo's proof should not be seen as a bijective proof (although one could make it bijective by introducing some arbitrary symmetry-breaking conventions); rather, it's a way of pairing up families of "LHS-objects" with equal-sized families of "RHS-objects", where the size of a family is always a power of two.