Counting Divisions of a 2 × n Rectangular Grid

DOI10.1080/07468342.2023.2201166MaRDI QIDQ6166771zbMATH OpenOpenAlexFDO

Authors

Publication date 6 July 2023

Published in The College Mathematics Journal (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2106.14755

Mathematics Subject Classification ID

Combinatorics (05-XX) Computer science (68-XX)

Abstract: Consider a $2imesn$ rectangular grid composed of $1imes1$ squares. Cutting only along the edges between squares, how many ways are there to divide the board into $k$ pieces? Building off the work of Durham and Richmond, who found the closed-form solutions for the number of divisions into 2 and 3 pieces, we prove a recursive relationship that counts the number of divisions of the board into $k$ pieces. Using this recursion, we obtain closed-form solutions for the number of divisions for $k=4$ and $k=5$ using fitting techniques on data generated from the recursion. Furthermore, we show that the closed-form solution for any fixed $k$ must be a polynomial on $n$ with degree $2k-2$.

Recommendations

• Some formulas for numbers of line segments and lines in a rectangular grid.
• scientific article; zbMATH DE number 4075941
• Connected subsets of an \(n\times 2\) rectangle
• Counting \(1\times 2\) rectangles in set partitions
• scientific article; zbMATH DE number 749666

Cites work

• A Primer on Bernoulli Numbers and Polynomials
• A simple derivation of Faulhaber's formula
• Connected subsets of an \(n\times 2\) rectangle
• Counting Connected Sets of Squares

Cited in

(4)

• On the number of tiles visited by a line segment on a rectangular grid
• scientific article; zbMATH DE number 3884166 (Why is no real title available?)
• scientific article; zbMATH DE number 3841867 (Why is no real title available?)
• Splitting numbers of grids

This page was built for publication: Counting Divisions of a 2 × n Rectangular Grid

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6166771)