Automatic CounTilings

By Doron Zeilberger

.pdf   .ps   .tex  
Written: Jan. 20, 2006.
published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger and copublished (July 2009) in Rejecta Mathematica
This is yet another exercise in "symbol crunching". What is so nice about it is that everything is done by machine: the combinatorics, the algebra, and the analysis. Enjoy! If I had Maple and this package back in 1960 I might have scooped Kasteleyn and Fisher&Temperley.
Important: This article is accompanied by Maple package TILINGS that automatically computes generating functions for the enumerating sequences of tilings of fixed-width rectangular boards with an arbitrary set of tiles, and also does "statistical processing". See also the precursor package, RecTILINGS that only handles rectangular tiles.

Sample Input and Output

  • For the generating functions, first few terms, and asymptotic statistics for the classical dimer problem (with the two domino tiles) for tiling rectangular boards of width 2,4,6,8,
    the input yields the output.
  • For the generating functions, first few terms, and asymptotic statistics for the monomer-dimer problem (with the two domino tiles as well as a monomer (1x1) tile ) for tiling rectangular boards of width 2,3,4,5,
    the input yields the output.
  • For the generating functions, first few terms, and asymptotic statistics for tilings with the set of tiles consisting of a monomer (1x1), the two dimers (1x2 and 2x1) and the 2x2 tiles, for tiling rectangular boards of width 2,3,4
    the input yields the output.
  • For the generating functions, first few terms, and asymptotic growth of tilings with the set of tiles consisting of a monomer (1x1), and the 1x3 and 3x1 tiles, for tiling rectangular boards of width 1,2,3,4,5
    the input yields the output.
  • To prove Kasteleyn's famous formula (straight enumeration version) for m=2,4,6,8,10, but ALL n,
    the input yields the output.
Added April 14, 2006: This article was submitted to Journal of Combinatorial Theory Series A, and was stupidly rejected by its Managing Editor, Helene Barcelo, and the members of its Advisory Board, that includes, surprisingly and sadly, Tiling expert Mireille Bousquet-Melou. Read the Narrow-Minded and Ignorant Referee's Report and my response .

Luckily, nowadays, publishing in a "real" journal is really only a formality, and this masterpiece is hence published in this Personal Journal.

Added July 24, 2006: Read Renzo Sprugnoli's interesting message
Personal Journal of Ekhad and Zeilberger

Doron Zeilberger's Home Page