In How Many Ways can a Rectangle be Rectangled?

In How Many Ways can a Rectangle be Rectangled?
By Pablo Blanco, Robert Dougherty-Bliss, Natalya Ter-Saakov, and Doron Zeilberger
.pdf .tex

Posted: June 3, 2026

We teach the computer (in two different ways!) how to discover a "grammar" for the "language" of tilings a rectangular grid (of a fixed width but of any length) by rectangles, that enable fast and efficient enumeration of these tilings. More impressively, we use the same grammar to weight-enumerate them according to the number of tiles and the number of participating edges.
This paper was inspired by the Recto puzzles, composed by Prasanna Seshadri, that appeared (March-May 2026) in the New York Times Sunday magazine.
[ Here is a collage of some sample puzzles.]

Maple packages

RectTile.txt, A Maple package to compute generating functions for enumerating tilings of a rectangle by rectangular tiles. Also by square tiles.

Recto.txt, A Maple package to create and solve Recto puzzles. It was used to create this Recto Puzzle Book

Sample Input and Output for RectTile.txt

If you want to see the generating functions for enumerating of an m by n rectangle into rectangular tiles, for m from 1 to 6, using the GRAMMAR
the input file produces output file

If you want to see the generating functions for enumerating of an m by n rectangle into rectangular tiles, for m from 1 to 9, using the Joshua Smith and Helena Verrill approach
the input file produces output file

If you want to see the generating functions for enumerating of an m by n rectangle into rectangular tiles, for m from 1 to 5, using GUESSING
the input file produces output file

If you want to see the generating functions for enumerating of an m by n rectangle into SQUARE tiles, for m from 1 to 9, using GUESSING
the input file produces output file

If you want to see the generating functions for weight-enumerating of an m by n rectangle into RECTANGULAR tiles, according to the weight w^{NumberOfEdges} for m from 1 to 6
the input file produces output file
If you want to see the generating functions for weight-enumerating of an m by n rectangle into RECTANGULAR tiles, according to the weight t^{NumberOfTiles} for m from 1 to 6
the input file produces output file
If you want to see the Tri-Variate generating functions for weight-enumerating of an m by n rectangle into RECTANGULAR tiles, according to the weight
w1^{NumberOfHorizontalTiles}*w2^{NumberOfVerticalTiles} for m from 1 to 5
the input file produces output file
If you want to see a short article about the asymptotics of the expectation and variance for the number of participating edges for tilings of an m by n rectangle by rectangular tiles for m from 1 to 6;
followed by a a short article about the asymptotics of the expectation and variance for the number of participating tiles for
followed by a a short article about the limit of the correlation coefficient between the number of horizontal edges and number of vertical edges, tilings of an m by n rectangle by rectangular tiles for m from 2 to 5:
the input file produces output file

Sample Input and Output for Recto.txt

If you want to see an example of a solution of puzzle that appeared in the New York Times (where one is looking for just one solution) the input file produces output file

If you want to see an example of a solution of puzzle that appeared in the New York Times (where one is looking for all solutions) the input file produces output file

Articles of Doron Zeilberger
Pablo Blanco's Home Page
Robert Dougherty-Bliss's Home Page
Natalya Ter-Saakov's Home Page
Doron Zeilberger's Home Page