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.