Counting Divisions of a 2 × n Rectangular Grid

DOI10.1080/07468342.2023.2201166arXiv2106.14755OpenAlexW4367836724MaRDI QIDQ6166771FDOQ6166771

Authors:

Publication date: 6 July 2023

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

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$.

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• Title not available (Why is that?)
• Title not available (Why is that?)
• On the number of tiles visited by a line segment on a rectangular grid
• 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)