Automatic Enumeration of Tilings by Polyominoes

Lucy Martinez

Automatic Enumeration of Tilings by Polyominoes

T0 review · 4 major / 4 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper demonstrates that an automated transfer-matrix enumeration program yields exact rational generating functions and recurrences for tilings of k×n boards by L-tetrominoes for widths 5 through 9.

desk verdict Zeilberger's package recovers the known k=4 case, then produces genuinely new L-tetromino data for widths 5–9, but every displayed recurrence is off by one at the boundary and the promised k=9 generating function never appears. read the letter →

arxiv 2607.29369 v2 pith:UVWZNHQJ submitted 2026-07-31 math.CO

Lucy Martinez This is my paper · ORCID

classification math.CO MSC 05B4505A1511B37

keywords polyominotilingsL-tetrominotransfer-matrixmethodgeneratingfunctionslinearrecurrencesrectangularboardsrationalautomaticenumeration

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper argues that an automated transfer-matrix enumeration program—rather than hand-built case analysis—can count tilings of rectangular boards by L-tetrominoes for several widths at once. The main new results are exact rational generating functions and linear recurrences for the numbers of tilings of k×n boards with k=5,6,7,8,9, allowing rotations but not reflections. For example, the number of tilings of a 5×8n board satisfies a_n = 2a_{n−1}+4a_{n−2}+4a_{n−3}+4a_{n−4}. The paper first checks the method by automatically recovering a recently published generating function for the 4×2n case, then reports sequences for the wider boards that are not currently listed in standard integer-sequence databases. The contribution is a uniform computational route to exact, previously unlisted tiling counts.

What carries the argument

The engine is a transfer-matrix construction over a fixed-width board. Each tile is stored as a normalized set of lattice points, and the tiling is built column by column; the state at each step records which cells of the current column are already occupied by tiles protruding from the left. The program assembles a finite linear system whose variables are generating functions for the original board and for auxiliary jagged boards, solves the system symbolically, and reads off a rational generating function and hence a linear recurrence. For L-tetrominoes the tile set consists of the four rotations of the L-shaped tile, and the correctness of the method is first checked against the known 4×2n

What would settle it

Compute the first several coefficients of any reported generating function—for instance, the 5×8n sequence 1,2,7,24,86,304,1076,3808—by an independent exhaustive tiling enumeration of the corresponding boards; a single mismatch (such as a 5×16 board admitting other than 7 tilings) would falsify the paper's claim for that width.

Watch

Extended reading notes

Core claim

The central claim is that an automated tiling-enumeration framework, which sets up a finite system of linear equations for a rectangular board and its auxiliary jagged boards, solves the system symbolically, and converts rational generating functions into recurrences, correctly enumerates L-tetromino tilings for widths 5 through 9. For 5×8n boards the framework gives the rational generating function (2t^4+2t^3+t^2−1)/(4t^4+4t^3+4t^2+2t−1) and the linear recurrence a_n = 2a_{n−1}+4a_{n−2}+4a_{n−3}+4a_{n−4}, starting from a_0=1, a_1=2, a_2=7, a_3=24. Propositions 6–8 state analogous generating functions for 6×4n, 7×8n, 8×n, and 9×8n boards. The paper verifies the framework by reproducing the k

Load-bearing premise

The load-bearing premise is the correctness of the automated transfer-matrix implementation for widths 5 through 9; if the program makes an error in building or solving its state equations at any of these widths, every new formula and sequence in the paper would be wrong.

Editorial extensions

If this is right

Exact formulas now exist for L-tetromino tilings of five new board families: the paper supplies generating functions and recurrences for widths 5 through 9, with the 5×8n recurrence explicitly a_n = 2a_{n−1}+4a_{n−2}+4a_{n−3}+4a_{n−4}.
The resulting integer sequences are not currently listed in standard sequence databases, so the paper extends the available enumeration data for polyomino tilings.
Because every generating function is rational with an explicit denominator, each sequence can be generated rapidly to arbitrary length by the corresponding linear recurrence.
The framework is not limited to the L-tetromino: it handles arbitrary tile sets, including reflected tiles and other free polyominoes, and can in principle reach widths up to at least 16.
The auxiliary files accompanying the paper also record asymptotics for the listed sequences, so growth estimates are part of the output.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The width-8 L-tetromino sequence, with zeros at odd n, suggests geometric tilability conditions that could be isolated by analyzing when the state system forces zero coefficients; such a divisibility criterion would complement the enumeration results.
An independent brute-force enumerator for small n at each new width would provide a cheap check that the transfer-matrix outputs are exact, since the paper presents the new propositions as program outputs rather than formal proofs.
The same transfer-matrix tool could be run on other tetromino classes under rotations, or on L-tetrominoes with reflections allowed, to see which families yield low-order rational generating functions and which exhibit irregular zero patterns.
For widths beyond 9, the state space grows quickly; a testable extension would be to compare the automatic generating function with coefficients from dynamic programming at moderate n, mapping the practical limits of the method.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Zeilberger's 2006 transfer-matrix package does recover the Bělohoubek–Slavík generating function for the 4×2n L-tetromino case, and the paper then applies the same crank to widths 5–9. The width-5 through width-8 generating functions in Appendix A.2 and the sequences in Table 3 are new as far as I can tell, and the T-tetromino outputs match Merino's table. The exposition is clear about what is program output and what is proof, and the code is on GitHub. This is an honest, useful computational data paper.

The soft spots, in order. First, every displayed recurrence has the same boundary error. Proposition 2 states a_n = 2a_{n−1}+4a_{n−2}+4a_{n−3}+4a_{n−4} for n≥4, but that recurrence with the stated initial values gives a_4 = 88, while the generating function expands to 86. The correct bound is n≥5. The same off-by-one appears in Propositions 3 and 4, and presumably throughout the appendix. This does not invalidate the generating functions — I checked the expansions and the GFs are consistent with their listed first terms — but it means the manuscript was never checked against its own formulas.

Second, the load-bearing new results, the L-tetromino generating functions for widths 5–9, have no independent verification. The k=4 recovery is a good sanity check, but a state-equation bug for the new widths would silently change every new sequence, and the recurrence errors make it harder to take unverified program output at face value.

Third, the k=9 generating function promised in the abstract, Table 3, and the appendix's own description is absent from Appendix A.2; the largest new sequence has no formula to verify. Minor: the OEIS "new" claims lack search details, and the zero-laden k=8 sequence deserves a comment on whether it is a subsequence of something known.

This paper is for combinatorialists who work on polyomino tilings and want exact sequences for OEIS or bijective work. It is an extension of a known method, not a conceptual advance, but the data is genuinely new, and the benchmark-then-extend approach is right. It deserves peer review, on the condition that the author fixes the recurrence bounds, supplies the k=9 generating function, and adds an independent check (a second implementation or a machine-checked certificate) for the new widths. I would not desk-reject it.

Referee Report

4 major / 4 minor

Summary. The paper revisits Zeilberger's Maple-based transfer-matrix method for automatic enumeration of polyomino tilings and applies it to L-tetromino tilings of k×n boards. It first recovers the known generating function for 4×2n boards (Bělohoubek–Slavík), then reports rational generating functions and integer sequences for widths k=5,...,9, several claimed new to the OEIS. T-tetromino results for widths 8, 12, 16 are also computed and agree with Merino. The stated contribution is computational: explicit generating functions, recurrences, and new sequences, with code available on GitHub.

Significance. If the reported outputs are correct, the paper provides a useful demonstration of Zeilberger's automated enumeration framework and supplies explicit exact results for previously unlisted L-tetromino tiling sequences. The recovery of the known 4×2n L-tetromino result and Merino's T-tetromino sequences gives positive evidence that the pipeline is sound. However, the new results are not yet trustworthy: three of the displayed generating functions have a sign error (constant term −1 instead of 1), three recurrence statements have off-by-one validity bounds, and the k=9 generating function promised in the appendix is missing. These errors are fixable, but they must be corrected and independently checked before the central claims can be accepted.

major comments (4)

[Appendix A.2, Propositions 6–8] The displayed generating functions are not the generating functions of the stated sequences. In Proposition 6, A(t) has constant term −1 and B(t) has constant term 1, so A(0)/B(0) = −1, whereas the sequence has a0=1. Expanding the displayed ratio gives −1,−5,... rather than 1,5,34,... . The correct GF is −A(t)/B(t). In Propositions 7 and 8, A(0)=1 and B(0)=−1, so A(0)/B(0)=−1 as well; the correct GF is A(t)/(−B(t)). These are load-bearing sign errors: every displayed new L-tetromino GF in the appendix is wrong as printed.
[Propositions 2–4] The stated recurrence bounds contradict the displayed generating functions. For Proposition 2, the GF expands to a4=86, while the recurrence a_n=2a_{n−1}+4a_{n−2}+4a_{n−3}+4a_{n−4} with n≥4 and the given initial values gives a4=88; the correct bound is n≥5. For Proposition 3, n≥2 gives a2=69 but the GF gives a2=84; the correct bound is n≥3. For Proposition 4, n≥4 gives a4=5,249,205 but the GF gives a4=5,253,822; the correct bound is n≥5. The initial-value lists must also include the first term needed for the corrected recurrence.
[Appendix A.2 / Table 3] Table 3 lists the sequence for 9×8n boards, and the text says 'the corresponding generating functions for each case are listed in Appendix A.2.' However, Appendix A.2 contains Propositions 6–8 only; there is no generating function for k=9. Since this is the largest new width in the paper's main table, the omission is material. Please add the GF or clearly state that it is only in the repository and amend the text accordingly.
[General verification] The new L-tetromino generating functions are asserted as direct outputs of Zeilberger's Maple package. The only reported checks are recovery of the known 4×2n L-tetromino GF and agreement with Merino's T-tetromino sequences. Given the sign and boundary errors above, these checks are insufficient for the new widths. I request an explicit machine-checkable verification for each new GF and recurrence, e.g., a worksheet that expands the GF to the first 20 coefficients and compares with a direct transfer-matrix or backtracking enumeration for small n, plus a script verifying each recurrence against its GF.

minor comments (4)

[§2.1] Citation error: 'See Elkies et al. [2]' should cite reference [3], not [2].
[Propositions 6–8] The generating functions should be given in normalized form with constant term 1 in the denominator; the current sign presentation makes it very easy to misread the outputs.
[Table 3] The definition of the 'smallest scaling factor' is informal. For k=8 the sequence still contains zero terms, so the criterion needs to be stated more carefully.
[Propositions 2–4] For the corrected recurrences, list all initial values actually needed (e.g., Proposition 2 should include a4=86 alongside a0,...,a3).

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the new generating functions are produced by Zeilberger's transfer-matrix program and benchmarked against independent published results, with no fitted parameters or target results fed into the computation.

full rationale

The derivation chain is self-contained. In Section 2.2, the author runs Zeilberger's Maple transfer-matrix package on the L-tetromino tile set and first recovers the Bělohoubek–Slavík generating function (1−z^2)/(z^4+z^3−3z^2−z+1) as a validation step, then applies the same program to widths 5 through 9. No free parameter is fitted to the new sequences, and no definition (e.g., GF_t(k,T,t)) presupposes the reported answers. The new rational generating functions are program outputs checked against the previously published 2n×4 case and against Merino's T-tetromino values, so the method has external support. The off-by-one recurrence bounds in Propositions 2–4 are presentation errors that affect the stated recurrences, but they do not make any result circular. The missing 9×8n generating function in Appendix A.2 is a completeness issue, not a circularity. Zeilberger's framework is cited, but its output is independently benchmarked here, so the self-citation is not load-bearing in the circular sense. No circular step can be exhibited from the paper's own equations.

Assumptions & free parameters 1 free parameters · 3 assumptions · 0 invented entities

The computations involve no fitted constants or invented entities. The hand-chosen scaling factors c_k only select the subsequence reported, not the enumeration. The key unproved premise is the correctness of the transfer-matrix implementation, plus the OEIS search being current.

free parameters (1)

scaling factors c_k for L-tetromino sequences = k=4: c=2; k=5: c=8; k=6: c=4; k=7: c=8; k=8: c=1; k=9: c=8
Chosen in Section 2.2/Table 3 as the smallest positive integer such that T_k(c n) has no zero terms; affects which subsequence is presented as the 'sequence' but not the transfer-matrix computation itself.

assumptions (3)

domain assumption Zeilberger's transfer-matrix construction (jagged-boundary states) yields a finite linear system whose solution is the exact tiling generating function.
Invoked in Section 2; not proved here, but standard and benchmarked against the known k=4 case.
domain assumption The Maple implementation (Zeilberger's package plus the author's scripts) executes this construction without error.
All new results in Appendix A.2 depend on this; code link [8] is given but no commit hash or machine check is provided.
domain assumption The OEIS search accurately reflects all prior listing of these sequences.
Table 3 'New' labels rely on OEIS absence; the cited OEIS reference is dated 2023 while the paper is from 2026, and no search date/query is stated.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Automatic Enumeration of Tilings by Polyominoes." pith.science (2026). https://pith.science/paper/UVWZNHQJ

@misc{pith2026260729369,
  author       = {Pith},
  title        = {Pith review of: Automatic Enumeration of Tilings by Polyominoes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UVWZNHQJ}},
  note         = {Machine review of arXiv:2607.29369}
}

abstract

We revisit Zeilberger's computational framework for enumerating polyomino tilings and demonstrate its use in counting tilings of $k\times n$ boards by $L$-tetrominoes, allowing rotations. Recently, B\v{e}lohoubek and Slav\'ik gave a generating function for tilings of $2n\times 4$ boards by $L$-tetrominoes. Motivated by their work, we first verify the method by automatically recovering their generating function. We then apply the method to widths $5$ through $9$ and obtain explicit rational generating functions and new integer sequences that are not currently listed in the OEIS.