A (CONJECTURAL) 1/3-PHENOMENON FOR THE NUMBER OF RHOMBUS TILINGS OF A HEXAGON WHICH CONTAIN A FIXED

RHOMBUS

C. KRATTENTHALER^{†}

Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria.

                            E-mail: kratt@ap.univie.ac.at
                  WWW: http://www.mat.univie.ac.at/People/kratt

Abstract. We state, discuss, provide evidence for, and prove in special cases the conjecture that the probability that a random tiling by rhombi of a hexagon with side lengths 2n+a, 2n+b, 2n+c, 2n+a, 2n+b, 2n+c contains the (horizontal) rhombus with coordinates (2n + x, 2n + y) is equal to \frac{1}{3} + g_{a,b,c,x,y}(n)\binom{2n}{n}^{3}/\binom{6n}{3n}, where g_{a,b,c,x,y}(n) is a rational function in n. Several specific instances of this “1/3-phenomenon” are made explicit.

1. Introduction and statement of the conjecture

Let a, b and c be positive integers, and consider a hexagon with side lengths a, b, c, a, b, c whose angles are 120^{∘} (see Figure 1.a for an example). The subject of our interest is the enumeration of tilings of this hexagon by rhombi (cf. Figure 1.b; here, and in the sequel, by a rhombus we always mean a rhombus with side lengths 1 and angles of 60^{∘} and 120^{∘}).

As is well-known, the total number of rhombus tilings of a hexagon with side lengths a, b, c, a, b, c equals

∏_{i=1}^{a} ∏_{j=1}^{b} ∏_{k=1}^{c} \frac{i + j + k − 1}{i + j + k − 2}.

(This follows from MacMahon’s enumeration [14, Sec. 429, q → 1; proof in Sec. 494] of all plane partitions contained in an a×b×c box, as these are in bijection with rhombus tilings of a hexagon with side lengths a, b, c, a, b, c, as explained e.g. in [4].)

The problem that we are going to address in this paper is the problem of enumerating rhombus tilings of a hexagon which contain a given fixed rhombus. Since the total number of rhombus tilings of a given hexagon is known, thanks to MacMahon’s formula, we may ask equivalently the question of what the probability is that a rhombus tiling

1991 Mathematics Subject Classification. Primary 05A15; Secondary 05A19 05B45 33C20 33C45 52C20.

Key words and phrases. rhombus tilings, lozenge tilings, summations and transformations for hypergeometric series, Zeilberger algorithm, multisum algorithms.

† Research partially supported by the Austrian Science Foundation FWF, grant P12094-MAT and P13190-MAT.

a. A hexagon with sides a, b, c, a, b, c, where a = 3, b = 4, c = 5  b. A rhombus tiling of a hexagon with sides a, b, c, a, b, c } c } }_{c{}  }  } a  b a b

Figure 1

of a hexagon that is chosen uniformly at random (to be precise, it is the tiling which is chosen at random, while the hexagon is given) contains a given fixed rhombus. (For example, we may ask what the probability is that a randomly chosen rhombus tiling of the hexagon with side lengths 3, 5, 4, 3, 5, 4, shown in Figure 4, contains the shaded rhombus. At this point the thick lines are without relevance.)

Figure 2

If this question is asked for an “infinite” hexagon, i.e., if we imagine the 2-dimensional plane being covered by a triangular grid (each triangle being an equilateral triangle; see Figure 2; at this point shades in the figure should be ignored), and ask the question of what the probability is that a particular rhombus formed out of two adjacent triangles (for example the shaded rhombus in Figure 2) is contained in a randomly chosen rhombus tiling of the plane (that is compatible with the triangular grid, of course), then there is a simple argument which shows that this probability is 1/3: Let us concentrate on one of the two adjacent triangles out of which our fixed rhombus is formed. (In Figure 3 we have enlarged the chosen rhombus. It is composed out of the triangles labelled 0 and 1. We are going to concentrate on the triangle labelled 0.) This triangle is adjacent to exactly three other triangles. (In Figure 3 these are the triangles labelled 1, 2 and 3.) In a rhombus tiling this triangle must be combined with exactly one of these to form a rhombus in the tiling. Hence, the probability that a random tiling will combine the triangle with the particular one to obtain the fixed rhombus is 1/3.

1 0 23 Figure 3

For a (finite) hexagon however, we must expect a very different behaviour, resulting from the boundary of the hexagon. The probability that a particular rhombus is contained in a random tiling will heavily depend on where the rhombus is located in the hexagon. (This is for example reflected in the asymptotic result of Cohn, Larsen and Propp [3, Theorem 1].) In particular, we must expect that the probability will usually be different from 1/3.

Rather surprisingly, John^{1} [11, bottom of p. 198] and Propp [17, 18, Problem 1] made the empirical observation that in a hexagon with side lengths 2n−1, 2n−1, 2n, 2n−1, 2n − 1, 2n the probability that the central rhombus is contained in a random tiling is exactly 1/3, the same being apparently true in a hexagon with side lengths 2n, 2n, 2n − 1, 2n, 2n, 2n − 1. These facts were proved by Ciucu and the author [2, Cor. 3] and, independently, by Helfgott and Gessel [9, Theorem 17]. In fact, more generally, in both papers the probability that in a hexagon with side lengths N, N, M, N, N, M, N ≢ M mod 2, the central rhombus is contained in a random tiling is expressed in terms of a single sum, from which the 1/3-result follows on simplification of the sum. These results were generalized in two directions. On the one hand, Fulmek and the author [6] found a single sum expression for this probability for any rhombus on the (horizontal) symmetry axis of the hexagon. On the other hand, Fischer [5] gave a single sum expression for the probability that the central rhombus is contained in a random tiling of a hexagon with arbitrary side lengths (i.e., with side lengths a, b, c, a, b, c). Some further single sum expressions for probabilities of “near-central” rhombi to be contained in a random tiling of a hexagon with sides N, N, M, N, N, M have been derived in [5, Theorem 2] and [7]. Finally, in complete generality, Fischer [5, Lemma 2] and Johansson [10, (4.37)] found triple sum expressions for the probability that a fixed (not necessarily central or near-central) rhombus is contained in a random tiling of a hexagon with side lengths a, b, c, a, b, c. (These two triple sum expressions are completely different from each other.)

1In fact, in [11] the problem of finding the probability that, given a hexagonal graph, a chosen fixed edge is contained in a randomly chosen perfect matching of the graph is dealt with. The motivation to consider this problem is that such hexagonal graphs serve as models for benzenoid hydrocarbon molecules. The above probability is called Pauling’s bond order. It measures how stable a carboncarbon bond (corresponding to the fixed edge) in a benzenoid hydrocarbon molecule is.

It is well-known that this problem is equivalent to our tiling problem. The link is a bijection between rhombus tilings of a fixed subregion of the infinite triangular grid (such as our hexagons) and perfect matchings of the hexagonal graph which is, roughly speaking, the dual graph of the subregion (see e.g.

[12]; “roughly speaking” refers to the little detail that the vertex corresponding to the outer face is ignored in the dual graph construction).

The purpose of this paper is to report a curious manifestation of the fact that “in the limit” the probability that a particular rhombus is contained in a random tiling is 1/3. Roughly speaking, it seems that the probability equals

1/3 plus a “nice” expression.

To make this precise, we need to introduce a convention of how to describe the position of a rhombus in a given hexagon. First of all, without loss of generality, we may restrict our considerations to the case where the fixed rhombus is a horizontal rhombus (by which we mean a rhombus such as the shaded ones in Figures 2–4), which we shall do for the rest of the paper. (The other two types of rhombi are then covered via a rotation by 120^{∘}, respectively by 240^{∘}.) In order to describe the position of a rhombus in the hexagon, we introduce, following [5], the following oblique angled coordinate system: Its origin is located in one of the two vertices where the sides of lengths b and c meet, and the axes are induced by those two sides (see Figure 4). The units are chosen such that the grid points of the triangular grid are exactly the integer points in this coordinate system. (That is to say, the two triangles in Figure 4 with vertices in the origin form the unit ‘square.’) Thus, in this coordinate system, the bottom-most point of the shaded hexagon in Figure 4 has coordinates (5, 4).

With this convention, we have the following conjecture. It extends an (ex)conjecture by Propp [17, 18, Problem 4]. Conjecture. Let a, b, c, x and y be arbitrary integers. Then the probability that a randomly chosen rhombus tiling of a hexagon with side lengths 2n + a, 2n + b, 2n + c, 2n + a, 2n + b, 2n + c contains the (horizontal) rhombus with bottom-most vertex (2n + x, 2n + y) (in the oblique angled coordinate system) is equal to

\frac{1}{3} + f_{a,b,c,x,y}(n)\binom{2n}{n}^{3}/\binom{6n + 2}{3n + 1}  for n > n_{0},  (1.1)

for a suitable n_{0} which depends on a, b, c, x and y, where f_{a,b,c,x,y}(n) is a rational function in n.^{2}

2This statement is clearly equivalent to the statement in the abstract. The form (1.1) of the expression is more convenient in the subsequent listing of special cases.

c  a b  b a  c

Figure 4. The oblique angled coordinate system

As is shown in Section 2, for any specific a, b, c, x, y the corresponding formula for f_{a,b,c,x,y}(n) can be worked out completely automatically by the use of a computer (given that the Conjecture is true, of course). We have in fact produced a huge list of such formulas, of which we list a few selected instances below. As we explain in Section 3, any of these is (at least) a “near-theorem,” in the sense that it could be proved automatically by the available multisum algorithms, provided there is enough computer memory available (and, thus, will at least be a theorem in the near future). Also in Section 3, we elaborate more precisely on which of these are just conjectural, and which of them are already theorems^{3}. However, we do not know how to prove the Conjecture in general, that is, for generic values of a, b, c, x, and y (cf. Section 3 for a possible approach).

Here is the announced excerpt from our list of special instances of the Conjecture:

f_{−1,−1,0,−1,−1}(n) = f_{2,2,1,2,1}(n) = 0 for n ≥ 1,  (1.2)

f_{2,1,1,2,1}(n) = f_{2,1,1,1,1}(n) = f_{1,2,1,2,1}(n) = f_{1,2,1,1,0}(n) = f_{−1,0,0,0,−1}(n) = f_{−1,0,0,−1,−1}(n) = f_{0,−1,0,0,0}(n) = f_{0,−1,0,−1,−1}(n) = 0 for n ≥ 1, (1.3)

f_{1,1,1,1,1}(n) = f_{1,1,0,1,−1}(n) = f_{1,1,0,1,1}(n)

= f_{1,1,1,0,−1}(n) = f_{1,1,1,0,1}(n) = f_{1,1,1,1,0}(n) = f_{0,2,0,1,0}(n)

= f_{2,0,0,0,1}(n) = f_{2,0,0,1,0}(n) = f_{2,0,0,1,1}(n) = f_{2,0,0,2,0}(n) = \frac{1}{3} for n ≥ 1, (1.4)

3For the convenience of the reader, we have marked conjectures by an asterisk in the equation number.

f_{1,1,0,0,−1}(n) = f_{1,1,0,0,0}(n) = f_{2,0,1,1,0}(n) = \frac{1}{3}  for n ≥ 1,  (1.5*)

f_{0,2,1,1,0}(n) = −\frac{2}{3}  for n ≥ 1,  (1.6)

f_{1,1,1,0,0}(n) = −\frac{2}{3}  for n ≥ 1,  (1.7*)

f_{1,1,0,1,0}(n) = \frac{4}{3}  for n ≥ 1,  (1.8)

f_{4,3,1,3,2}(n) = f_{4,3,1,4,2}(n) = \frac{4}{3}  for n ≥ 1,  (1.9*)

f_{0,0,0,0,0}(n) = −\frac{(6n + 1)}{6(3n + 1)}  for n ≥ 1,  (1.10)
f_{0,0,1,0,0}(n) = −\frac{2(6n + 1)}{3(3n + 1)}  for n ≥ 1,  (1.11)
f_{3,3,0,3,1}(n) = \frac{2(2n + 1)(3n + 2)(4n + 5)}{3(n + 1)^{2}(6n + 5)}  for n ≥ 1,  (1.12)

f_{2,1,0,3,−1}(n) = \frac{4n^{3} + 18n^{2} + 12n + 1}{6(n + 1)^{2}(2n − 1)}  for n ≥ 2,  (1.13*)

f_{5,1,0,3,2}(n) = \frac{(3n + 2)(16n^{3} + 54n^{2} + 57n + 20)}{3(n + 1)^{2}(n + 2)(6n + 5)}  for n ≥ 1,  (1.14*)

f_{−1,5,0,2,−1}(n) = \frac{(3n + 2)(2n^{2} + 4n + 1)}{3(n + 1)^{2}(n + 2)}  for n ≥ 1,  (1.15*)

f_{10,3,0,1,4}(n) = \frac{(2n+1)(2n+3)(3n+2)(3n+4)(3n+5)}{6(n+1)^{2}(n+2)^{2}(n+3)^{2}(n+4)^{2}(n+5)(2n−3)(2n−1)(6n+5)(6n+7)(6n+11)}

×(176n^{9}+3080n^{8}+21692n^{7}+74546n^{6}+102578n^{5}−73279n^{4}−362598n^{3}−283977n^{2}+24762n+55440)
for n ≥ 2. (1.16*)

2. How are these conjectures and results discovered?

Point of departure for all these discoveries is an observation by Propp [17, 18, Problem 4]: He conjectured that the probability that a randomly chosen rhombus tiling of a hexagon with all side lengths equal to N contains the “near-central” rhombus (this is the rhombus with bottom-most vertex (N, N) in the oblique angled coordinate system) is equal to 1/3 plus a “nice” formula in N.^{4} Should this observation be true, then the Mathematica program Rate^{5} (“Rate!” is German for “Guess!”), respectively its Maple equivalent GUESS^{6}, will find the formula, given enough initial terms of the sequence.

4Commonly, by a “nice” formula one means an expression which is built by forming products and quotients of factorials. A strong indication that one encounters a sequence (a_{N})_{N≥0} for which a “nice”

formula exists is that the prime factors in the prime factorization of a_{N} do not grow rapidly as N becomes larger. (In fact, they should grow linearly.)

Let us see how this works in the case that N is odd. For the generation of the probabilities, Propp used the programs vaxmaple^{7} and vaxmacs^{8}, which are based on the evaluation of determinants of large (if though sparse) matrices. However, since then triple sum formulas have been found by Fischer [5, Lemma 2] and Johansson [10, (4.37)], which allow to generate these probabilities much more efficiently. We choose to use Fischer’s formula. We state it below.

Theorem. Let a, b and c be positive integers, and let (x, y) be an integer point such that 0 ≤ x ≤ b + a − 1 and 1 ≤ y ≤ c + a − 1. Then the probability that a randomly chosen rhombus tiling of a hexagon with side lengths a, b, c, a, b, c contains the (horizontal) rhombus with bottom-most vertex (x, y) (in the oblique angled coordinate system) is equal to

\frac{c!}{(b + 1)_{c}} ∑_{i=1}^{a} ∑_{j=1}^{a} ∑_{s=1}^{j} (−1)^{i+s}\binom{j − 1}{s − 1} \binom{c + i + x − y − 2}{x − 1} \binom{b + s − x + y − 1}{b + s − x − 1}

· \frac{(b + 1)_{s−1} (c + 1)_{i−1} (b + c + i)_{j−i}}{(j − i)! (i − 1)! (b + c + 1)_{s−1}} . (2.1)

We now program this formula in Mathematica.

Mathematica 2.2 for DOS 387
Copyright 1988-93 Wolfram Research, Inc.
In[1]:= F[a ,b ,c ,x ,y ]:=c!/Pochhammer[b+1,c]*
   Sum[Sum[Sum[(-1)^{∧}(i+s)*Binomial[j-1,s-1]*
     Binomial[c+i+x-y-2,x-1]*Binomial[b+s-x+y-1,b+s-x-1]*
     Pochhammer[b+1,s-1]*Pochhammer[c+1,i-1]*
     Pochhammer[b+c+i,j-i]/(j-i)!/(i-1)!/Pochhammer[b+c+1,s-1],
   {s,1,j}],{j,1,a}],{i,1,a}]

Now we generate the first eleven values of these probabilities for N = 2n + 1 and subtract 1/3 from them.

In[2]:= Table[F[2n+1,2n+1,2n+1,2n+1,2n+1]-1/3,{n,1,11}]

5written by the author; available from http://radon.mat.univie.ac.at/People/kratt; see [13, Appendix A] for an explanation of how the program works.

6written  by  François  Béraud  and  Bruno  Gauthier;  available  from http://www-igm.univ-mlv.fr/~gauthier.

7written by Greg Kuperberg, Jim Propp and David Wilson; available at http://math.wisc.edu/~propp/software.html.

8written by David Wilson; also available at http://math.wisc.edu/~propp/software.html.

          4    3    2000    245    296352    142296    43188288
Out[2]= {---, ---, ------, -----, --------, --------, ----------,
         105  143  138567  22287  33393355  19126225  6743906935
      759169125     15365378600    55469016746     805693639296
⟩  ------------, -------------, --------------, ---------------}
     135054066707  3067656658059  12280863528759  195909013434965

Next we load Rate, and apply Rate’s function Ratekurz to the sequence of numbers.

In[3]:= ⟨ ⟨rate.m
In[4]:= Apply[Ratekurz,%2]
                             2
                   (1 + 2 i1)  (2 + 3 i1) (4 + 3 i1)
         4 Product[---------------------------------, {i1, 1, -1 + i0}]
                            2
                    (1 + i1)  (5 + 6 i1) (7 + 6 i1)
Out[4]= {-------------------------------------------------------------}
                                      105

The program outputs a formula which generates the terms of the sequence that was given as an input. The formula is written as a function in i0, i.e., we must replace i0 by n. In more compact terms, the formula can be rewritten as

\frac{1}{3}\binom{2n}{n}^{3}/\binom{6n + 2}{3n + 1}.  (2.2)

(It should be observed that this expression is exactly the one which features in (1.1).)

At this point, this formula is of course just a conjecture. It has however been proved in [7, Corollary 7, (1.9)].

Being adventurous, one tries the same thing for other choices of the parameters a, b, c, x and y. Very quickly one discovers, that a similar phenomenon seems to occur for any choice 2n + a, 2n + b, 2n + c for the side lengths and (2n + x, 2n + y) for the coordinates of the bottom-most point of the fixed rhombus, where a, b, c, x, and y are fixed integers. Although the (conjectural) expressions that one finds need not be “nice” anymore in the strict sense above, it is at worst polynomial factors in n that appear in addition. Moreover, one also realizes soon that division of such an expression by the expression in (2.2) apparently always results in a rational function in n, i.e., the Conjecture in Section 1 is discovered.

Let us see just one such example. We choose a hexagon with side lengths 2n + 2, 2n+1, 2n, 2n+2, 2n+1, 2n, and (2n+3, 2n−1) for the coordinates of the bottom-most point of the fixed rhombus. Then we obtain the following numbers for n = 1, 2, …, 15. The reader should note that we immediately divide the expression (2.2).

In[5]:= Table[(F2[2n+2,2n+1,2n,2n+3,2n-1]-1/3)/(Binomial[2n,n]^{∧}3/
        Binomial[6n+2,3n+1]),{n,1,15}]

A 1/3-PHENOMENON FOR RHOMBUS TILINGS 9

           35   43  307  593   337  1585  2339  1099  4483   5921
Out[5]= {-(--), --, ---, ----, ---, ----, ----, ----, -----, -----,
           12   54  480  1050  648  3234  4992  2430  10200  13794
     2545  9649   11987  4891   17731
⟩  ----, -----, -----, -----, -----}
     6048  23322  29400  12150  44544

By having a brief glance at this sequence, it seems that the first term is “alien,” so let us better drop it.

In[6]:= Drop[%,1]
         43  307  593   337  1585  2339  1099  4483   5921
Out[6]= {--, ---, ----, ---, ----, ----, ----, -----, -----,
         54  480  1050  648  3234  4992  2430  10200  13794
     2545  9649   11987  4891   17731
⟩  ----, -----, -----, -----, -----}
     6048  23322  29400  12150  44544

By the discussion above, this should be a sequence which is given by a rational function in n. Therefore is suffices to apply Rate’s Rateint (which does just rational interpolation, in contrast to Ratekurz, which tries several other things, and which is therefore slower).

In[7]:= Apply[Rateint,%]
                           2       3
         35 + 60 i0 + 30 i0  + 4 i0
Out[7]= {---------------------------}
                     2
           6 (2 + i0)  (1 + 2 i0)

Again, the program outputs the formula as a function in i0. Since initially we dropped the first term of the sequence, we must now replace i0 by n − 1.

In[8]:= Factor[%/.i0-⟩n-1]
                        2      3
         1 + 12 n + 18 n  + 4 n
Out[8]= {-----------------------}
                   2
          6 (1 + n)  (-1 + 2 n)

Hence, if the Conjecture in Section 1 is true, f_{2,1,0,3,−1}(n) must be the expression given in the output Out[8]. (Thus, we have discovered Eq. (1.13).) Again, at this point, this is just a conjecture.

The Equations (1.2)–(1.16) in Section 1 are all found in the same way.

3. Discussion: How to prove the conjecture?

A possible approach to prove the Conjecture in Section 1 is to start with the expression (2.1) (or with the alternative expression [10, (4.37)]), replace a by 2n + a, b by 2n + b, c by 2n + c, x by 2n + x, y by 2n + y, and by some manipulation (for example, by applying hypergeometric transformation and summation formulas) convert it into the form (2.2). Everybody who has some experience with manipulating binomial/hypergeometric sums will immediately realize that this is a formidable task. In particular, it seems a bit mysterious how one should be able to isolate “1/3” from the “rest.” In any case, I do not know how to prove the Conjecture in this manner, nor in any other way.

On the other hand, as we explained in Section 2, for any specific values of a, b, c, x, and y, it is routine to find a conjectural expression for the rational function f_{a,b,c,x,y}(n) (given that the Conjecture is true). In turn, once such an expression is available, it can (at least in principle) be verified completely automatically. For, what one has to prove is the equality of the expressions (2.1), with the above replacements, and (1.1), where f_{a,b,c,x,y}(n) is the explicit rational function found by the computer. That is to say, one has to prove that a certain triple sum equals a closed form expression. Clearly, this can be done (again, at least in principle) by the available multisum algorithms^{9}, by using the algorithm to find a recurrence in n for the expression (2.1), and subsequently checking that the expression (1.1), with the computer guess for f_{a,b,c,x,y}(n), satisfies the same recurrence. Unfortunately, in any case that I tried, the computer ran out of memory.

However, as we already mentioned in the Introduction, in some cases formulas in form of single hypergeometric sums are available. If one is in such a case then one would proceed as in the above paragraph, but one would replace the multisum algorithm by Zeilberger’s algorithm^{10} (see [15, 16, 23, 24]). The advantage is that, in contrast to the multisum algorithm, Zeilberger’s algorithm is very efficient. At any rate, in any case that I looked at in connection with our problem, the Zeilberger algorithm was successful. That is to say, if I am allowed to somewhat overstate it, whenever one is in a case where a single sum formula is available, one has a theorem (i.e., Zeilberger’s algorithm will prove that the empirical found rational function f_{a,b,c,x,y}(n) does indeed satisfy the Conjecture for all values of n).

For the sake of completeness, we list the vectors (a, b, c, x, y) for which single sums are available for f_{a,b,c,x,y}(n). Clearly, it suffices to restrict c to 0 and 1. (All other values can be attained by shifts of n.)

(A) By [5, Theorem 1, (1.2)]: (2a′ + 1, 2b′ + 1, 0, a′ + b′ + 1, a′), for integers a′ and b′. (B) By [5, Theorem 1, (1.3)]: (2a′, 2b′, 1, a′ + b′, a′), for integers a′ and b′.

9The first (theoretical) algorithm for proving multisum identities automatically was given by Wilf and Zeilberger [22]. A considerable enhancement and speedup was accomplished by Wegschaider [21], who combined the ideas of Wilf and Zeilberger with ideas of Verbaeten [20]. Wegschaider’s Mathematica implementation is available from http://www.risc.uni-linz.ac.at/research/combinat/risc/software.

10A  Maple  implementation  written  by  Doron  Zeilberger  is  available  from  http://www.math.temple.edu/~zeilberg;  a  Mathematica  implementation written by Markus Schorn and Peter Paule is available from http://www.risc.uni-linz.ac.at/research/combinat/risc/software.

A 1/3-PHENOMENON FOR RHOMBUS TILINGS 11

(C) By [5, Theorem 2, (1.4)]: (2a′ + 1, 2b′ + 1, 1, a′ + b′ + 1, a′ + 1) and (2a′ + 1, 2b′ +

1, 1, a′ + b′ + 1, a′), for integers a′ and b′. (D) By [5, Theorem 2, (1.5)]: (2a′, 2b′, 0, a′ + b′, a′) and (2a′, 2b′, 0, a′ + b′, a′ − 1), for

integers a′ and b′. (E) By [6, Theorem 1]: (a′, a′, 0, 2x′ + 1, x′), for integers a′ and x′. (F) By [6, Theorem 2]: (a′, a′, 1, 2x′, x′ − 1), for integers a′ and x′. (G) By [7, Theorem 3]: (2a′, 2a′, 1, 2a′, a′ + 1) and (2a′, 2a′, 1, 2a′, a′ − 1), for an

integer a′. (H) By [7, Theorem 4]: (2a′ + 1, 2a′ + 1, 0, 2a′ + 1, a′ + 1) and (2a′ + 1, 2a′ + 1, 0, 2a′ +

1, a′ − 1), for an integer a′. (I) By [7, Theorem 5]: (2a′, 2a′, 0, 2a′, a′ + 1) and (2a′, 2a′, 0, 2a′, a′ − 2), for an

integer a′. (J) By [7, Theorem 6]: (2a′ + 1, 2a′ + 1, 1, 2a′ + 1, a′ + 2) and (2a′ + 1, 2a′ + 1, 1, 2a′ +

1, a′ − 1), for an integer a′. Thus, choosing a′ = b′ = 0 in (A), we see for example that the expression for

f_{0,0,1,0,0}(n) given in (1.11) is in fact a theorem. For, by Theorem 1, (1.3) in [5] with a = b = 2n, c = 2n + 1, the probability that a randomly chosen rhombus tiling of a hexagon with side lengths 2n, 2n, 2n + 1, 2n, 2n, 2n + 1 contains the (horizontal) rhombus with bottom-most vertex (2n, 2n) can be written in the form

SUM(n) := ∑_{k=0}^{n−1} \frac{2n (2n + 1)!}{(2n + 1)_{4n}} \binom{2n}{n}\binom{3n}{n} 2^{2n−2} (n + 3/2)_{k} (2n + 1)_{k}

· (n + k + 2)_{n−k−1} (2n + k + 2)_{n−k−1} \frac{(1/2)_{n−k−1}}{(n − k − 1)!}. (3.1)

Next we take it as an input for Zeilberger’s algorithm (we are using Zeilberger’s Maple implementation here):

|\^{∧}/|     Maple V Release 4 (Uni Wien)
⟨  ⟩ Waterloo Maple Inc.
|       Type ?  for help.
⟩ read ekhad:
⟩ ezra(zeillim);
                zeillim(SUMMAND,k,n,N,alpha,beta)
                        N-2, k/(k-n-1),1

. |\|   |/| .  Copyright (c) 1981-1996 by Waterloo Maple Inc.  All rights \ MAPLE  /  reserved.  Maple and Maple V are registered trademarks of

Similar to zeil(SUMMAND,k,n,N) but outputs a recurrence for

the sum of SUMMAND from k=alpha to k=n-beta .

Outputs the recurrence operator, certificate and right hand side.

For example, "zeillim(binomial(n,k),k,n,N,0,1);" gives output of

which means that SUM(n):=2^{∧}n-1 satisfies the recurrence

               (N-2)SUM(n)=1, as certified by R(n,k):=k/(k-n-1)
⟩ zeillim(2*n*(2*n+1)!/rf(2*n+1,4*n)*binomial(2*n,n)*binomial(3*n,n)*
⟩ 2^{∧}(2*n-2)*rf(n+3/2,k)*rf(2*n+1,k)*rf(n+k+2,n-k-1)*
⟩ rf(2*n+k+2,n-k-1)*rf(1/2,n-k-1)/(n-k-1)!,k,n,N,0,1);
-1 + N, 1/6 (1 - 2 n + 2 k) (-288 n  - 432 n  k - 912 n  - 1440 n  k
            4  2        3  2         3           3        2  2        2
     - 216 n  k  - 414 n  k  - 1746 n  k - 1096 n  - 189 n  k  - 612 n
           2  3        2           3                           2
     + 36 n  k  - 907 n  k + 48 n k  - 152 n - 163 n k + 43 n k  - 12 + 4 k
           2       3    /
     + 32 k  + 16 k )  /  ((-n + k) n (6 n + 1) (6 n + 5) (2 n + k + 2)
                      /
                  2
    (1 + 3 n + 2 n )),
                  2               3   n      3       2
        GAMMA(3 n)  GAMMA(n + 1/2)  64  (36 n  + 60 n  + 29 n + 3)
    1/2 ----------------------------------------------------------
               2   3/2         3                      2
        (n + 1)  Pi    GAMMA(n)  (6 n + 5) (6 n + 1) n  GAMMA(6 n)

⟩

It tells us that the expression SUM(n) in (3.1) satisfies the recurrence

SUM(n + 1) − SUM(n) = \frac{(3 + 29n + 60n^{2} + 36n^{3}) (3n − 1)!^{2} (2n)!^{3}}{2n^{2} (n + 1)^{2} (6n + 1) (6n + 5) (n − 1)!^{3} (6n − 1)! n!^{3}} . (3.2)

(The first term in the output, -1 + N, encodes the form of the left-hand side of (3.2), the third term gives the right-hand side. The middle term is the so-called certificate which provides a proof of the recurrence.) So it just remains to check that the expression (1.1) with f_{0,0,1,0,0}(n) as in (1.11) satisfies the same recurrence and agrees with (3.1) for n = 1, which is of course a routine task.

On the other hand, the expression for f_{2,1,1,2,1}(n) given in (1.3) cannot be established in the same way by appealing to a special case of one of (A)–(H). Still, it is also a theorem, thanks to the following simple observation: suppose that we consider a hexagon with side lengths a, b, c, a, b, c, where a = b, and a rhombus on the horizontal symmetry axis of the hexagon. Let us imagine that this rhombus were the one in Figure 3 (consisting of the triangles labelled 0 and 1). Let us denote the probability that a randomly chosen tiling contains this rhombus by p. Since the rhombus is on the symmetry axis, the probability that a randomly chosen tiling contains the rhombus consisting of the triangles labelled 0 and 2 is equal to the probability that it contains the rhombus consisting of the triangles labelled 0 and 3. Let us denote this probability by q. Any tiling must contain exactly one of these three rhombi, hence we have p + q + q = p + 2q = 1. Therefore, whenever there is a single sum formula available for p, there is also one for q. To come back to our example, the rhombus whose bottom-most point has coordinates (2n + 2, 2n + 1) in a hexagon with side lengths 2n + 2, 2n + 1, 2n + 1, 2n + 2, 2n + 1, 2n + 1, can be seen as such a rhombus consisting of triangles labelled 0 and 3, where the bottom-most point of the rhombus consisting of the triangles labelled 0 and 1 has coordinates (2n + 1, 2n + 1). This puts us in Case (E), with a′ = x′ = −1, (to see this one has to replace n by n − 1 in the above coordinatization), and thus the claimed expression for f_{2,1,1,2,1}(n) can be proved in the same manner as we proved the expression for f_{0,0,1,0,0}(n) above.

Again, for the sake of completeness, we list the additional vectors (a, b, c, x, y) for which single sums are available for f_{a,b,c,x,y}(n) by the above observation.

(C’) By [7, Theorem 1]: (2a′, 0, 0, a′+1, a′), (2a′, 0, 0, a′, a′), (2a′, 0, 0, a′, a′−1), (2a′, 0, 0, a′−1, a′−1), (0, 2a′, 0, a′+1, 0), (0, 2a′, 0, a′, −1), (0, 2a′, 0, a′, 0), (0, 2a′, 0, a′− 1, −1), for an integer a′.

(D’) By [7, Theorem 2]: (2a′ + 1, 1, 1, a′ + 2, a′ + 1), (2a′ + 1, 1, 1, a′ + 1, a′ + 1), (2a′ + 1, 1, 1, a′ +1, a′), (2a′ +1, 1, 1, a′, a′), (1, 2a′ +1, 1, a′ +2, 1), (1, 2a′ +1, 1, a′ +1, 0),

(1, 2a′ + 1, 1, a′ + 1, 1), (1, 2a′ + 1, 1, a′, 0), for an integer a′.

(E’) By [6, Theorems 1 and 2]: (2a′, 0, 0, a′ + x′, a′ − x′), (2a′, 0, 0, a′ + x′, a′ − x′ − 1), (2a′+1, 0, 0, a′+x′, a′−x′), (2a′+1, 0, 0, a′+x′, a′−x′+1), (0, 2a′, 0, a′+x′, 2x′−1), (0, 2a′, 0, a′ + x′, 2x′), (0, 2a′ + 1, 0, a′ + x′, 2x′ − 2), (0, 2a′ + 1, 0, a′ + x′, 2x′ − 1), for integers a′ and x′.

(F’) By [6, Theorems 1 and 2]: (2a′, 1, 1, a′ + x′, a′ − x′ + 1), (2a′, 1, 1, a′ + x′, a′ − x′), (2a′+1, 1, 1, a′+x′, a′−x′+2), (2a′+1, 1, 1, a′+x′, a′−x′+1), (1, 2a′, 1, a′+x′, 2x′− 1), (1, 2a′, 1, a′+x′, 2x′), (1, 2a′+1, 1, a′+x′, 2x′−2), (1, 2a′+1, 1, a′+x′, 2x′−1), for integers a′ and x′.

(G’) By [7, Theorem 3]: (2a′ + 1, 0, 0, a′ + 2, a′ + 2), (2a′ + 1, 0, 0, a′ + 1, a′ + 2), (2a′ + 1, 0, 0, a′, a′), (2a′+1, 0, 0, a′−1, a′), (0, 2a′+1, 0, a′+2, 0), (0, 2a′+1, 0, a′+1, −1),

(0, 2a′ + 1, 0, a′, 0), (0, 2a′ + 1, 0, a′ − 1, −1), for an integer a′.

(H’) By [7, Theorem 4]: (2a′, 1, 1, a′+2, a′+2), (2a′, 1, 1, a′+1, a′+2), (2a′, 1, 1, a′, a′), (2a′, 1, 1, a′−1, a′), (1, 2a′, 1, a′+2, 1), (1, 2a′, 1, a′+1, 0), (1, 2a′, 1, a′, 1), (1, 2a′, 1, a′ − 1, 0), for an integer a′.

(I’) By [7, Theorem 5]: (2a′, 0, 0, a′ + 2, a′ + 1), (2a′, 0, 0, a′ + 1, a′ + 1), (2a′, 0, 0, a′ − 1, a′), (2a′, 0, 0, a′ − 2, a′), (0, 2a′, 0, a′ + 2, 0), (0, 2a′, 0, a′ + 1, −1), (0, 2a′, 0, a′ −

1, 0), (0, 2a′, 0, a′ − 2, −1), for an integer a′.

(J’) By [7, Theorem 6]: (2a′ + 1, 1, 1, a′ + 3, a′ + 2), (2a′ + 1, 1, 1, a′ + 2, a′ + 2), (2a′ +1, 1, 1, a′, a′ −1), (2a′ +1, 1, 1, a′ −1, a′ −1), (1, 2a′ +1, 1, a′ +3, 1), (1, 2a′ +

1, 1, a′ + 2, 0), (1, 2a′ + 1, 1, a′, 1), (1, 2a′ + 1, 1, a′ − 1, 0), for an integer a′.

Table 1 lists the special cases that we considered in (1.2)–(1.4), (1.6), (1.8), (1.10)– (1.12), for which proofs are available, together with an indication from which of the Cases (A)–(H), respectively (C’)–(H’), these proofs come from. In particular, the expression for f_{0,0,1,0,0}(n) in (1.11) (together with (1.1)) provides the formula for the values of Pauling’s bond order in Tabelle 2 of [11] for higher naphtalenes N(p) of odd order p = 2n − 1, and the expression for f_{1,1,0,1,0}(n) in (1.8) (together with (1.1)) provides the formula for the values of Pauling’s bond order in Tabelle 3 of [11] for higher pyrenes

entry in (A)–(H),

a, b, c, x, y respectively (C’)–(H’)
−1, −1, 0, −1, −1 (A), a′ = b′ = −1
2, 2, 1, 2, 1 (B), a′ = b′ = 1
2, 1, 1, 2, 1 (F’), a′ = x′ = 1
2, 1, 1, 1, 1 (F’), a′ = 1, x′ = 0
1, 2, 1, 2, 1 (F’), a′ = x′ = 1
1, 2, 1, 1, 0 (F’), a′ = 1, x′ = 0
−1, 0, 0, 0, −1 (E’), a′ = −1, x′ = 1
−1, 0, 0, −1, −1 (E’), a′ = −1, x′ = 0
0, −1, 0, 0, 0 (E’), a′ = −1, x′ = 1
0, −1, 0, −1, −1 (E’), a′ = −1, x′ = 0
1, 1, 1, 1, 1 (C), a′ = b′ = 0
1, 1, 0, 1, −1 (H), a′ = b′ = 0
1, 1, 0, 1, 1 (H), a′ = b′ = 0
1, 1, 1, 0, −1 (F), a′ = 1, x′ = 0
1, 1, 1, 0, 1 (J’), a′ = 0
1, 1, 1, 1, 0 (C), a′ = b′ = 0
0, 2, 0, 1, 0 (E’), a′ = 1, x′ = 0
2, 0, 0, 0, 1 (I’), a′ = 1
2, 0, 0, 1, 0 (E’), a′ = 1, x′ = 0
2, 0, 0, 1, 1 (E’), a′ = 1, x′ = 0
2, 0, 0, 2, 0 (E’), a′ = x′ = 1
0, 2, 1, 1, 0 (B), a′ = 0, b′ = 1
1, 1, 0, 1, 0 (A), a′ = b′ = 0
0, 0, 0, 0, 0 (D), a′ = b′ = 0
0, 0, 1, 0, 0 (B), a′ = b′ = 0
3, 3, 0, 3, 1 (A), a′ = b′ = 1

Table 1

P (p) of odd order p = 2n − 1. The values in Tabelle 1 of [11] for higher benzenes B(p) are expressed by (1.1) with a = b = c = x = y = 0 and a = b = c = x = y = 1, respectively, with the expression for f_{0,0,0,0,0}(n) given in (1.10) and the one for f_{1,1,1,1,1}(n) given in (1.4). (The latter formulas have already been stated in [7, Cor. 7, (1.8) and (1.9)]. In fact, Corollary 7 of [7] contains some more evaluations of this kind.)

Coming back to the original goal, a proof of the Conjecture for arbitrary a, b, c, x and y, it may seem that it should be at least possible to achieve this in the Cases (A)–(H) and (C’)–(H’), where single sum formulas are available. For, for each specific choice of a, b, c, x and y out of one of these cases, an identity of the form “single sum = closed form” has to be proved. So one would try to follow the strategy that was suggested in complete generality at the beginning of this section: apply some manipulations (using hypergeometric transformation and summation formulas, for example) until the desired expression is obtained. This task is much less daunting here, since we are dealing now with a single sum, not with a triple sum. Moreover, as it turns out, the sums that occur are very familiar objects in hypergeometric theory (we refer the reader to [1, 19, 8] for information on this theory), they turn out to be balanced _{4}F_{3}-series, respectively verywell-poised _{7}F_{6}-series. (For example, the series in (3.1) is a balanced _{4}F_{3}-series.) For these series there are a lot of summation and transformation formulas known. However, and this is somehow mysterious, I was not able to establish any of the theorems that I presented here in this classical manner (i.e., without the use of Zeilberger’s algorithm), not to mention a general theorem for an infinite family of parameters. As already said at the beginning of this section, the biggest stumbling block in such an attempt is the question of how one would be able to isolate “1/3” from the “rest.” So, potentially, there is a hierarchy of interesting hypergeometric identities lurking behind the scene which has not yet been discovered.

References

[1] W. N. Bailey, Generalized hypergeometric series, Cambridge University Press, Cambridge, 1935.

[2] M. Ciucu and C. Krattenthaler, The number of centered lozenge tilings of a symmetric hexagon, J. Combin. Theory Ser. A 86 (1999), 103–126.

[3] H. Cohn, M. Larsen and J. Propp, The shape of a typical boxed plane partition, New York J. Math. 4 (1998), 137–166.

[4] G. David and C. Tomei, The problem of the calissons, Amer. Math. Monthly. 96 (1989), 429–431.

[5] I. Fischer, Enumeration of rhombus tilings of a hexagon which contain a fixed rhombus in the centre, J. Combin. Theory Ser. A (to appear), math/9906102.

[6] M. Fulmek and C. Krattenthaler, The number of rhombus tilings of a symmetric hexagon which contain a fixed rhombus on the symmetry axis, I, Ann. Combin. 2 (1998), 19–40.

[7] M. Fulmek and C. Krattenthaler, The number of rhombus tilings of a symmetric hexagon which contain a fixed rhombus on the symmetry axis, II, Europ. J. Combin. 21 (2000), 601–640.

[8] G. Gasper and M. Rahman, Basic Hypergeometric Series, Encyclopedia of Mathematics And Its Applications 35, Cambridge University Press, Cambridge, 1990.

[9] H. Helfgott and I. M. Gessel, Exact enumeration of tilings of diamonds and hexagons with defects, Electron. J. Combin. 6 (1) (1999), #R16, 26 pp.

[10] K. Johansson, Nonintersecting paths, random tilings and random matrices, preprint,

math/0011250.

[11] P. John, Über ein einfaches Wachstum hexagonaler Systeme und das Verhalten der Paulingschen Bindungsordnung, Wiss. Zeitschr. FSU Jena 39 (1990), 192–200.

[12] G. Kuperberg, Symmetries of plane partitions and the permanent determinant method, J. Combin. Theory Ser. A 68 (1994), 115–151.

[13] C. Krattenthaler, Advanced determinant calculus, Séminaire Lotharingien Combin. 42 (“The Andrews Festschrift”) (1999), paper B42q, 67 pp.

[14] P. A. MacMahon, Combinatory Analysis, vol. 2, Cambridge University Press, 1916; reprinted by Chelsea, New York, 1960.

[15] P. Paule and M. Schorn, A Mathematica version of Zeilberger’s algorithm for proving binomial coefficient identities, J. Symbol. Comp. 20 (1995), 673–698.

[16] M. Petkovšek, H. Wilf and D. Zeilberger, A=B, A. K. Peters, Wellesley, 1996.

[17] J. Propp, Twenty open problems on enumeration of matchings, manuscript, 1996, math/9801060.

[18] J. Propp, Enumeration of matchings: Problems and progress, in: ”New Perspectives in Algebraic Combinatorics”, L. Billera, A. Björner, C. Greene, R. Simion, and R. P. Stanley, eds., Mathematical Sciences Research Institute Publications, vol. 38, Cambridge University Press, 1999, pp. 255–291.

[19] L. J. Slater, Generalized hypergeometric functions, Cambridge University Press, Cambridge, 1966.

[20] P. Verbaeten, Rekursiebetrekkingen voor lineaire hypergeometrische funkties, Proefschrift voor het doctoraat in de toegepaste wetenschapen, Katholieke Universiteit te Leuven, Heverlee, Belgium, [21] K. Wegschaider, Computer generated proofs of binomial multi-sum identities,

diploma thesis, Johannes Kepler University, Linz, Austria, 1997; available from

    http://www.risc.uni-linz.ac.at/research/combinat/risc/publications.

[22] H. S. Wilf and D. Zeilberger, An algorithmic proof theory for hypergeometric (ordinary and “q”) multisum/integral identities, Invent. Math. 108 (1992), 575–633.

[23] D. Zeilberger, A fast algorithm for proving terminating hypergeometric identities, Discrete Math. 80 (1990), 207–211.

[24] D. Zeilberger, The method of creative telescoping, J. Symbolic Comput. 11 (1991), 195–204.

Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria.

e-mail: KRATT@Ap.Univie.Ac.At, WWW: http://www.mat.univie.ac.at/People/kratt