Cutting 4 by n grids into two congruent pieces Robert Dougherty-Bliss, Natalya Ter-Saakov, and Doron Zeilberger

Pour Jean-Paul Delahaye, avec admiration Introduction In the March 2025 issue of Pour La Science (the French analog of Scientific American), in his delightful monthly column [D], Jean-Paul Delahaye described in detail the solution of the following counting problem. In how many ways can you cut a 3 × 2n rectangle consisting of 6n unit squares (in other words a 3 × 2n (colorless) checkerboard) into two connected congruent pieces? In collaboration with his épouse, Martine Raison, they used human ingenuity to prove that this number is given explicitly by the beautiful formula 2^{n+1} − n − 1. We asked ourselves, what about a 4 × n checkerboard? Now human ingenuity is still necessary, but (most probably) not sufficient. In collaboration with our beloved silicon friends we proved the following deep theorem. Theorem 1: Let c_{n} be the number of ways of cutting a 4 × n grid into two (connected) congruent pieces, then the (ordinary) generating function is:

∑_{n=0}^{∞} c_{n}x^{n} = \frac{x (2x^{8} − 4x^{7} + 8x^{6} − 7x^{5} + 3x^{4} + 2x^{3} − 5x^{2} + x + 1)}{(x − 1)^{2} (x^{4} + 3x^{2} − 1) (x^{4} + 2x^{2} − 1)} .

For the sake of the OEIS the first 30 terms are: 1, 3, 5, 14, 22, 54, 84, 197, 305, 696, 1075, 2410, 3716, 8231, 12676, 27844, 42843, 93558, 143865, 312859, 480868,

1042624, 1602002, 3466064, 5324385, 11501987, 17665729, 38119718, 58540246, 126217718 . To our delight, this sequence was not (viewed Sept. 4, 2025) in the OEIS, and we hope to submit it soon. A convenient way to represent such decoupages into congruent pieces is via 4 × n 0 − 1 matrices, where because of symmetry we assume that the last entry of the first row is always 1. There are \binom{4n−1}{2n−1} such candidate matrices (without the conditions of connectivity and congruence), but most of them do not obey the condition. From now on we will call them good martices. Here is one of the 54 such 4 × 6 good matrices:

[ \begin{matrix}0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 \end{matrix} ] ,

and here is one of the 696 such 4 × 10 good matrices:

[ \begin{matrix}0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \end{matrix} ] .

To see all good matrices 4 × n matrices for 1 ≤ n ≤ 12 see the output file:

https://sites.math.rutgers.edu/~zeilberg/tokhniot/oDecoupage1.txt .

It is easy to see that any such good matrix must start with a zeroes followed by n − a ones, where 0 ≤ a ≤ ⌊n/2⌋. We also have the more detailed theorem. Theorem 2: Let f_{a}(x) be the coefficient of z^{a} in the Maclaurin expansion (with respect to the variable z) of the rational function

\frac{−x^{3} − x^{2} + x + 1 + (x^{5} + 2x^{3} − x^{2} − x) z + (x^{4} − x^{3} + 2x^{2} − 1) z^{2}}{z^{3} + z^{2} − 3z + 1}

then the number of 4 × n good matrices whose first row starts with a consecutive zeroes (and hence ends with n − a consecutive ones) is the coefficient of x^{n} in the Maclaurin expansion of the rational function

\frac{x^{2a}f_{a}(x)}{(x − 1) (x^{4} + 3x^{2} − 1)} .

Note that if we drop the condition of the two pieces being congruent, and consider only square matrices, then we have the (computationally) challenging problem of the Gerrymeander sequence [Sl] , beautifully treated in [KKS] and extended in [GJ]. Maple Package This article is accompanied by a Maple package Decoupage.txt that can be gotten from

https://sites.math.rutgers.edu/~zeilberg/tokhniot/Decoupage.txt .

The front of this article

https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/decoupage.html contains

some sample output files. How did we find this beautiful Generating function? We asked our computer to show us all these creatures up to n = 12. We stared at them and tried to guess a grammar. It was very reasonable to expect a type 3 grammar, also known as finite state machine, with starting states and accepting states, and ‘transitions edges’ in a certain finite alphabet. Once we had the grammar, we (or rather our computer) could easily find the transfer matrix and, in turn, using symbolic computation, usig that very useful took-of-the-trade called the transfer matrix method ([St], section 4.7) derive the desired generating function.

We will now actually describe the grammar.

NATASHA and ROBERT YOUR PART

Future work

What about the analogous problem of 5 × 2n, 6 × n, 7 × 2n, 8 × n checkerboards? Eventually it would be nice to have the computer do everything, i.e. discover the grammar, and then process it all by itself without any need of human ingenuity. But even computers can only go so far, and we are sure that humankind, and even computerkind will never have the generating function (most probably a rational function) for the sequence counting 30 × n good matrices.

References

[D] Jean-Paul Delahaye, Combinatoire pour les rectangles, Logique & Calcul, Pour La Science No. 569, Mars 2025.

[GJ] Anthony J. Guttmann and Iwan Jensen, The gerrymander sequence, or A348456, arXiv:2211.14482

[math.CO], 2022. https://arxiv.org/abs/2211.14482 .

[KKS] Manuel Kauers, Christoph Koutschan, and George Spahn, How Does the Gerrymander Sequence Continue?, J. Int. Seq., 25 (2022), Article 22.9.7.

https://cs.uwaterloo.ca/journals/JIS/VOL25/Kauers/kauers6.html.
arxiv version: https://arxiv.org/abs/2209.01787 .

[Sl] Neil Sloane, OEIS sequence A348456 https://oeis.org/A348456.

[St] Richard P. Stanley,“Enumerative Combinatorics”, Volume 1, Cambridge University Press, First Edition, Wadsworth and Brooks/Cole, 1986.

Robert Dougherty-Bliss, Department of Mathematics, Dartmouth College, 29 N. Main Street, 6188 Kemeny Hall, Hanover NH 03755-3551 . Email: robert dot w dot bliss at gmail dot com

Natalya Ter-Saakov, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: nt399 at rutgers dot edu .

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: DoronZeil at gmail dot com .

Sept. 10, 2025 4