## New Research In

### Physical Sciences

### Social Sciences

#### Featured Portals

#### Articles by Topic

### Biological Sciences

#### Featured Portals

#### Articles by Topic

- Agricultural Sciences
- Anthropology
- Applied Biological Sciences
- Biochemistry
- Biophysics and Computational Biology
- Cell Biology
- Developmental Biology
- Ecology
- Environmental Sciences
- Evolution
- Genetics
- Immunology and Inflammation
- Medical Sciences
- Microbiology
- Neuroscience
- Pharmacology
- Physiology
- Plant Biology
- Population Biology
- Psychological and Cognitive Sciences
- Sustainability Science
- Systems Biology

# A dual of MacMahon’s theorem on plane partitions

Edited by Richard P. Stanley, Massachusetts Institute of Technology, Cambridge, MA, and approved January 15, 2013 (received for review October 2, 2012)

## Abstract

A classical theorem of MacMahon states that the number of lozenge tilings of any centrally symmetric hexagon drawn on the triangular lattice is given by a beautifully simple product formula. In this paper, we present a counterpart of this formula, corresponding to the exterior of a concave hexagon obtained by turning 120° after drawing each side (MacMahon’s hexagon is obtained by turning 60° after each step).

## 1. Introduction

MacMahon’s classical theorem (1) on the number of plane partitions that fit in a given box [see refs. 2⇓⇓⇓–6 and the survey (7) for more recent developments] is equivalent to the fact that the number of lozenge* tilings of a hexagon of side lengths *a*, *b*, *c*, *a*, *b*, *c* (in cyclic order) on the triangular lattice is equal to

where the hyperfactorials H(*n*) are defined by

(see Fig. 1*A* for an example).

The hexagon is obtained by turning 60° after drawing each side. If after drawing each side, one instead turns 120° (the other natural amount of turning on the triangular lattice), one obtains a shape of the type illustrated in Fig. 1*B*; we call such a shape a “shamrock.”

Our results concern the exterior of a shamrock (as its interior has no lozenge tilings). Let *S*(*a*, *b*, *c*, *m*) be the shamrock whose central equilateral triangle has side length *m*, whereas its top, bottom left, and bottom right lobes are equilateral triangles of side lengths *a*, *b*, and *c*, respectively; denote its exterior by *S**(*a*, *b*, *c*, *m*).

We define the ratio of the number of tilings of the exteriors of the shamrocks *S*(*a*, *b*, *c*, *m*) and *S*(*a* + *b* + *c*, 0, 0, *m*) as follows: Let *H*_{N}(*a*, *b*, *c*, *m*) be the hexagonal region of side lengths alternating between *N + a + b + c* and *N* + *a* + *b* + *c* + *m* (the top side being *N* + *a* + *b* + *c*), and having the shamrock *S*(*a*, *b*, *c*, *m*) removed from its center [to be precise, *H*_{N}(*a*, *b*, *c*, *m*) is the region *SC*_{N,N,N}(*a*, *b*, *c*, *m*) described in the next section]. Then, we define

where for a lattice region *R*, *M*(*R*) denotes the number of lozenge tilings of *R*.

The dual MacMahon theorem we obtain in this paper is the following.

### Theorem 1.1.

*For any nonnegative integers a, b, c, and m we have*

*In the special case in which m = a + b + c, this may be written simply as*

Eq. **1.5** is illustrated geometrically in section 5 (see Fig. 9). Theorem 1.1 will follow as a consequence of a more general result (see Theorems 2.1 and 2.2), which we describe next.

## 2. Precise Statement of Results

The family of regions whose lozenge tilings we enumerate in this paper is a generalization of the following family, introduced in ref. 8. Consider hexagons of sides *x*, *y* + *m*, *z*, *x* + *m*, *y*, *z* + *m* (in clockwise order, starting from top), with an equilateral triangle of side *m* removed from its center (see Fig. 2 *A* and *B* for examples). This triangle is called the “core” and the leftover region, denoted *C*_{x,y,z}(*m*), a “cored hexagon.”

To define *C*_{x,y,z}(*m*) precisely, we need to specify what position of the core is the “central” one. Let *s* be a side of the core, and let *u* and *v* be the sides of the hexagon parallel to it. The most natural definition would require that the distance between *s* and *u* is the same as the distance between *v* and the vertex of the core opposite *s*, for all three choices of *s*.

However, because the sides of the core have to be along lines of the underlying triangular lattice, it is easy to see that this can be achieved only if *x*, *y*, and *z* have the same parity (Fig. 2*A* illustrates such a case); in that case, we define this to be the position of the core. On the other hand, if for instance *x* has parity different from that of *y* and *z*, the triangle satisfying the above requirements would have only one side along a lattice line, whereas each of the remaining two sides extends midway between two consecutive lattice lines (which may be seen in Fig. 2*B*). To resolve this, we translate this central triangle half a unit toward the side of the hexagon of length *y*, in a direction parallel to the side of length *x*, and define this to be the position of the core in this case (Fig. 2*B*).

The family of regions with which we are concerned in this paper is a generalization of cored hexagons, corresponding to the case in which the core is not just a triangle but a shamrock.

Given nonnegative integers *a*, *b*, and *c*, construct our region as follows: Start with the cored hexagon *C*_{x,y,z}(*m*), and “push out” the six lattice lines containing its sides as follows: the top, southwestern, and southeastern sides, *a*, *b*, and *c* units, respectively, and the bottom, northeastern, and northwestern sides, *b* + *c*, *a* + *c*, and *a* + *b* units, respectively. Also enlarge the core by adding to it down-pointing equilateral triangles of sides *a*, *b*, and *c* that touch the original core at its top, left, and right vertex, respectively. The hexagon formed by the pushed-out edges, with the enlarged, shamrock-shaped core taken out of it, is called an “*S*-cored hexagon” and is denoted by *SC*_{x,y,z}(*a*, *b*, *c*, *m*) (see Fig. 2 *C* and *D* for two examples; the dotted lines indicate the underlying cored hexagons).

The main result of this paper—from which Theorem 1.1 follows easily—is the exact enumeration of the lozenge tilings of *S*-cored hexagons. This is contained in the following two results. To state them, we extend the definition of hyperfactorials to half-integers (i.e., odd integers divided by 2), by setting, for *n* a positive half-integer, where Γ denotes the classical gamma function.

### Theorem 2.1.

*Let x, y, z, a, b, c, and m be nonnegative integers. If x, y, and z have the same parity, we have*

### Theorem 2.2.

*Let x, y, z, a, b, c, and m be nonnegative integers. If x has parity different from the parity of y and z, we have*

This represents a common generalization of MacMahon’s Eq. **1.1** and Theorem 1.1. It shows that if one regards the hexagon as being the right outer boundary to consider on the triangular lattice for the corresponding region to have a number of lozenge tilings given by a simple product formula, then a good inner boundary is the shamrock.

Note also that Theorems 2.1 and 2.2 generalize the main results of ref. 8, by introducing three additional parameters to the geometry of the core (the sizes of the three lobes of the shamrock). This results in a four-parameter generalization of MacMahon’s theorem (Eq. **1.1**).

## 3. Magnet Bar Regions

Our proof of Theorems 2.1 and 2.2 uses the exact enumeration of the following regions.

Let *x*, *y*, *a*, *b*, *c*, and *m* be nonnegative integers. Consider the hexagonal region with two removed equilateral triangles illustrated by Fig. 3, where the side lengths of the hexagon are, clockwise from top, *x* + *c*, *y* + *m*, *a* + *b* + *c*, *x* + *m*, *y* + *c*, and *a* + *b* + *m*, and the sides of the two removed triangles are *m* (for the triangle touching the northwestern hexagon side; note that the lengths of the portions of that side above and below this triangle are *a* and *b*, respectively) and *c* (for the central triangle; the four shaded unit triangles are relevant later). We call such a region a “magnet bar region” and denote it by *B*_{x,y}(*a*, *b*, *c*, *m*).

The main result of this section is the following.

### Theorem 3.1.

*For any nonnegative integers x, y, a, b, c, and m, we have*

** Proof:** The proof follows by induction on

*x*+

*y*+

*b*in the same style as the proof of Theorems 2.1 and 2.2, detailed in the next section. The base cases are the situations when

*x*= 0,

*y*= 0, or

*b*= 0. When

*b*= 0, the

*m*× (

*y*+

*c*) rhombus fitting in the bottom left corner of the magnet bar region is tiled by forced lozenges (Fig. 4

*A*), and the leftover region is one whose tilings are enumerated by a formula due to Cohn, Larsen, and Propp (see Proposition 2.1 in ref. 9). If

*x*= 0, the region looks as illustrated in Fig. 4

*B*, and the hexagonal subregions cut out by the dashed lines must be tiled internally (indeed, if a tiling had a lozenge like the one shown in gray, the path of tiles continuing up from it would have no place to end on the top side, as its entire length

*c*is required to accommodate the paths of tiles starting from the top side of the removed central triangle). Then, the number of tilings is the product of the number of tilings of the two hexagons, and Eq.

**3.1**follows by Eq.

**1.1**. The case

*y*= 0 follows similarly.

For the induction step, we apply Kuo’s graphical condensation (see Theorem 4.1) to the planar dual graph^{†} of *B*_{x,y}(*a*, *b*, *c*, *m*), with *v*_{1}, *v*_{2}, *v*_{3}, and *v*_{4} chosen to be the gray unit triangles in Fig. 3. As in the proof of Theorems 2.1 and 2.2 in the next section, because of forced lozenges, all five of the additional regions in the equality resulting from Eq. **4.1** are regions of the same kind, but with the sum of their *x*-, *y*-, and *b*-parameters strictly smaller. Explicitly, we obtain the recurrence

It is readily verified that the expression on the right-hand side of Eq. **3.1** also satisfies the above recurrence. This completes the proof.

## 4. Proof of Theorems 2.1 and 2.2

Our proof of Theorems 2.1 and 2.2 is based on the following special case of Kuo’s graphical condensation method:

### Theorem 4.1 [Kuo (10); Theorem 2.1].

*Let G = (V*_{1}*, V*_{2}*, E) be a plane bipartite graph in which |V*_{1}*| = |V*_{2}*|. Let vertices v*_{1}*, v*_{2}*, v*_{3}*, and v*_{4} *appear cyclically on a face of G. If v*_{1}*, v*_{3} ∈ *V*_{1} *and v*_{2}*, v*_{4} ∈ *V*_{2}*, then*

In our proof, it is essential to be familiar with various distances one naturally may consider within a given *S*-cored hexagon. These are displayed in Fig. 5 (note that the unit used is the distance between two consecutive lattice lines).

** Proof of Theorems 2.1 and 2.2:** We prove Eqs.

**2.1**and

**2.2**by induction on

*x*+

*y*+

*z*. The base cases are the instances when

*x*= 0,

*y*= 0, or

*z*= 0.

Consider first the case in which *x*, *y*, and *z* have the same parity. Because of symmetry, it is enough to verify the instance when *z* = 0. In that case, the *S*-cored hexagon *SC*_{x,y,0}(*a*, *b*, *c*, *m*) looks as illustrated in Fig. 6. Then, the hexagon *H* cut out from the *S*-cored hexagon by extending sides of the *a*- and *b*-lobes of the shamrock core, as indicated in Fig. 6 (dotted lines), must be tiled internally in each tiling of *SC*_{x,y,0}(*a*, *b*, *c*, *m*). Indeed, this follows by the same argument we used to show that the top hexagonal subregion in Fig. 4*B* is internally tiled, except we need to apply it now for both dashed-line cuts. (The argument applies because the northwestern and southeastern sides of *H* have the same length, *m.*)

Because *H* is tiled internally, it follows that the rhombus that fits in the top right corner of *SC*_{x,y,0}(*a*, *b*, *c*, *m*) and rests on both *H* and the *a*-lobe of the shamrock is forced to be tiled as shown. The same is true for the analogous rhombus fitting in the bottom left corner. Note that the region obtained from *SC*_{x,y,0}(*a*, *b*, *c*, *m*) by removing *H* and these two rhombi is precisely the magnet bar region (Fig. 6; because we are in the case in which *x*, *y*, and *z* have the same parity and we assume *z* = 0, both *x* and *y* are even). It follows that we have

(for the second equality, we used Fig. 5 to read off the side lengths of *H*). Substituting the values of and given by Eqs. **1.1** and **3.1** in the right-hand side above, it is apparent that it becomes precisely the *z* = 0 specialization of the expression on the right-hand side of Eq. **2.1**. This checks the base case of the induction when *x*, *y*, and *z* have the same parity. When *x*, *y*, and *z* have mixed parities, we may assume without loss of generality that *x* has parity opposite the parities of *y* and *z*. Then there are two inequivalent base cases to consider, namely *x* = 0 and *y* = 0 (*z* = 0 follows from the latter). Both follow in the same way as the case worked out above. For *x* = 0 and *y* and *z* odd, we obtain

whereas for *z* = 0, *x* odd, and *y* even, we obtain

Using Eqs. **1.1** and **3.1**, one readily sees that the above equations agree with the *x* = 0 (respectively, *z* = 0) specializations of Eq. **2.2**. This concludes the verification of all the base cases we need for our induction.

The induction step is based on Kuo’s graphical condensation (stated in Theorem 4.1). More precisely, we use graphical condensation to obtain recurrences for the number of lozenge tilings of the *S*-cored hexagons *SC*_{x,y,z}(*a*, *b*, *c*, *m*), valid for *x*, *y*, *z* ≥ 1, and then verify that the right-hand side of the claimed Eqs. **2.1** and **2.2** satisfy the same recurrences.

We need two different recurrences, one for the case in which *x*, *y*, and *z* have the same parity, and one for the mixed-parity case. Both follow by applying graphical condensation in the same fashion, namely by choosing the four removed unit triangles to be along two sides of the outer boundary of the *S*-cored hexagons, in the pattern shown in Fig. 7. In particular, only the outer boundary of the *S*-cored hexagons changes in the resulting subregions, whereas the shamrock core remains intact. Because of this, it suffices to discuss how we obtain our recurrences in the case in which *a* = *b* = *c* = 0.

Consider first the case in which *x*, *y*, and *z* have mixed parities (an instance of this is illustrated in Fig. 7). Without loss of generality, we may assume that the parity of *x* is different from that of *y* and *z*. When applying Kuo’s graphical condensation as described in the previous paragraph, it is of crucial importance in which corner of the outer hexagon one places the pattern of the four removed unit triangles. Because in *SC*_{x,y,z}(0, 0, 0, *m*) [which is the same as the cored hexagon *C*_{x,y,z}(*m*) of ref. 8] the core is just to the left of the true central position, the correct choice is to place the pattern of the four removed unit triangles in the right corner of the outer hexagon (Fig. 7).

Let *G* be the planar dual graph of the region *SC*_{x,y,z}(0, 0, 0, *m*). Choose the vertices *v*_{1}, *v*_{2}, *v*_{3}, and *v*_{4} as indicated in Fig. 7, where *v*_{1} is the bottom black unit triangle and *v*_{2}, *v*_{3}, and *v*_{4} are the next black unit triangles as one moves upward (Fig. 7 corresponds to the case *x* = 4, *y* = 7, *z* = 3). Then Eq. **4.1** states that the product of the number of lozenge tilings of the two regions on top is equal to the product of the number of lozenge tilings of the two regions in the middle, plus the product of the number of lozenge tilings of the two regions on the bottom. After the lozenges forced by the black unit triangles indicated in Fig. 7 are removed, the leftover regions are, in all six instances, *S*-cored hexagons. (Note that this would not be the case if we applied graphical condensation with the pattern of removed triangles placed in a different corner—some of the resulting positions of the core would not be central!) The precise parameters of these *S*-cored hexagons can be visually extracted from Fig. 7. (This is easier to do in the case *a* = *b* = *c* = 0, which is why we have reduced the proof of the recurrences to this case.)

Indeed, the leftover region on the top right of Fig. 7 is *SC*_{x,y−1,z−1}(0, 0, 0, *m*). The central left region, after clockwise rotation by 120° followed by a reflection across the vertical, becomes *SC*_{y,x,z−1}(0, 0, 0, *m*). The central right region, after counterclockwise rotation by 120° followed by a reflection across the vertical, becomes *SC*_{z,y−1,x}(0, 0, 0, *m*). Similarly, the bottom two leftover regions are *SC*_{x−1,y,z}(0, 0, 0, *m*) and *SC*_{x+1,y−1,z−1}(0, 0, 0, *m*), respectively. We obtain

As explained above, this yields a recurrence for any nonnegative values for the sizes *a*, *b*, and *c* of the lobes of the shamrock core. Taking into account the two rotations followed by reflections that we needed to consider when converting Fig. 7 into the recurrence in Eq. **4.5**, one sees that the resulting recurrence for arbitrary *a*, *b*, *c* is

where *x*, *y*, *z* ≥ 1 and *x* has parity opposite to that of *y* and *z*.

In the remaining case in which *x*, *y*, and *z* have the same parity, there is no “singled-out” corner of the outer hexagon in which to place the pattern of removed unit triangles when applying condensation—any of the six choices gives a recurrence for *S*-cored hexagons. To be closer to the previous case, we again choose to fit this pattern in the rightmost corner. The same arguments lead in this case to the recurrence

where *x*, *y*, *z* ≥ 1 and *x*, *y*, and *z* have the same parity.

Using the “cancellation rule”

where *x* is an integer or a half-integer, it is routine to verify that the expressions on the right-hand sides of Eqs. **2.1** and **2.2** also satisfy the recurrence Eqs. **4.6** and **4.7**. This completes the proof of Theorems 2.1 and 2.2.

** Remark 1.** The special case

*a*=

*b*=

*c*= 0 of Theorems 2.1 and 2.2 was the main result of our earlier paper (Ref. 8) (see Theorems 1 and 2 there). At the other extreme, the specialization

*x*=

*y*=

*z*= 0 of Theorems 2.1 and 2.2 provides the following interesting picture (Fig. 8). In this case, the

*S*-cored hexagon

*SC*

_{0,0,0}(

*a*,

*b*,

*c*,

*m*) is the disjoint union of three hexagons. It follows that

This offers a different way of viewing Theorems 2.1 and 2.2 as a generalization of MacMahon’s theorem (Eq. **1.1**). Namely, they may be regarded as simultaneously generalizing three applications of MacMahon’s formula.

## 5. Deducing Theorem 1.1. Geometric Interpretation

** Proof of Theorem 1.1.** By Eq.

**1.3**, the explicit definition of the expression on the left-hand side of Eq.

**1.4**is

In the *S*-cored hexagons on the right-hand side above, the *x*-, *y*-, and *z*-parameters have the same parity (all being equal to *N*). Thus, the number of their lozenge tilings is given by the formula provided in Theorem 2.1. Applying this formula, one obtains, after simplifications, that

Recall the Glaisher–Kinkelin formula (11)

where *A* = 1.28242712… is a constant (called the Glaisher–Kinkelin constant). This readily implies that

As *m* is fixed, Eq. **5.4** shows that both the numerator and the denominator of the second fraction on the right-hand side of Eq. **5.2** approach 1 as *N* → ∞. It follows, then, from Eq. **5.2** that

The first equality in Eq. **1.4** follows from Eqs. **5.1** and **5.5**. The second equality in Eq. **1.4**, as well as Eq. **1.5**, then follow using Eq. **1.1**.

A geometric interpretation for the symmetric form (Eq. **1.5**) of Theorem 1.1 is sketched in Fig. 9. The first hexagon is determined by reflecting the lobes in the corresponding vertices of the central triangle of the shamrock; the second is described by the picture.

** Remark 2.** Recall that a lozenge tiling of a hexagon naturally lifts to a 3D surface (see e.g., ref. 12). This lifting also works in the presence of a hole of “charge zero” (see the detailed discussion in ref. 13). For instance, the tiling shown on the left in Fig. 10 lifts to the surface shown on the right in the same figure (note that this surface has an overhang and some precipices in the middle). From this point of view, the case

*m*=

*a*+

*b*+

*c*of Theorems 2.1 and 2.2 states that the number of such surfaces is given by the explicit formulas in Eqs.

**2.1**and

**2.2**.

## Acknowledgments

This work was supported in part by National Science Foundation Grant DMS-1101670 (M.C.) and in part by the Austrian Science Foundation Fonds zur Förderung der Wissenschaftlichen Forschung, Grants Z130-N13 and S9607-N13, the latter in the framework of the National Research Network “Analytic Combinatorics and Probabilistic Number Theory” (C.K.).

## Footnotes

- ↵
^{1}To whom correspondence should be addressed. E-mail: mciucu{at}indiana.edu.

Author contributions: M.C. and C.K. performed research and wrote the paper.

The authors declare no conflict of interest.

This article is a PNAS Direct Submission.

↵*A lozenge is the union of two fundamental regions on the triangular lattice.

↵

^{†}By the planar dual graph of a region on the triangular lattice, we understand the graph whose vertices are the unit triangles inside the region, and whose edges connect vertices corresponding to unit triangles that share an edge.

## References

- ↵
- MacMahon PA

- ↵
- ↵
- ↵
- ↵
- ↵
- Koutschan C,
- Kauers M,
- Zeilberger D

*q*-TSPP-conjecture. Proc Natl Acad Sci USA 108(6):2196–2199. - ↵
- Bressoud DM

- ↵
- ↵
- Cohn H,
- Larsen M,
- Propp J

- ↵
- ↵
- Glaisher JWL

- ↵
- ↵
- Ciucu M

## Citation Manager Formats

### More Articles of This Classification

### Physical Sciences

### Related Content

- No related articles found.

### Cited by...

- No citing articles found.