Conference rusure::math

    When counting, what transformations are allowed in order to eliminate
    duplicates? e.g. rotations, reflections
    
    What are we to assume about the patterns of dots on the dominoes?

>    When counting, what transformations are allowed in order to eliminate
>    duplicates? e.g. rotations, reflections

	Rotations & reflections are considered distinct.
    
>    What are we to assume about the patterns of dots on the dominoes?

	All dominos are taken to be identical:  a rectangular slab which will
cover exacly two adjacent squares on the chessboard.

	Eg: there are two ways to tile a 2x2 board:

[]
[] 

nn
uu

	(If someone can come up with a better notation, they're welcome!)

Cheers,
Andrew.

Sometimes I start answering counting questions by just doing some.  Here's
one possible tiling:

	+-------+---------------+-------+-------+---------------+-------+
	|	|		|	|	|		|	|
	|	|		|	|	|		|	|
	|	+---------------+	+	+---------------+	+
	|	|		|	|	|		|	|
	|	|		|	|	|		|	|
	+-------+---------------+-------+-------+---------------+-------+
	|	|		|	|	|		|	|
	|	|		|	|	|		|	|
	|	+---------------+	+	+---------------+	+
	|	|		|	|	|		|	|
	|	|		|	|	|		|	|
	+-------+---------------+-------+-------+---------------+-------+
	|	|		|	|	|		|	|
	|	|		|	|	|		|	|
	|	+---------------+	+	+---------------+	+
	|	|		|	|	|		|	|
	|	|		|	|	|		|	|
	+-------+---------------+-------+-------+---------------+-------+
	|	|		|	|	|		|	|
	|	|		|	|	|		|	|
	|	+---------------+	+	+---------------+	+
	|	|		|	|	|		|	|
	|	|		|	|	|		|	|
	+-------+---------------+-------+-------+---------------+-------+


Some ideas that came to mind while doing this:

o	We might want to count the dividable tilings, such as the above,
	separately from the nondividable ones.  By dividable ones, I mean where
	a tiling of 8-8 board is composed of tilings of smaller boards, in this
	case 4-2 boards.

o	

    Using a progam to count them all I got: 12,988,816
    Has anyone else tried this? I'm curious if I've got a bug hiding here.
    
    Trying to subdivide this problem seems to get in trouble. I initially
    tried to use four 4x4 boards. There are 36 combinations, so a lower
    bound would be 36**4 = 1,679,616. What is missed are the combinations
    with tiles sitting across the boundaries. But trying to enumerate
    those has eluded me. I always seem to have the higher level partition
    "invading" the lower ones... With each combination of tiles that bridge
    the upper partition boundaries, it sets up a new problem to solve for
    the lower level problem (4x4 minus a few on the edges). 
    
    It would be nice to have a formular form of this
    result: the total as a function of N sides. Any suggestions?

    re .-1
    
    My gut feeling was that counting "dividables" separately was not the
    way to go.
    
    I would suggest starting with something less ambitious and more
    verifiable e.g. N=2,4,6 before attempting N=8.
    
    I haven't actually tried this one. My brain was still searching for the
    right approach.

re .4
    
>    Using a progam to count them all I got: 12,988,816
    
    My program also output this number (after a little over 2 minutes on a
    VAX 6610).
    
>    It would be nice to have a formular form of this
>    result: the total as a function of N sides. Any suggestions?
    
    Here's my empirical data.
    
    N	tilings		WAG
    =   =======		===
    
    2	2		= 2 * 1�
    4	36		= 6�
    6	6728		= 2 * 58�
    8	12988816	= 3604�
    
    Draw your own conclusions...
    
    I am using the following notation. Squares of the chess board are
    numbered left to right, top to bottom from 0 to N�-1. A tile is
    represented by the pair of square numbers and a tiling as the
    appropriate number of tiles.
    
    My program does straightforward recursion with backtracking.
    
    With this notation the tilings for case N=4 are as follows if anyone
    wants to compare or check.
    
( 0 , 1) ( 2 , 3) ( 4 , 5) ( 6 , 7) ( 8 , 9) (10 ,11) (12 ,13) (14 ,15) 

( 0 , 1) ( 2 , 3) ( 4 , 5) ( 6 , 7) ( 8 , 9) (10 ,14) (11 ,15) (12 ,13) 

( 0 , 1) ( 2 , 3) ( 4 , 5) ( 6 , 7) ( 8 ,12) ( 9 ,10) (11 ,15) (13 ,14) 

( 0 , 1) ( 2 , 3) ( 4 , 5) ( 6 , 7) ( 8 ,12) ( 9 ,13) (10 ,11) (14 ,15) 

( 0 , 1) ( 2 , 3) ( 4 , 5) ( 6 , 7) ( 8 ,12) ( 9 ,13) (10 ,14) (11 ,15) 

( 0 , 1) ( 2 , 3) ( 4 , 5) ( 6 ,10) ( 7 ,11) ( 8 , 9) (12 ,13) (14 ,15) 

( 0 , 1) ( 2 , 3) ( 4 , 5) ( 6 ,10) ( 7 ,11) ( 8 ,12) ( 9 ,13) (14 ,15) 

( 0 , 1) ( 2 , 3) ( 4 , 8) ( 5 , 6) ( 7 ,11) ( 9 ,10) (12 ,13) (14 ,15) 

( 0 , 1) ( 2 , 3) ( 4 , 8) ( 5 , 9) ( 6 , 7) (10 ,11) (12 ,13) (14 ,15) 

( 0 , 1) ( 2 , 3) ( 4 , 8) ( 5 , 9) ( 6 , 7) (10 ,14) (11 ,15) (12 ,13) 

( 0 , 1) ( 2 , 3) ( 4 , 8) ( 5 , 9) ( 6 ,10) ( 7 ,11) (12 ,13) (14 ,15) 

( 0 , 1) ( 2 , 6) ( 3 , 7) ( 4 , 5) ( 8 , 9) (10 ,11) (12 ,13) (14 ,15) 

( 0 , 1) ( 2 , 6) ( 3 , 7) ( 4 , 5) ( 8 , 9) (10 ,14) (11 ,15) (12 ,13) 

( 0 , 1) ( 2 , 6) ( 3 , 7) ( 4 , 5) ( 8 ,12) ( 9 ,10) (11 ,15) (13 ,14) 

( 0 , 1) ( 2 , 6) ( 3 , 7) ( 4 , 5) ( 8 ,12) ( 9 ,13) (10 ,11) (14 ,15) 

( 0 , 1) ( 2 , 6) ( 3 , 7) ( 4 , 5) ( 8 ,12) ( 9 ,13) (10 ,14) (11 ,15) 

( 0 , 1) ( 2 , 6) ( 3 , 7) ( 4 , 8) ( 5 , 9) (10 ,11) (12 ,13) (14 ,15) 

( 0 , 1) ( 2 , 6) ( 3 , 7) ( 4 , 8) ( 5 , 9) (10 ,14) (11 ,15) (12 ,13) 

( 0 , 4) ( 1 , 2) ( 3 , 7) ( 5 , 6) ( 8 , 9) (10 ,11) (12 ,13) (14 ,15) 

( 0 , 4) ( 1 , 2) ( 3 , 7) ( 5 , 6) ( 8 , 9) (10 ,14) (11 ,15) (12 ,13) 

( 0 , 4) ( 1 , 2) ( 3 , 7) ( 5 , 6) ( 8 ,12) ( 9 ,10) (11 ,15) (13 ,14) 

( 0 , 4) ( 1 , 2) ( 3 , 7) ( 5 , 6) ( 8 ,12) ( 9 ,13) (10 ,11) (14 ,15) 

( 0 , 4) ( 1 , 2) ( 3 , 7) ( 5 , 6) ( 8 ,12) ( 9 ,13) (10 ,14) (11 ,15) 

( 0 , 4) ( 1 , 2) ( 3 , 7) ( 5 , 9) ( 6 ,10) ( 8 ,12) (11 ,15) (13 ,14) 

( 0 , 4) ( 1 , 5) ( 2 , 3) ( 6 , 7) ( 8 , 9) (10 ,11) (12 ,13) (14 ,15) 

( 0 , 4) ( 1 , 5) ( 2 , 3) ( 6 , 7) ( 8 , 9) (10 ,14) (11 ,15) (12 ,13) 

( 0 , 4) ( 1 , 5) ( 2 , 3) ( 6 , 7) ( 8 ,12) ( 9 ,10) (11 ,15) (13 ,14) 

( 0 , 4) ( 1 , 5) ( 2 , 3) ( 6 , 7) ( 8 ,12) ( 9 ,13) (10 ,11) (14 ,15) 

( 0 , 4) ( 1 , 5) ( 2 , 3) ( 6 , 7) ( 8 ,12) ( 9 ,13) (10 ,14) (11 ,15) 

( 0 , 4) ( 1 , 5) ( 2 , 3) ( 6 ,10) ( 7 ,11) ( 8 , 9) (12 ,13) (14 ,15) 

( 0 , 4) ( 1 , 5) ( 2 , 3) ( 6 ,10) ( 7 ,11) ( 8 ,12) ( 9 ,13) (14 ,15) 

( 0 , 4) ( 1 , 5) ( 2 , 6) ( 3 , 7) ( 8 , 9) (10 ,11) (12 ,13) (14 ,15) 

( 0 , 4) ( 1 , 5) ( 2 , 6) ( 3 , 7) ( 8 , 9) (10 ,14) (11 ,15) (12 ,13) 

( 0 , 4) ( 1 , 5) ( 2 , 6) ( 3 , 7) ( 8 ,12) ( 9 ,10) (11 ,15) (13 ,14) 

( 0 , 4) ( 1 , 5) ( 2 , 6) ( 3 , 7) ( 8 ,12) ( 9 ,13) (10 ,11) (14 ,15) 

( 0 , 4) ( 1 , 5) ( 2 , 6) ( 3 , 7) ( 8 ,12) ( 9 ,13) (10 ,14) (11 ,15) 

    Well, we probably have the answer - a number. But no proof or insight
    into why this is the answer. (But that wasn't required, was it?)

Article 708 of sci.math.research:
Newsgroups: sci.math.research
Path: nntpd.lkg.dec.com!pa.dec.com!decwrl!wupost!uwm.edu!ux1.cso.uiuc.edu!news.cso.uiuc.edu!dan
From: [email protected] (Noam Elkies)
Subject: Re: Tiling/Combinatorics puzzle
Approved: Daniel Grayson <[email protected]>
Summary: There's some non-trivial math here!
Date: Sun, 30 May 1993 00:00:03 GMT
Message-ID: <[email protected]>
References: <[email protected]>
Sender: Daniel Grayson <[email protected]>
Keywords: algebraic combinatorics, domino tilings, matching, permanent/determinant trick
Originator: [email protected]
Organization: Harvard Math Department
Lines: 76

[cross-posted to sci.math.research]

In article <[email protected]>
[email protected] (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 0<m<M+1, 0<n<N+1.

[Exercises:
 0) Why does this work for M*N odd?
 1) When M<3 the count can be determined directly;
   check that it agrees with the above formula.
 2) Prove directly this formula gives an integer for all M,N, and
   further show that if M=N it is a perfect square when 4|N and
   twice a square otherwise.
]

Where does this come from?  For starters note that, with the usual checker-
board coloring, each domino must cover one light and one dark square.  Assume
that M*N is even (but as it happens our formula will work also when both
M,N are odd --- see exercise 0 above).  Form a square matrix of size
M*N/2 whose rows and columns are indexed by the light and dark squares,
and whose (j,k) entry is 1 if the j-th light and k-th dark square are
adjacent and zero otherwise.  There are now three key ideas:

First, the number of tilings is the number of ways to match each light
square with an adjacent dark square; thus it is the _permanent_ of our
matrix (recall that the permanent of a rxr matrix is a sum of the same
r! terms that occur in its determinant, except without the usual +1/-1
sign factors).

Second, that by modifying this matrix slightly we can convert the
permanent to a determinant; this is nice because determinants are generally
much easier to evaluate than permanents.  One way to do this is to replace
all the 1's that correspond to vertical adjacency to i's, and multiply the
whole thing by a suitable power of i (which will disappear when we raise
it to a fourth power).

[Exercise 3: check that this transformation actually works as advertised!]

Third, that we can diagonalize the resulting matrix A --- or, more
conveniently, the square matrix of A' order M*N whose order-(M*N/2)
blocks are 0,A;A-transpose,0 , whence det(A') = +-(det(A))^2.  Then
the rows and columns of A' are indexed by squares of either hue on our
generalized checkerboard, and its entries are 1 for horizontally adjacent
squares, i for vertically adjacent ones, and 0 for nonadjacent (including
coincident) squares.  This A' can be diagonalized by using the trigonometric
basis of vectors v_ab (a,b as in the formula above) whose coordinate at
the (m,n)-th square is  sin(a*m*pi/(M+1)) * sin(b*n*pi/(N+1)).

[Exercise 4: verify that these are in fact orthogonal eigenvectors of A',
determine their eigenvalues, and complete the proof of the above formula.]

(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.  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_.)

--Noam D. Elkies ([email protected])
  Dept. of Mathematics, Harvard University

Article 1006 of sci.math.research:
Newsgroups: sci.math.research
Path: e2big.mko.dec.com!pa.dec.com!decwrl!ames!agate!howland.reston.ans.net!ux1.cso.uiuc.edu!news.cso.uiuc.edu!dan
From: [email protected] (Greg Kuperberg)
Subject: Re: Tiling/Combinatorics puzzle
Approved: Daniel Grayson <[email protected]>
Date: Sun, 30 May 1993 03:40:14 GMT
Message-ID: <[email protected]>
References: <[email protected]> <[email protected]>
X-Char-Esc: 29
Sender: Daniel Grayson <[email protected]>
Keywords: algebraic combinatorics, domino tilings, matching, permanent/determinant trick
Reply-To: [email protected]
X-Charset: LATIN1
Originator: [email protected]
Organization: University of Chicago
Lines: 45

In article <[email protected]> [email protected] (Noam Elkies) writes:
>In article <[email protected]>
>[email protected] (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 1010 of sci.math.research:
Newsgroups: sci.math.research
Path: e2big.mko.dec.com!pa.dec.com!decwrl!spool.mu.edu!howland.reston.ans.net!ux1.cso.uiuc.edu!news.cso.uiuc.edu!dan
From: [email protected] (Greg Kuperberg)
Subject: Re: Tiling/Combinatorics puzzle
Approved: Daniel Grayson <[email protected]>
Date: Mon, 31 May 1993 17:53:41 GMT
Message-ID: <[email protected]>
References: <[email protected]> <[email protected]> <[email protected]>
X-Char-Esc: 29
Sender: Daniel Grayson <[email protected]>
Reply-To: [email protected]
X-Charset: LATIN1
Originator: [email protected]
Organization: University of Chicago
Lines: 43

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:

In article <[email protected]> Allan Adler 
<[email protected]> 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 1012 of sci.math.research:
Newsgroups: sci.math.research
Path: e2big.mko.dec.com!dbased.nuo.dec.com!news.crl.dec.com!deccrl!decwrl!decwrl!wupost!crcnis1.unl.edu!moe.ksu.ksu.edu!ux1.cso.uiuc.edu!news.cso.uiuc.edu!dan
From: [email protected] (Noam Elkies)
Subject: Re: Tiling/Combinatorics puzzle
Approved: Daniel Grayson <[email protected]>
Date: Tue, 1 Jun 1993 16:56:53 GMT
Message-ID: <[email protected]>
References: <[email protected]> <[email protected]> <[email protected]>
Sender: Daniel Grayson <[email protected]>
Keywords: algebraic combinatorics, domino tilings, matching, permanent/determinant trick
Originator: [email protected]
Organization: Harvard Math Department
Lines: 49

In article <[email protected]> [email protected] writes:
>In article <[email protected]> [email protected] (Noam Elkies) writes:
>>In article <[email protected]>
>>[email protected] (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 ([email protected])
  Dept. of Mathematics, Harvard University

Article 1016 of sci.math.research:
Newsgroups: sci.math.research
Path: e2big.mko.dec.com!dbased.nuo.dec.com!news.crl.dec.com!deccrl!decwrl!decwrl!spool.mu.edu!uwm.edu!ux1.cso.uiuc.edu!news.cso.uiuc.edu!dan
From: [email protected] (Greg Kuperberg)
Subject: Re: Tiling/Combinatorics puzzle
Approved: Daniel Grayson <[email protected]>
Date: Wed, 2 Jun 1993 00:31:19 GMT
Message-ID: <[email protected]>
References: <[email protected]> <[email protected]> <[email protected]>
X-Char-Esc: 29
Sender: Daniel Grayson <[email protected]>
Keywords: algebraic combinatorics, domino tilings, matching, permanent/determinant trick
Reply-To: [email protected]
X-Charset: LATIN1
Originator: [email protected]
Organization: University of Chicago
Lines: 36

In article <[email protected]> [email protected] (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 1022 of sci.math.research:
Newsgroups: sci.math.research
Path: e2big.mko.dec.com!dbased.nuo.dec.com!pa.dec.com!decwrl!wupost!howland.reston.ans.net!ux1.cso.uiuc.edu!news.cso.uiuc.edu!dan
From: [email protected] (Philippe AIGRAIN)
Subject: Re: Tiling/Combinatorics puzzle
Approved: Daniel Grayson <[email protected]>
Date: Thu, 3 Jun 1993 08:46:53 GMT
Message-ID: <[email protected]>
References: <[email protected]> <[email protected]> <[email protected]> <[email protected]>
X-Char-Esc: 29
Sender: Daniel Grayson <[email protected]>
X-Charset: LATIN1
Originator: [email protected]
Organization: IRIT-UPS, Toulouse, France
Lines: 50

In article <[email protected]>, [email protected] (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 1027 of sci.math.research:
Newsgroups: sci.math.research
Path: e2big.mko.dec.com!pa.dec.com!decwrl!concert!gatech!howland.reston.ans.net!ux1.cso.uiuc.edu!news.cso.uiuc.edu!dan
From: [email protected] ( Torsten Sillke)
Subject: Re: Tiling/Combinatorics puzzle
Approved: Daniel Grayson <[email protected]>
Date: Thu, 3 Jun 1993 16:57:18 GMT
Message-ID: <[email protected]>
References: <[email protected]> <[email protected]> <[email protected]> <[email protected]>
X-Char-Esc: 29
Sender: Daniel Grayson <[email protected]>
Keywords: tilings, hexagonal systems, dominoes, perfect matchings
X-Charset: LATIN1
Originator: [email protected]
Organization: Universitaet Bielefeld, Rechenzentrum
Lines: 151

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

[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     ]

------------------------------------------------------
Example for the number of tilings of the 5*6 board:
Orient the edges of the 5*6 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  *


  Number of perfect matchings = Abs Determinat M

    M[i,j] = number of pathes from p[i] to v[j].

  In the example:
                     [  52  39  ]
                 M = [          ]
                     [  39  52  ] 

          Det M = 1183
--------------------------------------------------------------

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 1031 of sci.math.research:
Newsgroups: sci.math.research
Path: e2big.mko.dec.com!pa.dec.com!decwrl!concert!news-feed-1.peachnet.edu!gatech!howland.reston.ans.net!ux1.cso.uiuc.edu!news.cso.uiuc.edu!dan
From: [email protected] (Greg Kuperberg)
Subject: Re: Tiling/Combinatorics puzzle
Approved: Daniel Grayson <[email protected]>
Date: Fri, 4 Jun 1993 02:02:51 GMT
Message-ID: <[email protected]>
References: <[email protected]> <[email protected]> <[email protected]>
X-Char-Esc: 29
Sender: Daniel Grayson <[email protected]>
Keywords: tilings, hexagonal systems, dominoes, perfect matchings
Reply-To: [email protected]
X-Charset: LATIN1
Originator: [email protected]
Organization: University of Chicago
Lines: 80

In article <[email protected]> [email protected] ( 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.

Article 1037 of sci.math.research:
Newsgroups: sci.math.research
Path: e2big.mko.dec.com!uvo.dec.com!news.crl.dec.com!deccrl!decwrl!decwrl!sdd.hp.com!ux1.cso.uiuc.edu!news.cso.uiuc.edu!dan
From: [email protected] ( Torsten Sillke)
Subject: Re: Tiling/Combinatorics puzzle
Approved: Daniel Grayson <[email protected]>
Date: Tue, 8 Jun 1993 10:39:45 GMT
Message-ID: <[email protected]>
References: <[email protected]> <[email protected]> <[email protected]> <[email protected]>
X-Char-Esc: 29
Sender: Daniel Grayson <[email protected]>
Keywords: tilings, hexagonal systems, dominoes, perfect matchings
X-Charset: LATIN1
Originator: [email protected]
Organization: Universitaet Bielefeld, Rechenzentrum
Lines: 23

>
>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].


 [1] David; Tomei,
         The problem of the calissons, AMM 96 (1989) 429-431 
         [ They give a bijection: 
           (n,n,n) hexagonal tilings <-> (n,n,n) plane partitions. ]

 [2] 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 ]

Torsten Sillke

Article 1045 of sci.math.research:
Newsgroups: sci.math.research
Path: e2big.mko.dec.com!pa.dec.com!decwrl!olivea!spool.mu.edu!howland.reston.ans.net!ux1.cso.uiuc.edu!news.cso.uiuc.edu!dan
From: [email protected] (Greg Kuperberg)
Subject: Re: Tiling/Combinatorics puzzle
Approved: Daniel Grayson <[email protected]>
Date: Thu, 10 Jun 1993 03:29:22 GMT
Message-ID: <[email protected]>
References: <[email protected]> <[email protected]> <[email protected]>
X-Char-Esc: 29
Sender: Daniel Grayson <[email protected]>
Keywords: tilings, hexagonal systems, dominoes, perfect matchings
Reply-To: [email protected]
X-Charset: LATIN1
Originator: [email protected]
Organization: University of Chicago
Lines: 49

In article <[email protected]> [email protected] ( 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.