Keywords: algebraic combinatorics, permanent/determinant trick, tilings, rhombic tilings, domino tilings, matching, hexagonal systems, dominoes, perfect matchings, counting matchings, plane partitions - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Article: 973 of sci.math.research From: elkies@ramanujan.harvard.edu (Noam Elkies) Subject: Re: Tiling/Combinatorics puzzle Summary: There's some non-trivial math here! Date: Sun, 30 May 1993 00:00:03 GMT Keywords: algebraic combinatorics, domino tilings, matching, permanent/determinant trick Organization: Harvard Math Department In article <1993May24.173049.16004@donau.et.tudelft.nl> arlet@einstein.et.tudelft.nl (Arlet Ottens) writes: >How many ways are there to cover an 8x8 square with 32 tiles of size 2x1 ? 12988816 = 3604^2 >Is there a general formula for larger squares ? Yes. In fact there's a formula for rectangles: the number of ways to tile an MxN rectangle with 1x2 dominos is 2^(M*N/2) times the product of { cos^2(m*pi/(M+1)) + cos^2(n*pi/(N+1)) } ^ (1/4) over all m,n in the range 0In article <1993May24.173049.16004@donau.et.tudelft.nl> >arlet@einstein.et.tudelft.nl (Arlet Ottens) writes: >>How many ways are there to cover an 8x8 square with 32 tiles of size 2x1 ? >12988816 = 3604^2 ... >(None of this is new, but it does not seem to be well-known: indeed >each of the above steps seems to have been discovered independently >several times, and I'm not sure whom to credit with the first discovery >of this particular application of the method. Of the four steps you mention, the only one discovered in this century is the permanent-determinant method, which can be credited to Kasteleyn, Fischer, Temperley, and Percus, roughly in that order. The first three workers took a Pfaffian approach, initially to enumerate exactly the same objects, domino tilings of rectangles. Later, Kasteleyn generalized the method to an enumeration of matchings of an arbitrary planar graph by a Pfaffian. Later still, Percus noticed that permanents and determinants do the job just as well for bipartite graphs. (Definition up to sign: The Pfaffian of an anti-symmetric matrix is the square root of the determinant.) >For different approaches to exactly solvable problems involving the >enumeration of domino tilings, see the two papers of G.Kuperberg, >Larsen, Propp and myself on "Alternating-Sign Matrices and Domino >Tilings" in the first volume of the _Journal of Algebraic >Combinatorics_.) I'm very glad you mentioned these papers, especially because of who the authors are :-). Unfortunately, they do not treat the permanent-determinant method in detail. I recommend this survey: @incollection{kasteleyn:crystal, author = "P. W. Kasteleyn", booktitle = "Graph Theory and Theoretical Physics", editor = "F. Harary", publisher = "Academic Press", title = "Graph theory and crystal physics", year = 1967} Finally, I'll follow Noam's tradition of giving really hard exercises: "Exercise": Count the number of tilings of a regular hexagon by rhombuses which consist of two unit equilateral triangles. ============================================================================= Article: 980 of sci.math.research From: elkies@ramanujan.harvard.edu (Noam Elkies) Subject: Re: Tiling/Combinatorics puzzle Date: Tue, 1 Jun 1993 16:56:53 GMT Keywords: algebraic combinatorics, domino tilings, matching, permanent/determinant trick Organization: Harvard Math Department > (Noam Elkies) writes: >>In article <1993May24.173049.16004@donau.et.tudelft.nl> >>arlet@einstein.et.tudelft.nl (Arlet Ottens) writes: >>>How many ways are there to cover an 8x8 square with 32 tiles of size 2x1 ? >>12988816 = 3604^2 >... >>For different approaches to exactly solvable problems involving the >>enumeration of domino tilings, see the two papers of G.Kuperberg, >>Larsen, Propp and myself on "Alternating-Sign Matrices and Domino >>Tilings" in the first volume of the _Journal of Algebraic >>Combinatorics_.) > >I'm very glad you mentioned these papers, especially because of who >the authors are :-). Unfortunately, they do not treat the >permanent-determinant method in detail. True; sorry if my previous post did not make this clear. By the way, the problem we considered in that paper is enumerating domino tilings of figures like X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X Jim Propp found the answer (a power of 2 depending on the size of the figure; for the above it's 2^10=1024) experimentally, but it took a while to prove it. In our papers we finally gave several proofs, each suggesting further work in different directions. None of the proofs used the permanent/determinant transformation, but an argument along these lines was found subsequently. I should also point out another reference from the paper: W. Jokusch, Perfect matchings and perfect squares, J. Combin. Theory A (this was "to appear" in 1992, so it's probably appeared by now) which gives a vast generalization of the fact that the number of ways to tile an n*n by dominos is a square or twice a square depending on the parity of n/2. --Noam D. Elkies (elkies@zariski.harvard.edu) Dept. of Mathematics, Harvard University ============================================================================= Article: 978 of sci.math.research From: gk00@midway.uchicago.edu (Greg Kuperberg) Subject: Re: Tiling/Combinatorics puzzle Date: Mon, 31 May 1993 17:53:41 GMT Organization: University of Chicago Let me first take this opportunity to take back my catty comment about Noam's exercises being really hard. He did break the analysis of domino tilings of a rectangle into stages, which is a big hint. There is a tradition in mathematics of "last year's thesis, next year's problem set". However, in the best of the tradition, there are new definitions and motivations to make the same question a lot easier. To answer Alan Adler's question: Allan Adler writes: >How about triminoes, say, covering a board with r straight triminoes >and s right triminoes? No one knows, but I at least am pessimistic. The reason that Jim Propp started looking at domino tilings (and planted the seed of the our joint paper) is that he used a computer program to count them in small cases and saw some interesting patterns. Without any theorems at one's disposal, an "interesting pattern" in combinatorial enumeration usually means that the size of some set of objects factors a lot. It's almost the only pattern that's easy to see ab initio. By this principle, an enumeration which is a simple sum, for example, might be unrecognizable as such. C'est la vie. As far as I know, concerning the problem of counting tilings of any interesting region by triominoes, there are no interesting results AND no one has noticed any interesting patterns. And furthermore, if the problem is treated as an analogue of domino tilings, one of the key steps is to convert the problem to counting matchings of a planar graph. You can characterize the triomino problem as counting "menage a trois" partitions subordinate to a certain hypergraph, but the hypergraph isn't really planar, and even if it were, it's a lot hore complicated than "menage a deux". A more tractable question is: When does a region admit a tiling by triominoes, say by r planks and s elbows? A pretty good method to establish an answer of "no", which was recently generalized by Conway and Lagarias, is to treat the region as a formal sum of its squares, and ask if it is an integral combination of the triominoes. For an answer of no, you can find a map from the abelian group generated by the squares to Z or Z/n that annihilates all triominoes but does not annihilate the region. ============================================================================= Article: 984 of sci.math.research From: gk00@midway.uchicago.edu (Greg Kuperberg) Subject: Re: Tiling/Combinatorics puzzle Date: Wed, 2 Jun 1993 00:31:19 GMT Keywords: algebraic combinatorics, domino tilings, matching, permanent/determinant trick Organization: University of Chicago (Noam Elkies) writes: >W. Jokusch, Perfect matchings and perfect squares, J. Combin. Theory A >(this was "to appear" in 1992, so it's probably appeared by now) I doubt it! How long did it take JCTA to publish your paper? Jockusch's paper has conceivably appeared in the latest issue; it hadn't as of May. I have an already-refereed paper waiting with JCTA and they told me it would be 18 months. >which gives a vast generalization of the fact that the number of >ways to tile an n*n by dominos is a square or twice a square >depending on the parity of n/2. Per Noam's private request, here is one description following Jockusch of what the number of tilings is a square or double-square of: First, I need to define the residue and the sign of a tiling by means of square moves, where a square move consists of switching a pair of adjacent, horizontal dominoes to vertical. Every pair of tilings is connected by a sequence of square moves and inverse square moves. The residue (mod 4) of the all-horizontal tiling is 0, it is constant under a square move away from the center of the big square, and it increases by 1 under a square move at the center of the square. A tiling is positive if its residue is 0, negative if it is 2, and null if it is odd. If N is the number of positive minus negative centrally-symmetric tilings, then there are N^2 or 2N^2 tilings in all. What's really going on is this: Given an arbitrary centrally-symmetric planar graph whose central face has 8k+4 sides, a perfect matching also has a residue r mod 4, and if the total of i^r over all centrally-symmetric matchings is a+ib, then the total number of matchings is a^2+b^2. If the graph additionally has a 4-fold rotational symmetry, then either a=b or b=0, depending on a parity condition. ============================================================================= Article: 990 of sci.math.research From: aigrain@cerise.irit.fr (Philippe AIGRAIN) Subject: Re: Tiling/Combinatorics puzzle Date: Thu, 3 Jun 1993 08:46:53 GMT Organization: IRIT-UPS, Toulouse, France (Greg Kuperberg) writes: [stuff on counting tilings by triminoes deleted] >A more tractable question is: When does a region admit a tiling by >triominoes, say by r planks and s elbows? A pretty good method to >establish an answer of "no", which was recently generalized by Conway >and Lagarias, is to treat the region as a formal sum of its squares, >and ask if it is an integral combination of the triominoes. For an >answer of no, you can find a map from the abelian group generated by >the squares to Z or Z/n that annihilates all triominoes but does not >annihilate the region. Claire and Richard Kenyon (respectively from ENS Lyon, France and Institut Fourier, Grenoble, France) recently extended the Conway-Lagarias method to give a definite answer to the question: "Can a region without holes be tiled by a set of two rectangles - one k x l and one l x k ?" This result has been first presented at the 2nd Workshop on Polyominoes and Tilings (ENS Lyon, June 1992) and later at FOCS'92. Maurice Nivat and myself have also tried to extend a result on tilability of convex regions by dominoes to triminoes (or any set of one vertical bar and one horizontal bar of the same length). The result for tiling by dominoes is as follows: A convex region can be tiled by dominoes if and only if its diagonal section are both 2-reducible. Diagonal sections are the words of Zn built by intersecting the region by successive diagonal lines and counting elements in each intersection. A word of Zn is 2-reducible (resp. k-reducible) iff it is the additive projection of a stack of couples (resp. k-uples) of 1. For instance, 1 3 3 1 is 2-reducible, 3 1 1 3 is not. This result was also presented at the 2nd Workshop on Polyominoes and Tilings and at the 8th Summer Conference on General Topology and its Applications (Queens College, NY, June 1992) We conjecture that a convex region is tilable by triminoes iff its diagonal sections are both 3-reducible. As a matter of fact, the 3rd Workshop on Polyominoes and Tilings will be held at the Institut de Recherche en Informatique de Toulouse, France January 20-21, 1994. Anyone interested to receive the call for participation and communications to this unformal seminar should send me e-mail. Philippe Aigrain Institut de Recherche en Informatique de Toulouse ============================================================================= Article: 995 of sci.math.research From: sieda@hrz.uni-bielefeld.de ( Torsten Sillke) Subject: Re: Tiling/Combinatorics puzzle Date: Thu, 3 Jun 1993 16:57:18 GMT Keywords: tilings, hexagonal systems, dominoes, perfect matchings Organization: Universitaet Bielefeld, Rechenzentrum Another way to compute the number of domino tilings (perfect matchings) of the n*m board (n*m grid). ([1, 2, 3, 4]) This method was used mainly for hexagonal systems, but can be used for other graphs too [3]. [1] P. John, J. Rempel Counting perfect matchings in hexagonal systems in: Graphs, Hypergraphs and Applic. Proc. of the Conference on Graph Theory ( Euba 84 ) 72-79 [2] P. John, H. Sachs Calculating the Number of Perfect Matchings and of Spanning Trees, Pauling's Orders, the Characteristic Polynomial, and the Eigenvectors of a Benzenoid System in: Topics in Current Chemistry, Vol 153, Springer (1990) 145-179 [3] K. A. Al-Khnaifes Graphentheoretische Methoden zur Loesung Linearer Gleichungen und ihre Anwendung auf Probleme inner- und ausserhalb der Graphentheory Thesis TH Ilmenau (1988) [4] H. Sachs Perfect Matchings in hexagonal systems Combinatorica 4 (1984) 89-99 [ Algorithm (faster than the usually max match for bipartite graphs). Conjecture for a necessary and sufficient condition for a perfect matching, which was disproved in [5].] [5] Zhang Fu-ji, Chen Rong-si, Guo Xiao-fong Perfect Matchings in Hexagonal Systems Graphs and Combinatorics 1:4 (1985) 383-386 [ Proof of a necessary and sufficient condition for a perfect matching. They give a counterexample to a conjecture of [4].] [6] D.M. Cvetkovic, M. Doob, H. Sachs Spectra on Graphs - theory and applic. Academic Press, (1980) [ for domino tilings see the chapter: Dimer Problem. It gives an asymthotics too. ] [7] R. C. Read The dimer problem for narrow rectangular arrays: A unified method of solution, and some extensions Aequationes Mathematicae 24 (1982) 47-65 [ the variations include the triomino I3 (trimer) and diagonal dimers.] [8] A. W. M. Dress, T. Sillke Ueber Domino-Ueberdeckungen von Schachbrett- und aehnlichen Mustern unpublished note, Bielefeld, (1984) [ we had a necessary condition for 1) hexagonal systems: the one of H. Sachs [4] 2) domino tilings: the diagonal cuts of P. Aigrain (if I understand him right.) A non-tilable non-convex figure, which fullfills the diagonal criterium: x x x x x x x x ] [9] R. L. Graham, D. E. Knuth, O. Pataschnik; Concrete Mathematics, Addison Wessley, Reading (1994) 2nd Ed. Chap. 7.1: Domino Theory and Change [ The dimer problem for narrow rectangular arrays (width 2 and 3) ] Problem 7.51: [ the dimer problem solved with eigenvalues ] - M. E. Fisher; Statistical mechanics of dimers on a plane lattice, Physical Review 124 (1961) 1664-1672 - J. K. Percus; Combinatorial Methods, Springer Verlag, 1971 [ the dimer problem, pp 89-123 ] - R. P. Stanley, On dimer coverings of rectangles of fixed width, Discrete Applied Mathematics 12 (1985) 81-87 - N. Elkies, G.Kuperberg, Larsen, Propp "Alternating-Sign Matrices and Domino Tilings", 2 articles Journal of Algebraic Combinatorics, 1 - W. Jokusch; Perfect matchings and perfect squares, J. Combin. Theory A, (1993?) - G. Kuperberg; Symmetries of Plane Partitions and the Permanent-Determinant Method, Journal of Combinatorial Theory Series A (199??) ------------------------------------------------------ Example for the number of tilings of the 5x6 board: Orient the edges of the 5x6 grid in the following way. . <- p1 -> . <- p2 -> . | | | | | v v v v v . -> . <- . -> . <- . | | | | | v v v v v . <- . -> . <- . -> . | | | | | v v v v v . -> . <- . -> . <- . | | | | | v v v v v . <- . -> . <- . -> . | | | | | v v v v v . -> v1 <- . -> v2 <- . 1 1 * 1 * * Number of pathes from p1 to v1 and v2 * 3 * 1 * 4 * 5 * 1 * 12 * 7 * 16 * 24 * 8 * 52 * 39 * <- 5x6 rectangle 68 * 115 * 47 * 235 * 201 * <- 5x8 rectangle Number of perfect matchings = Abs Determinat M M[i,j] = number of pathes from p[i] to v[j]. In the example 5x6: [ 52 39 ] M = [ ] [ 39 52 ] Det M = 1183 In the example 5x8: [ 235 201 ] M = [ ] [ 201 235 ] Det M = 14824 -------------------------------------------------------------- To answer the question of G. Kuperberg: What is the number of tilings of a hexagon which rhombuses of unit equilateral triangles? Hexagon: . . . . . . . . . . . . . . . a hexagon with edgelengths (a,b,c)=(6,3,2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . The opposite side has the same edgelength. Number of rhombuses to tile: ab+bc+ac S(a+b+c) S(a) S(b) S(c) Number of tilings: ------------------------- S(a+b) S(a+c) S(b+c) with S(n) = 0! 1! 2! ... (n-1)! this is an easy exercise with the method of [1, 2, 3, 4], as the number of paths are binomial coefficients, and the determinant is easy to compute. Asymtotics of S(n): see Gradshteyn 8.333 or: Barnes, The Theory of the G-Function, Quarterly Math. 1900, 264-314 ln(S(x)) = x/2 ln(2 Pi) - ln(A) + 1/12 - 3/4 x^2 + (x^2/2 - 1/12)ln(x) + O(x^(-2)) with A = 1.28242713 Torsten Sillke ============================================================================= Article: 999 of sci.math.research From: gk00@midway.uchicago.edu (Greg Kuperberg) Subject: Re: Tiling/Combinatorics puzzle Date: Fri, 4 Jun 1993 02:02:51 GMT Keywords: tilings, hexagonal systems, dominoes, perfect matchings Organization: University of Chicago ( Torsten Sillke) writes: > What is the number of tilings of a hexagon which rhombuses of unit > equilateral triangles? > > . . . . . . . > . . . . . . . . a hexagon with edgelengths (a,b,c)=(6,3,2) > . . . . . . . . . > . . . . . . . . . > . . . . . . . . > . . . . . . . > > S(a+b+c) S(a) S(b) S(c) > Number of tilings: ------------------------- > S(a+b) S(a+c) S(b+c) > > with S(n) = 0! 1! 2! ... (n-1)! > > this is an easy exercise with the method of [1, 2, 3, 4], > as the number of paths are binomial coefficients, and the > determinant is easy to compute. Pretty good! Let me up the ante in that case. Firstly, MY determinant reduces to YOUR determinant :-). You are taking the determinant of M_ij, the number of lattice paths from the i'th edge at the top to the j'th edge at the bottom. This is either an a x a, b x b, or c x c matrix, depending on how you orient the hexagon. The machine tells you you get the same determinant each time. My matrix, A_tu, is indexed by the triangles, and has a 1 if the triangles t and u are adjacent and a 0 otherwise. (The rows are triangles pointing down and the columns are triangles pointing up by convention.) It is a familiar observation that the permanent of A is the number of tilings. In this case, permanent = determinant (exercise). If you have a matrix that has an entry of 1 that look like this: L | v ---+-- w | 1 where v is a column vector and w is a row vector, then the pivot operation is to replace this matrix by L-wv. The pivot operation does not change the determinant or the cokernel of the matrix as a homomorphism from Z^n to Z^n (although it changes it to a map from Z^(n-1) to Z^(n-1)). (The cokernel of a homomorphism is the quotient of the target by the image.) In the matrix A, each 1 entry corresponds to a single rhombus somewhere in the hexagon. Claim: If you pivot A at every 1 which corresponds to a vertical rhombus, the result is the matrix M up to global sign. Corollary: A and the three choices for M all have the same determinant, as well as cokernels as maps of Z-modules. Question: The integer cokernel of an integer matrix is an abelian group whose cardinality is the determinant. Since the determinant in this case counts tilings of a hexagon and has a nice form, what is the cokernel? All I know is that it can be presented by min(a,b,c) or fewer generators, so if one of a,b, or c=1, it is cyclic. It is not always cyclic. Question: Since the cokernel is equinumerous with the set of tilings, is there a natural bijection, or perhaps a linear isomorphism between the vector spaces of formal linear combinations of elements of the sets? Historical note: The set of tilings of an a,b,c hexagon is also the set of plane partitions in an a x b x c box, first enumerated by Colonel Percy MacMahon circa 1900. The c x c determinant above was found by Carlitz in the 60's, and perhaps by someone else earlier, and a lattice-path approach very similar to the one described by Torsten Sillke was found (independently?) by Gessel and Viennot. ============================================================================= There is a bijection between the hexagonal tilings and the plane partitions [1]. [1] G. David, C. Tomei; The problem of the calissons, AMM 96 (May 1989) 429-431 [ They give a bijection: (n,n,n) hexagonal tilings <-> (n,n,n) plane partitions. ] [2] F. Galvin letter AMM 97 (1990) 131 [3] S. Kannan, Tiling Polygons with Parallelograms, Discrete Computational Geometrie 7 (1992) 175-188 [A condition for tiling with parallelograms ] [4] H. Pfeiffer, F. Romer; Zerlegung von Regulaeren 2n-Ecken [in Rauten], Elemente der Mathematik, 38:6 (1983) 157-159 [5] Ein Zerlegungssatz fuer punktsymmetrische konvexe Vielecke, Elemente der Mathematik, 38:6 (1983) 159 Torsten Sillke ============================================================================= Article 1013 of sci.math.research: From: gk00@midway.uchicago.edu (Greg Kuperberg) Subject: Re: Tiling/Combinatorics puzzle Date: Thu, 10 Jun 1993 03:29:22 GMT Keywords: tilings, hexagonal systems, dominoes, perfect matchings Organization: University of Chicago In article sieda@hrz.uni-bielefeld.de ( Torsten Sillke) writes: >> >>Historical note: The set of tilings of an a,b,c hexagon is >>also the set of plane partitions in an a x b x c box, first enumerated >>by Colonel Percy MacMahon circa 1900. .... > >There is a bijection between the hexagonal tilings >and the plane partitions [1]. As I like to say it, a hexagonal tiling is a picture of (the 3D Young diagram of) a plane partition together with the back walls of its box. ________ / /\ \ /___/ \___\ /\ \ / /\ / \___\/___/ \ \ / /\ \ / \/___/ \___\/ \ \ / / \___\/___/ If I may toot my own horn a little (I know, I've been plenty verbose and conspicuous here anyway), the program: Plane partitions --> Tilings --> Determinant/Pfaffian --> Enumeration was suggested to me by Jim Propp. I carried out the second step of this program via the permanent-determinant method (and the non-bipartite version, the Hafnian-Pfaffian method) for all ten symmetry classes of plane partitions, and then grunged the third step for many of the symmetry classes, including cyclically symmetric, self-complementary plane partitions, equivalent to tilings invariant under a rotation by 60 degrees. There is no other known enumeration of this case. It's written up in my preprint "Symmetries of Plane Partitions and the Permanent-Determinant Method" which will appear in the Journal of Combinatorial Theory Series A some time before the new millenium. Their backlog is the reason I'm mentioning it again here. The answer, by the way, is that there are ( 1!4!7!...(3a-2)!/a!(a+1)!...(2a-1)! )^2 of them in a hexagon of size 2a, as conjectured by David Robbins. If anyone here wants a reprint, I'll send it to you by hook or by crook (i.e., by e-mail or paper mail, I haven't decided which) if you send me a request with your paper mail address. ============================================================================= Article 1197 of sci.math.research: From: William.Jockusch@math.lsa.umich.edu (William Jockusch) Subject: Re: domino tilings Date: Mon, 16 Aug 1993 14:21:22 GMT Organization: University of Michigan Engineering, Ann Arbor >I was catching up on sci.math.research, and noticed the thread about >counting domino tilings on squares and rectangles. My friend Eric >Jensen counted some of these c. 1967, and noticed that the counts >were squares or doubles of squares. He also counted domino tilings >of *odd* squares and rectangles, which he made tilable by deleting >the center square (making three different meanings of "square"!). >I don't remember the pattern, but I think the counts for the holey >odd squares were also squares or twice squares. > >Rich Schroeppel rcs@cs.arizona.edu There is a theorem that if a bipartite plane graph has four-fold rotational symmetry, the graph-theoretic distance between any vertex and its 90-degree rotational image is odd, then the number of matchings of the graph will be either a square or double a square according to whether or not the number of vertices is a multiple of 8. Because of the duality between domino tilings and perfect matchings, this includes the situation you are talking about as a special case. There is also a combinatorial interpretation for the square root in terms of 2-factors of a "quotient graph" which is basically 1/4 of the origional graph. (A 2-factor is the same thing as a matching, except that you have TWO edges at every vertex. You are allowed have an edge be a "double member" of the 2-factor.) > What happens if you move the hole around? The only fact I know of here is that IF you put the hole on the outside of the square, it doesn't matter where on the outside you put it -- as long as it is in the correct color-class (with the chessboard coloring), the number of matchings will be the same. I'm not sure who first noticed this. Thanks to Wayne Goddard for bringing this string to my attention. William Jockusch ============================================================================= Subject: The Shape of a Typical Boxed Plane Partition Date: 24 Sep 1998 18:50:22 GMT From: mark@csc.albany.edu (Mark Steinberger) Organization: The University at Albany Newsgroups: sci.math.research New Release New York Journal of Mathematics 4 (1998), 137-165 Title: The Shape of a Typical Boxed Plane Partition Authors: Henry Cohn, Michael Larsen, and James Propp Date of Publication: September 23, 1998 Keywords: Plane partitions, rhombus tilings of hexagons, calculus of variations, random tilings, limit laws for random structures Subject Classification: Primary 60C05, 05A16; Secondary 60K35, 82B20 Abstract: Using a calculus of variations approach, we determine the shape of a typical plane partition in a large box (i.e., a plane partition chosen at random according to the uniform distribution on all plane partitions whose solid Young diagrams fit inside the box). Equivalently, we describe the distribution of the three different orientations of lozenges in a random lozenge tiling of a large hexagon. We prove a generalization of the classical formula of MacMahon for the number of plane partitions in a box; for each of the possible ways in which the tilings of a region can behave when restricted to certain lines, our formula tells the number of tilings that behave in that way. When we take a suitable limit, this formula gives us a functional which we must maximize to determine the asymptotic behavior of a plane partition in a box. Once the variational problem has been set up, we analyze it using a modification of the methods employed by Logan and Shepp and by Vershik and Kerov in their studies of random Young tableaux. This paper's home page is http://nyjm.albany.edu:8000/j/1998/4-10.html It contains links to the various graphical formats of the paper, including pdf with numerous cross-reference links for ease of reading. ============================================================================= math.CO/9810019 Theresia Eisenk\"olbl Rhombus Tilings of a Hexagon with Two Triangles Missing on the Symmetry Axis math.CO/9810091 Greg Kuperberg An exploration of the permanent-determinant method math.CO/9810143 Harald Helfgott, Ira M. Gessel Enumeration of tilings of diamonds and hexagons with defects math.CO/9904150 James Propp: Enumeration of Matchings: Problems and Progress math.CO/9906102 Ilse Fischer: Enumeration of rhombus tilings of a hexagon which contain a fixed rhombus in the centre cond-mat/9906154 W. T. Lu, F. Y. Wu: Dimer statistics on the M\"obius strip and the Klein bottle the xxx Math Archive Front at http://front.math.ucdavis.edu/