Automatic Counting of Tilings of Skinny Plane Regions

By
Shalosh B. Ekhad and Doron Zeilberger

.pdf   .ps   .tex

Written: June 21, 2012

Appeared in "Surveys in Combinatorics 2013", edited by Simon R. Blackburn, Stefanie Gerke, and Mark Wildon, London Mathematical Society Lecture Notes Series #409, 363-378.
(Proceedings of the 24th British Combinatorial Conference)
The deductive method ruled mathematics for the last 2500 years, now it is the turn of the inductive method.

# Maple Packages

• RITSUF, for straight-counting

• RITSUFwt, for weighted-counting
[it also contains everything in RITSUF]

• ARGF, for Analyazing (statistically) Rational Generating Functions of combinatorial families

# Web-books from the Maple package RITSUF

• If you want to see how Shalosh discovered (and proved!), (in 0.287 seconds!) the solution to Math. Magazine problem #1868, that asked for the number of ways of tiling with 4n+8 dominoes the region in the discrete plane obtained by removing from the (n+4) by (n+4) square the central nxn square, proposed by CS Giant Don Knuth in the April 2011 issue, that, as it turned out, was already proposed and solved, in 2004, by the human Roberto Tauraso, in Theorem 2.2. of J. Integer of Sequence Article 04.2.3

the input file would yield the output file

• If you want to see the analogous theorems for the number of ways of tiling with 4an+2a2 dominoes the region in the discrete plane obtained by removing from the (n+2a) by (n+2a) square the central n by n square, from a=1 (even you can do it!) to a=6 (not even Knuth can do it (by hand))

the input file would yield the output file

• If you want to see 150 deep theorems about the number of ways of tiling with dominoes (also called dimers) the region in the discrete plane obtained by removing from the (c1+n+c2) by (d1+n+d2) rectangle the central n by n square for 1 ≤ c1,c2,d1,d2 ≤ 4,

the input file would yield the output file

• If you want to see 38 deep theorems about the number of ways of tiling with MONOMERS and DIMERS the region in the discrete plane obtained by removing from the (c1+n+c2) by (d1+n+d2) rectangle the central n by n square for many cases of 1 ≤ c1,c2,d1,d2 ≤ 3,

the input file would yield the output file

• If you want to see explicit expressions for the number of ways of DOMINO-tilings crosses whose central square is a 2 by 2 square and a 4 by 4 square, and that have equal arms of length n, for all n,

the input file would yield the output file

• If you want to see explicit expressions for the number of ways of DOMINO-tilings of crosses whose central rectangle has side-lengths up to 4, and that have equal arms of length n, for all n,

the input file would yield the output file

• If you want to see explicit expressions for the number of ways of MONOMER-DIMER tiling crosses for 1 by 1, 1 by 2, 1 by 3, and 2 by 2 rectangles, and that have equal arms of length n, for all n,

the input file would yield the output file

• If you want to see generating functions for the sequences enumerating the number of DIMER (i.e. domino) tilings of a by n (or a by 2n, if a is odd) for a from 1 to 9, then

the input file would yield the output file

• If you want to see generating functions for the sequences enumerating the number of MONOMER-DIMER (i.e. domino) tilings of a by n for a from 1 to 7, then

the input file would yield the output file

• If you want to see 81 deep theorems (rigorously proved!) giving the BI-VARIATE generating functions for the number of DIMER (domino) tilings the region in the plane obtained by removing from the c + m + c, by , d + n + d rectangle the central m by n rectangle, for 1 ≤ c,c,d,d ≤ 3

the input file would yield the output file

• If you want to see 81 deep theorems (rigorously proved!) giving the BI-VARIATE generating functions for the number of MONOMER-DIMER tilings the region in the plane obtained by removing from the c + m + c, by , d + n + d rectangle the central m by n rectangle, for 1 ≤ c,c,d,d ≤ 3

the input file would yield the output file

# Web-books from the Maple package RITSUFwt

• If you want to see how Shalosh discovered (and proved!) the (much harder!) weighted analog of Math. Magazine problem #1868, that finds the generating function for the weight-enumerator of the set of tilings with 4n dominoes the region in the discrete plane obtained by removing from the (n+4) by (n+4) square the central nxn square,where the weight of a tiling is h raised to the power the number of horizintal tiles, In other words the coefficient of tnhi of the outputed rational function gives you the exact number of tilings of the region with exactly i horizontal tiles, and also finds out that the average is n+2 (that's trivial, even you can do it, dear human!), and the asymptotic variance, and higher moments

the input file would yield the output file

• If you want to see 12 deep theorems about the weight-enumerator (according to the weight "h to the power of the nuber of horizontal tiles") of the set of tilings with dominoes (also called dimers) the region in the discrete plane obtained by removing from the (c1+n+c2) by (d1+n+d2) rectangle the central n by n square for 1 ≤ c1,c2,d1,d2 ≤ 2,

the input file would yield the output file

• If you want to see 41 deep theorems (that include the 12 previous ones) about the weight-enumerator (according to the weight "h to the power of the nuber of horizontal tiles") of the set of tilings with dominoes (also called dimers) the region in the discrete plane obtained by removing from the (c1+n+c2) by (d1+n+d2) rectangle the central n by n square for 1 ≤ c1,c2,d1,d2 ≤ 3, for many cases (but not all) [COMPLETE WITH STATISTICAL ANALYSIS]

the input file would yield the output file

• If you want do see the generating functions (in the variable t), of the sequences of weight-enumerators for dimer (domino) tilings of the a by n rectangles for a from 2 to 8 (the coeff. of tn in the Maclaurin expansion would be the weight-enumerator of tilings of an a by n rectangle according to the weight hNumberOfHorizontalTiles) and ALSO fascinating STATISTICAL ANALYSIS of the random variable "number of horizontal tiles" (confirming, empirically, the well-known fact that it is asymptotically normal, but also giving more accurate asymptotics for the alpha coefficients for the first eight of them)

the input file would yield the output file

• If you want do see the generating functions (in the variable t), of the sequences of weight-enumerators for dimer (domino) tilings of the a by n rectangles for a from 2 to 5 (the coeff. of tn in the Maclaurin expansion would be the weight-enumerator of tilings of an a by n rectangle according to the weight hNumberOfHorizontalTiles) and ALSO fascinating STATISTICAL ANALYSIS of the random variable "number of horizontal tiles" with EXPLICIT Expressions for the average, variance, and the so-called alpha coefficients (confirming, RIGOROUSLY, the well-known fact that it is asymptotically normal, but also giving more accurate (symbolic!) asymptotics for the alpha coefficients)

the input file would yield the output file

Articles of Doron Zeilberger