2021/06/28 by Jacob Brown, Brown, Jacob
Computer Science · Mathematics · #05A18 #Algorithms and Data Compression #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Stochastic processes and statistical mechanics #math.CO #msc:05A18
paper · pdf · doi:10.48550/arxiv.2106.14755
9 pages, 5 figures
openalex publication_date 2021/06/28 · arxiv created 2021/07/21 · arxiv updated 2021/07/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Consider a 2× n rectangular grid composed of 1× 1 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.