Counting Divisions of a $2\times n$ Rectangular Grid
Consider a $2\times n$ rectangular grid composed of $1\times 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$.

\section{Algorithm for Counting Divisions of $n\times m$ Board into $k$ Pieces} \label{sec:algorithm}

While $d_k^m(n)$ has directly proven explicit formulas for small values for $m$ and $k$, computational methods are much more useful to collect data about greater values. We used those data to fit polynomials that predict the number of divisions of the $2\times n$ board into more than two pieces; we prove those formulas satisfy the recursion of Theorem~\ref{drecursion} in the next section.

Our algorithm involves encoding the board as a graph, where the vertices represent the squares, and two vertices are adjacent if and only if their squares are connected in the board. A cut corresponds to removing an edge from the graph, and every valid division of the board corresponds to removing some set of edges from the graph to produce some number of connected components. The algorithm involves checking all possible combinations of edges to be removed, in other words, it iterates through the power set of the edge set of the graph, and finds the number of connected components for each graph after the edge removal. We implemented our algorithm in Python using Networkx [3] and Numpy [4].

However, not every sequence of cuts results in a valid division. For a division to be valid, any two squares that are separated by a cut must end up in different pieces of the division. In the algorithm, this means that if two vertices are adjacent before the edge removal and are not adjacent after the edge removal, the two vertices must not be in the same connected component of the resulting graph.

Using this check for validity, the following algorithm returns the number of divisions of an $n\times m$ board into $1$ through $mn$ pieces. While the algorithm is computationally expensive, it is exhaustive. Therefore no divisions are missed by the algorithm and the divisions into all numbers of pieces are returned by the algorithm at once.



\section{Recursive Relationship for Counting Divisions into $k$ Pieces}
This problem is ripe for recursion because the $2\times n$ board can be extended by simply adding two squares onto the rightmost end, creating a $2\times (n+1)$ board. We can then use these two newly-added squares to form divisions of the $2\times (n+1)$ board in a way that builds off the divisions of the $2\times n$ board nested inside of it. We will denote the $2\times n$ board as $B=(S, A)$, where $S=\{x_0,x_1,\dots,x_{2n-1}\}$, and the $2\times (n+1)$ board as $B'=(S', A')$, where $S'=S\cup\{x_{2n},x_{2n+1}\}$.

In order for $B'$ to build upon the divisions of $B$, special attention needs to be paid to the two rightmost squares of $B$, $x_{2n-2}$ and $x_{2n-1}$. Whether or not these squares are in different pieces is important for how the two newly added squares can be added to the board to create more divisions. We will partition the set of divisions $\mathcal{D}_k(n)$ into $\mathcal{S}_k(n)$ and $\mathcal{T}_k(n)$, where $\mathcal{S}_k(n)$ is the set of divisions where $x_{2n-2}$ and $x_{2n-1}$ are not in the same piece, and $\mathcal{T}_k(n)$ is the set of divisions where $x_{2n-2}$ and $x_{2n-1}$ are in the same piece. We will denote the number of divisions in each set as $|\mathcal{S}_k(n)|=s_k(n)$ and $|\mathcal{T}_k(n)|=t_k(n)$. 
\begin{theorem}
The number of divisions of a $2\times n$ board into $k$ pieces satisfies the following recursion:
\begin{equation*}
d_k(n+1)=d_{k-2}(n)+3d_{k-1}(n)+d_k^2(n)+2s_k(n)
\end{equation*}
\label{drecursion}
\end{theorem}
\begin{proof}
The two additional squares in $B'$ can be used to add 0, 1, or 2 extra pieces to each division of $B$. Thus, to obtain a division into $k$ pieces for $B'$, we only have to consider how the additional squares interact with the divisions of $B$ into \textbf{(i)} $k-2$, \textbf{(ii)} $k-1$, and \textbf{(iii)} $k$ pieces. Throughout this proof, we let $D=\{P_1,P_2,\dots,P_\ell\}$ be the division in $B$ into $\ell$ pieces and we let $D'$ be the division in $B'$.

\textbf{Case (i):} 
To obtain $k$ pieces in $B'$, $x_{2n}$ and $x_{2n+1}$ must both be added as an individual piece, that is, the division in $B'$ is:\\ $D'=\{P_1,P_2,\dots,P_{k-2},\{x_{2n}\},\{x_{2n+1}\}\}$ (see Figure~\ref{fig:kminus2}).\\ 
There is only one way to add the two squares for each division $D\in \mathcal{D}_{k-2}(n)$ to obtain a division in $\mathcal{D}_k(n+1)$. Therefore, there must be a term of $d_{k-2}(n)$ in the recursion.

\textbf{Case (ii):} 
To obtain $k$ pieces in $B'$, $x_{2n}$ and $x_{2n+1}$ must be used to add exactly one piece. There are three ways to do this. The first is to add both as a single piece:\\
$D'=\{P_1,P_2,\dots,P_{k-1},\{x_{2n},x_{2n+1}\}\}$.\\
The other two ways are to add $x_{2n}$ or $x_{2n+1}$ as its own piece, and attach the other to piece containing $x_{2n-2}$ and $x_{2n-1}$, respectively. If $x_{2n-2}\in P_i$ and $x_{2n-1}\in P_j$ (note that it is \textit{not} necessary for $i\neq j$), then the two ways to add the single piece are:\\
$D'=\{P_1,P_2,\dots,P_i\cup\{x_{2n}\},\dots,P_{k-1},\{x_{2n+1}\}\}$ and\\ $D'=\{P_1,P_2,\dots,P_j\cup\{x_{2n+1}\},\dots,P_{k-1},\{x_{2n}\}\}$ (see Figure~\ref{fig:kminus1}).\\
Thus, for each division $D\in \mathcal{D}_{k-1}(n)$, there are 3 ways to obtain a division in $\mathcal{D}_k(n+1)$. Therefore, there must be a term of $3d_{k-1}(n)$ in the recursion.

\textbf{Case (iii):} 
To obtain $k$ pieces in $B'$, $x_{2n}$ and $x_{2n+1}$ must both be attached to some other piece in $B$. How these squares can be added depends on if the division in $B$ is in $\mathcal{T}_k(n)$ or $\mathcal{S}_k(n)$. 

If $D\in \mathcal{T}_k(n)$, then $x_{2n-2},x_{2n-1}\in P_i$, that is, they are in the same piece. The only way to add $x_{2n}$ and $x_{2n+1}$ to remain at $k$ pieces is to add them both to $P_i$, so:\\
$D'=\{P_1,P_2,\dots,P_i\cup\{x_{2n},x_{2n+1}\},\dots,P_k\}$.\\
There is only one way to add the two squares for each division $D\in \mathcal{T}_{k}(n)$ to obtain a division in $\mathcal{D}_k(n+1)$. Therefore, there must be a term of $t_{k}(n)$ in the recursion.

If $D\in \mathcal{S}_k(n)$, then $x_{2n-2}\in P_i$ and $x_{2n-1}\in P_j$, where $i\neq j$. There are three ways to add $x_{2n}$ and $x_{2n+1}$ to remain at exactly $k$ pieces. They can both be added to $P_i$, they can both be added to $P_j$, or they can split, with $x_{2n}$ being added to $P_i$ and $x_{2n+1}$ being added to $P_j$:\\
$D'=\{P_1,P_2,\dots,P_i\cup\{x_{2n},x_{2n+1}\},\dots,P_{k}\}$,\\
$D'=\{P_1,P_2,\dots,P_j\cup\{x_{2n},x_{2n+1}\},\dots,P_{k}\}$, and \\
$D'=\{P_1,P_2,\dots,P_i\cup\{x_{2n}\},P_j\cup\{x_{2n+1}\},\dots,P_{k}\}$ (see Figure~\ref{fig:sep_recursion}).\\
Thus, for each division $D\in \mathcal{S}_{k}(n)$, there are 3 ways to obtain a division in $\mathcal{D}_k(n+1)$. Therefore, there must be a term of $3s_{k}(n)$ in the recursion.

Adding everything together, we get the following:
\begin{equation*}
    d_k(n+1)=d_{k-2}(n)+3d_{k-1}(n)+t_k(n)+3s_k(n)
\end{equation*}
It is quite clear that $\mathcal{D}_k(n)=\mathcal{S}_k(n)\cup \mathcal{T}_k(n)$ and $\mathcal{S}_k(n)\cap \mathcal{T}_k(n)=\emptyset$, so $d_k(n)=s_k(n)+t_k(n)$. We can substitute this into the equation above to obtain the recursion in the theorem statement.
\end{proof}

\begin{figure}
    \centering
    \includegraphics[width=4cm]{kminus2.eps}
    \caption{The single way to add the two squares to each division in $\mathcal{D}_{k-2}(n)$.}
    \label{fig:kminus2}
\end{figure}

\begin{figure}
    \centering
    \includegraphics[width=12cm]{kminus1.eps}
    \caption{The three ways to add the two squares to each division in $\mathcal{D}_{k-1}(n)$. Note that a cut \textit{could} exist between $x_{2n-2}$ and $x_{2n-1}$, it has been omitted in this figure.}
    \label{fig:kminus1}
\end{figure}

\begin{figure}
    \centering
    \includegraphics[width=12cm]{sep_recursion.eps}
    \caption{The three ways to add the two squares to each division in $\mathcal{S}_k(n)$.}
    \label{fig:sep_recursion}
\end{figure}

This recursion is only of use when $s_k(n)$ can be calculated. Fortunately, $s_k(n)$ can also be computed recursively, in terms that do not involve $d_k(n)$.
\begin{theorem}
The number of divisions of a $2\times n$ board into $k$ pieces where the rightmost squares separate satisfies the following recursion:
\begin{equation*}
s_k(n+1)=d_{k-2}(n)+2d_{k-1}(n)+s_k (n)
\end{equation*}
\label{s_recursion}
\end{theorem}
\begin{proof}
Using the same arguments from the proof of Theorem~\ref{drecursion}, finding these divisions simply involves counting the number of divisions of $B'$ where $x_{2n}$ and $x_{2n+1}$ end up in different pieces. They separate in the $d_{k-2}(n)$ term, in two of the cases of the $d_{k-1}(n)$ term, none of the cases of the $t_k(n)$ term, and in one of the cases of the $s_k(n)$ term, so the recursion is just the sum of these cases.
\end{proof}

As a check of this result, we show that Durham and Richmond's result for the number of divisions into two pieces satisfies this recursion. Note that our notation of $s_2(n)$ corresponds to their result that the number of partitions where the first two squares are in different pieces is $2n-1$.
\begin{align*}
d_0(n)=0,&\quad d_1(n)=1,\quad d_2(n)=2n^2-n,\quad s_2(n)=2n-1\\
d_2(n+1)&=0+3(1)+2n^2-n+2(2n-1)
\\&=3+2n^2-n+4n-2=2n^2+3n+1
\\&=2(n+1)^2-(n+1)
\end{align*}

\section{Closed-Form Solutions for Divisions of $2\times n$ Board into Three, Four, and Five Pieces} \label{sec:threeandfour}
Using the tools we have proven thus far, we can find closed-form solutions for the number of divisions of a $2\times n$ board into $k=3,4,5$ pieces. First, we find closed forms of $s_3(n)$, $s_4(n)$, and $s_5(n)$ by generating data using the recursions and then fitting a polynomial to the points. We repeat this process for $d_3(n)$ (and show it matches the result by Durham and Richmond), $d_4(n)$, and $d_5(n)$. Because we know the degrees of each of these polynomials, we only have to generate $2k-2$ points for each $s_k(n)$ and $2k-1$ points for each $d_k(n)$ to exactly determine their coefficients. 

There are multiple methods of interpolation, all of which will produce the same result. Our fitting methods are least-squares regression using Numpy~\cite{harris} and Lagrange interpolation~\cite{archer}. Newton's divided difference method~\cite{weisstein} is another avenue that future researchers can employ.





\input{formula_tables.tex}

The formulas for $s_k(n)$ are shown in Table \ref{tab:s_formulas} and the formulas for $d_k(n)$ are shown in Table \ref{tab:d_formulas}. These polynomials can be explicitly proven to hold by induction using the recursions. As an example, we show the formulas hold for $k=3$ by using the proposed polynomials, as well as the proven polynomials for $d_1(n)$ and $d_2(n)$.

\begin{example}
\begin{align*}
s_3(n+1)&=d_1(n)+2d_2(n)+s_3(n)\\
&=(1)+2n(2n-1)+\frac{4}{3}n^3-3n^2+\frac{8}{3}n-1\\
&=\frac{4}{3}n^3+n^2+\frac{2}{3}n\\
&=\frac{4}{3}(n+1)^3-3(n+1)^2+\frac{8}{3}(n+1)-1\\
d_3(n+1)&=d_1(n)+3d_2(n)+d_3(n)+2s_3(n)\\
&=(1)+3n(2n-1)+\frac{2}{3}n^4-\frac{4}{3}n^3+\frac{11}{6}n^2-\frac{13}{6}n+1\\
&\quad+2\left(\frac{4}{3}n^3-3n^2+\frac{8}{3}n-1\right)\\
&= \frac{2}{3}n^4+\frac{4}{3}n^3+\frac{11}{6}n^2+\frac{1}{6}n\\
&= \frac{2}{3}(n+1)^4-\frac{4}{3}(n+1)^3+\frac{11}{6}(n+1)^2-\frac{13}{6}(n+1)+1
\end{align*}
\end{example}
The proofs for $k=4$ and $k=5$ proceed in the exact same manner, and are omitted for brevity.

The greatest challenge to proving formulas like these is to actually obtain the polynomials; the proof that they hold consists of only algebraic manipulations that can readily be outsourced to a computer algebra system. In theory, this process can be continued for $k=6,7,\dots$, as long as enough points are generated using the recursion. So long as the computer calculating the fitting polynomials has sufficient precision, the decimals returned by the interpolation algorithm can be converted into fractions relatively easily. 

\section{Functional Forms of $d_k^2(n)$ and $s_k^2(n)$}\label{sec:forms}
In the previous section, we implicitly assumed that the functions that count the number of divisions are polynomials on $n$. This assumption is correct. In this section, we prove that for all $k$, $d_k(n)$ and $s_k(n)$ must be polynomials on $n$. Moreover, we show that the degrees of these polynomials are $2k-2$ and $2k-3$, respectively. 

Our proofs of the polynomial nature of the functions is based on the fact that the sum of polynomials is a polynomial, and our proof of their degrees is based on Faulhaber's formula. A straightforward derivation of Faulhaber's formula is given in \cite{orosi}. The formula gives an expression for the sum of the first $n$ integers each raised to the positive integer power $p$ as a polynomial of degree $p+1$. Stated more explicitly,
\begin{equation*}
    \sum_{k=1}^nk^p=\frac{1}{p+1}\sum_{j=0}^p(-1)^j\binom{p+1}{j} B_jn^{p+1-j},
\end{equation*}
where $B_j$ is the $j$-th Bernoulli number \cite{apostol}. As we are only interested in the degree of the polynomial, we will condense the coefficients into a single variable, 
\begin{equation*}
    \sum_{k=1}^nk^p=\sum_{j=0}^pA_jn^{p+1-j},
\end{equation*}
where $A_j=\frac{(-1)^j}{p+1}\binom{p+1}{j}B_j$. Before we can employ the formula, we must rewrite our recursions in terms of summations. Beginning with $s_k(n)$, by Theorem~\ref{s_recursion} we have
\begin{equation*}
s_k(n)=d_{k-2}(n-1)+2d_{k-1}(n-1)+s_k(n-1).
\end{equation*}
Substituting for $s_k(n-1)$ using the recursion gives
\begin{align*}
s_k(n)&=d_{k-2}(n-1)+2d_{k-1}(n-1)\\
&+d_{k-2}(n-2)+2d_{k-1}(n-2)+s_k(n-2).
\end{align*}
This can be repeated until the input is 0, where $d_k(0)=s_k(0)=0$ for all $k$, so
\begin{equation}
s_k(n)=\sum_{j=1}^{n-1} d_{k-2}(j)+2d_{k-1}(j).
\label{eq:s_summation}
\end{equation}
We can do the same for $d_k(n)$. From Theorem~\ref{drecursion} we have
\begin{equation*}
d_k(n)= d_{k-2}(n-1)+3d_{k-1}(n-1)+2s_k(n-1)+d_k(n-1).
\end{equation*}
Substituting for $d_k(n-1)$ using the recursion gives
\begin{align*}
d_k(n)&= d_{k-2}(n-1)+3d_{k-1}(n-1)+2s_k(n-1)\\
&+d_{k-2}(n-2)+3d_{k-1}(n-2)+2s_k(n-2)+d_k(n-2).
\end{align*}
Again, this can be repeated all the way to 0, so
\begin{equation}
d_k(n)=\sum_{j=1}^{n-1} d_{k-2}(j)+3d_{k-1}(j)+2s_k(j)
\label{eq:d_summation}
\end{equation}


\begin{theorem}
For all $k$, $s_k(n)$ and $d_k(n)$ are polynomials on $n$, where $s_k(n)$ is of degree $2k-3$ and $d_k(n)$ is of degree $2k-2$.
\end{theorem}
\begin{proof}
Proof is by strong induction on $k$

The base cases are satisfied for $k=1,2$, as $d_1(n)=1,d_2(n)=2n^2-n,s_1(n)=0,s_2=2n-1$, each of which is a polynomial with appropriate degree. Our inductive assumption is that for all positive integers $\ell$ less than some integer $k$, $s_\ell(n)$ and $d_\ell(n)$ are of degree $2\ell-3$ and $2\ell-2$, respectively. Using Equation~(\ref{eq:s_summation}), it must be a polynomial, because it is a sum of polynomials. The same holds true for $d_k(n)$ using Equation~(\ref{eq:d_summation}). To prove the degrees, we start with $s_k(n)$. From Equation~(\ref{eq:s_summation}), we have
\begin{equation*}
    s_k(n)=\sum_{j=1}^{n-1} d_{k-2}(j)+2d_{k-1}(j).
\end{equation*}
Expanding $d_{k-1}(j)$ as a polynomial of degree $2k-4$ gives
\begin{align*}
    s_k(n)&=\sum_{j=1}^{n-1}\left(d_{k-2}(j)+2\left(\sum_{i=0}^{2k-4} C_i j^i\right)\right)\\
    &=\sum_{j=1}^{n-1}\left( d_{k-2}(j)+2C_{2k-4}j^{2k-4}+2\left(\sum_{i=0}^{2k-5} C_i j^i\right)\right).
\end{align*}
By Faulhaber's formula, $\displaystyle\sum_{j=1}^{n-1} 2C_{2k-4}j^{2k-4}$ is equal to a polynomial of degree $2k-3$. The remainder of the summation involves terms of powers that are at most $2k-5$, so Faulhaber's formula will only produce polynomials of degree up to $2k-4$ for those terms. Therefore $s_k(n)$ is equal to a polynomial of degree $2k-3$. To prove $d_2(n)$ is equal to a polynomial of degree $2k-2$, we begin with Equation~(\ref{eq:d_summation}),
\begin{equation*}
d_k(n)=\sum_{j=1}^{n-1} d_{k-2}(j)+3d_{k-1}(j)+2s_k(j).
\end{equation*}
Expanding $s_k(j)$ as a polynomial of degree $2k-3$ gives
\begin{align*}
    d_k(n)&=\sum_{j=1}^{n-1}\left( d_{k-2}(j)+3d_{k-1}(j)+2\left(\sum_{i=0}^{2k-3}C_ij^i\right)\right)\\
    &=\sum_{j=1}^{n-1}\left( d_{k-2}(j)+3d_{k-1}(j)+2C_{2k-3}j^{2k-3}+2\left(\sum_{i=0}^{2k-4}C_ij^i\right)\right).
\end{align*}
By Faulhaber's formula, $\displaystyle\sum_{j=1}^{n-1} 2C_{2k-3}j^{2k-3}$ is equal to a polynomial of degree $2k-2$. The remainder of the summation involves terms of powers that are at most $2k-4$, so Faulhaber's formula will only produce polynomials of degree up to $2k-3$ for those terms. Therefore $d_k(n)$ is equal to a polynomial of degree $2k-2$. This completes the induction.
\end{proof}

The power in knowing that these functions are polynomials with predictable degrees is that their closed-form solutions can be found simply by using interpolation on data generated from the recursion, which can swiftly be implemented in most programming languages. A polynomial of degree $d$ is uniquely determined by $d+1$ points, so by generating enough data for some fixed $k$, the polynomial that counts the number of divisions can be calculated immediately, with no need for any combinatorial arguments.



\section{Future Work}
Counting the number of divisions of a $2\times n$ rectangular grid into $k$ pieces has exhibited multiple interesting patterns. The functions that count these divisions are all polynomials with predictable degrees, a fact that is not at all obvious from the first glance at this problem. 

While we have shown that all the division-counting functions will be polynomials, these polynomials are unknown to us for $k>5$. Our process of fitting polynomials to the data generated from the recursion eventually failed due to the limited precision of our computer.

Our recursion technique works well for the $2\times n$ board, but quickly becomes more complicated when the height of the board is 3 or greater. For a $3\times (n+1)$ board, the recursion that counts the number of divisions  will involve the number of divisions of the $3\times n$ board into $k-3,k-2,k-1$ and $k$ pieces. While the $k-3$ case is easy (just add the three new squares as separate pieces), the other cases will depend on how the three rightmost squares of the $3\times n$ board are distributed among the pieces of each division. The cases would be: (i) all three are in different pieces, (ii) two are in one piece, the last is in another (of which there are three subcases depending on which square is alone), and (iii) all three are in the same piece. This would require defining more sets than just $\mathcal{S}_k(n)$ and $\mathcal{T}_k(n)$ to account for all possible ways to add the new squares.

It's worth noting that this problem is deeply connected to graph theory. Our goal of counting the number of divisions of the $2\times n$ into $k$ pieces board is equivalent to counting the number of ways to remove edges from a $2\times n$ lattice graph while following some specific rules. Those rules being that the removed edges must result in the graph being decomposed into $k$ connected components, and that if an edge is removed between two vertices, those vertices must end up in different connected components, similar to how a cut determines that two adjacent squares end up in different pieces.

We were able to leverage this equivalence to write Python code that counts all the divisions of an $m\times n$ board into $k$ pieces for all $1\leq k\leq mn$. This was achieved by encoding the grid as an $m\times n$ lattice graph with connected squares being adjoined by edges. A cut corresponded to removing the edge between two vertices. Using Networkx~\cite{hagberg}, we were able to iterate through all possible edge removals and count the number of pieces that were returned for each removal that followed the rules mentioned previously. Removals that did not follow the rules were ignored. The program is not efficient, but it is exhaustive. To access the code, go to \url{https://github.com/jakebr118/Counting-Divisions/blob/main/division_counting}.

A pattern with our polynomials is that the leading coefficient appeared to be decreasing monotonically for greater and greater $k$. The leading coefficients of the polynomials for $k\leq 5$ are $2,\frac{2}{3},\frac{4}{45},\frac{2}{315}$, in order. Whether or not this pattern continues is unknown to us, but we conjecture that it holds. Our reasoning is that in order to ``control" the number of divisions at small $n$, the coefficient on the highest-order term must stay small. A rigorous proof (or counterexample) is definitely in order, though.

\begin{abstract}
What is the number of ways to divide a $2\times n$ rectangular grid, cutting along the grid lines, into $k$ pieces? Are there formulas that calculate these number of divisions? If so, what do they look like? We show that all division-counting formulas will be polynomials on $n$ for all $k$, and that for a fixed $k$, the division-counting polynomial will have degree $2k-2$. We find these polynomials up to $k=5$.
\end{abstract}
\textbf{Acknowledgements}\\
The author wishes to thank Emilie Wiesner and Daniel Visscher for their support, knowledge, and inspiration throughout the course of the project. 



\section{Symmetry of Divisions}\label{sec:sym}

Consider the two divisions shown in Figure~\ref{fig:symmetry}. One could reasonably argue that these two divisions are the same, as one can be obtained from the other by simply reflecting the board along a horizontal or vertical axis. This raises the question: is there a way to count the divisions that are the same under isometric transformations of the board, that is, rotations and reflections?

To answer this question, we introduce the following definition:

\begin{definition}
Two divisions are \textbf{equivalent up to isometry} if and only if one division can be mapped onto the other by rotating or reflecting the board. The number of divisions up to isometry is denoted as $i_2^2(n)$
\end{definition}

Equivalence up to isometry forms an equivalence relation over the set of divisions of the board, therefore, there is a set of equivalence classes under this equivalence relation. Each division in an equivalence class can be obtained from the others by rotating and reflecting the overall board. Therefore, each equivalence class is an orbit of the divisions under the group actions of rotation and reflection. In this case, these actions correspond to the dihedral group of order 4, $\mathcal{D}_2$. This calls to mind Burnside's Lemma [5]:
\begin{lemma}[Burnside's Lemma]
Let $X$ be a set and $G$ be a group acting on the set. If $X^g$ is the set of elements in $X$ that are fixed by each $g\in G$, then the number of orbits $|X/G|$ of $X$ when acted upon by $G$ is
\begin{equation*}
|X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g|
\end{equation*}
\label{burnside}
\end{lemma}
\begin{figure}
    \centering
    \includegraphics[width=9cm]{symmetry.eps}
    \caption{Reflecting the board along a horizontal or vertical axis maps one division onto the other.}
    \label{fig:symmetry}
\end{figure}
Before moving on to counting the divisions up to isometry, a couple additional lemmas will be proven to facilitate the arguments.
\begin{lemma}
For a $2\times n$ board being divided into 2 pieces, there are at most 2 vertical cuts.
\end{lemma}
\begin{proof}
Consider a division consisting of 3 or more vertical cuts. Either three cuts are on the same row, or two are on one row and one is on the other. If three are on the same row, then one cut must be between the other two. The outer two cuts will form a division consisting of a rectangular piece and the remainder of the board. The third vertical cut will divide this rectangular piece into two pieces, giving three in total. If two are on one row and one is on the other, there are three cases: (i) one cut is between the other two, and the outer cuts are on the same row, (ii) one cut is between the other two, and the outer cuts are on different rows, (iii) the single cut in one row aligns with one of the two cuts in the other row.
\\ \\
For case (i), the outer cuts will form a division consisting of a rectangular piece and the remainder of the board. The third cut will divide the remainder of the board, giving three total. For case (ii), the outer cuts will form a division consisting of an L-shaped piece and the remainder of the board. The third cut will divide this L-shaped piece into two pieces, giving three in total. For case (iii), the two cuts on the same row will form a division consisting of a rectangle and the remainder of the board. The third cut will divide the remainder of the board, giving three in total.
\end{proof}
\begin{lemma}
Any division fixed by rotation must consist of isometrically identical pieces.
\label{identical_rotation}
\end{lemma}
\begin{proof}
Consider a division consisting of non-identical pieces. In order for a rotation to fix a division, when rotated, each piece must map exactly to where the other piece was previously. If the pieces are shaped differently, then neither piece will fit into where the other piece was previously, meaning the division cannot be fixed by rotation. This means a division consisting of non-identical pieces is not fixed by rotation, and the contrapositive must also be true.
\end{proof}
\begin{lemma}
Any division fixed by reflection must map vertical cuts to vertical cuts.
\label{cuts_reflection}
\end{lemma}
\begin{proof}
Suppose there is a reflection that does not map vertical cuts to vertical cuts. Then, after the reflection, the division will be different, as the vertical cuts are not in the same place as before. This means that any reflection that does not map vertical cuts to vertical cuts cannot fix any division, and the contrapositive must also be true.
\end{proof}
\begin{lemma}
Let $g\in \mathcal{D}_2$ not be the identity action. Then for each $x\in X^g$, there must be 0 or 2 vertical cuts. If there are 2, they must be the same distance from the vertical axis of reflection.
\label{lem:not_identity}
\end{lemma}
\begin{proof}
A division consisting of only 1 vertical cut cannot be fixed by any non-identity group action. This is because a single vertical cut corresponds to a division that results in a corner being removed from the main board. The non-rectangular remainder of the board is cannot be fixed by any rotation or reflection, so the division as a whole cannot be fixed by any group action.
\\ \\
Consider a division consisting of 2 vertical cuts. Suppose that the two cuts are not the same distance from the vertical axis of reflection, which means they cannot be identical. Then the pieces cannot be fixed by any symmetry in $\mathcal{D}_2$. By Lemma~\ref{identical_rotation}, they cannot be fixed by the rotation because they are not identical. By Lemma~\ref{cuts_reflection}, they cannot be fixed by any reflection because any such reflection cannot map vertical cuts to vertical cuts, as they will not ``align" with one another. Therefore any division where the vertical cuts are not the same distance from the vertical axis of reflection cannot by fixed by any non-identity group action, and the contrapositive must also be true.
\end{proof}
We now have the capability to prove the following theorem:
\begin{theorem}
The number of divisions up to isometry for the $2\times n$ board into two pieces is
$$i_2^2(n)=\frac{1}{2}n(n+1)$$.
\label{the:symmetry}
\end{theorem}
\begin{proof}
Let $D_2^2(n)$ be the set of divisions of the $2\times n$ board into 2 pieces. The number of divisions up to isometry is equal to the number of orbits of $D_2^2(n)$ under the elements of $\mathcal{D}_2$. These are counted using Burnside's Lemma:
\begin{equation*}
   i^2_2(n)=\frac{1}{|\mathcal{D}_2|}\sum_{g\in \mathcal{D}_2}|D_2^2(n)^g|
\end{equation*}
Recall that $\mathcal{D}_2=\{e,\rho,\mu_H,\mu_V\}$, where $e$ is the identity, $\rho$ is a rotation by $180^\circ$, $\mu_H$ is a horizontal reflection, and $\mu_V$ is a vertical reflection. 

Clearly, all elements of $D_2^2(n)$ are fixed by $e$, so $|D_2^2(n)^e|=d_2^2(n)=2n^2-n$.

For $\rho$, recall from Lemma~\ref{identical_rotation} that any division fixed by rotation must consist of identical pieces, and from Lemma~\ref{lem:not_identity} that the division must consist of 0 or 2 vertical cuts. If there are 0, then the board must be cut completely in half along the horizontal middle, which corresponds to 1 division. 

If there are 2, then they must be the same distance from the vertical axis of reflection. To produce identical pieces, the two vertical cuts must be on opposite sides both the horizontal and vertical axes of reflection, corresponding to a division that creates two identical L-shaped pieces. There are $n-1$ ways to choose where to place the cut above the horizontal axis, which fixes the location of the second cut. This corresponds to $n-1$ divisions. Therefore, there are $n$ divisions fixed by rotation.

For $\mu_H$, recall from Lemma~\ref{cuts_reflection} that any division fixed by reflection must consist of identical pieces, and from Lemma~\ref{lem:not_identity} that the division must consist of 0 or 2 vertical cuts. If there are 0, then the board must be cut completely in half along the horizontal middle, which corresponds to 1 division. 

If there are 2, then they must be the same distance from the vertical axis of reflection. To map vertical cuts to vertical cuts, the two vertical cuts must be on opposite sides both the horizontal axis of reflection, but on the same side of the vertical axis of reflection, corresponding to a division that cuts the board along a vertical cut of length 2. There are $n-1$ ways to choose where to place the cut above the horizontal axis, which fixes the location of the second cut. This corresponds to $n-1$ divisions. Therefore, there are $n$ divisions fixed by horizontal reflection.

For $\mu_V$, recall from Lemma~\ref{cuts_reflection} that any division fixed by reflection must consist of identical pieces, and from Lemma~\ref{lem:not_identity} that the division must consist of 0 or 2 vertical cuts. If there are 0, then the board must be cut completely in half along the horizontal middle, which corresponds to 1 division. 

If there are 2, then they must be the same distance from the vertical axis of reflection. To map vertical cuts to vertical cuts, the two vertical cuts must be on the same side of horizontal axis of reflection, but on opposite sides of the vertical axis of reflection, corresponding to a division that cuts a rectangle out of one side of the board, leaving a cup-shaped piece on the other side. There are $n-1$ ways to choose where to place the first cut, which fixes the location of the second cut. This corresponds to $n-1$ divisions. Therefore, there are $n$ divisions fixed by vertical reflection.

Putting everything together:
\begin{equation*}
    i_2^2(n)=\frac{1}{4}(2n^2-n+n+n+n)=\frac{1}{4}(2n^2+2n)=\frac{1}{2}n(n+1)
\end{equation*}
\end{proof}
\section{Table of Values}

\begin{table}[h]
    \centering
    \begin{tabular}{l|ccccc}
$n$\textbackslash $k$&1&2&3&4&5\\\hline
1&1&1&0&0&0\\
2&1&6&4&1&0\\
3&1&15&29&21&7\\
4&1&28&107&153&111\\
5&1&45&286&678&831\\
6&1&66&630&2241&4131\\
7&1&91&1219&6091&15748\\
8&1&120&2149&14385&49728\\
9&1&153&3532&30556&136322\\
10&1&190&5496&59745&334650\\
11&1&231&8185&109297&751797\\
12&1&276&11759&189321&1570261\\
13&1&325&16394&313314&3085929\\
14&1&378&22282&498849&5759013\\
15&1&435&29631&768327&10280634\\
16&1&496&38665&1149793&17657998\\
17&1&561&49624&1677816&29321364\\
18&1&630&62764&2394433&47256260\\
19&1&703&78357&3350157&74164659\\
20&1&780&96691&4605049&113659083\\\hline
$n$\textbackslash $k$&6&7&8&9&10\\\hline
1&0&0&0&0&0\\
2&0&0&0&0&0\\
3&1&0&0&0&0\\
4&45&10&1&0&0\\
5&603&274&78&13&1\\
6&4596&3334&1635&545&120\\
7&24732&25747&18667&9668&3600\\
8&104575&146831&145602&105508&56931\\
9&369826&671848&868084&829399&600723\\
10&1138712&2596968&4227342&5121823&4751906\\
11&3138171&8779022&17557890&26233173&30193383\\
12&7896713&26600748&64099355&115621525&161241434\\
13&18416453&73572842&210256970&450245602&747044478\\
14&40266876&188347198&630047025&1579913534&3073562178\\
15&83292430&451183577&1747134845&5071899551&11430370077\\
16&164186075&1020203769&4529679900&15074867903&38959972033\\
17&310252468&2193013248&11071498344&41885398146&123062891994\\
18&564768560&4507745568&25686998844&109653320338&363498052540\\
19&994447045&8903613660&56893770324&272254496222&1011537069434\\
20&1699620357&16969012366&120878343957&644635341150&2668573664500\\
    \end{tabular}
    \label{tab:my_label}
\end{table}
\section{Closed Form Solution for Counting Divisions into Two Pieces} \label{sec:twopieces}
Durham and Richmond previously showed that the number of divisions of the $2\times n$ board into two pieces is given by $2n^2-n$. Wagon~\cite{wagon} provided an alternative visual proof to their result, we offer yet another alternative proof. Our argument makes use of induction and recursion, and these arguments will be utilized in a similar manner in the following sections. A key insight to our argument is that the divisions of a $2\times n$ board are embedded within the divisions of a $2\times (n+1)$ board, and the divisions of this ``sub-board" (consisting of all but the rightmost column) correspond in a predictable manner with the divisions of the overall board.
\begin{theorem}[Durham]
\label{the:twopieces}
The number of divisions of a $2\times n$ board into two pieces is $d^2_2(n)=n(2n-1)$.
\end{theorem}
\begin{proof}

Our proof is by induction on $n$.

By Remark~\ref{re:onedivision}, $d^2_2(1)=1=(1)(2(1)-1)$.

For the induction, assume for a positive integer $j$ that $d_2^2(j)=j(2j-1)$. Each division of the $2\times j$ sub-board has some number of corresponding divisions in the $2\times (j+1)$ board. Note that the sub-board's division may be into only one piece. Color the rightmost vertically-connected squares of the $2\times(j+1)$ board blue and the rightmost vertically-connected squares of the $2\times j$ sub-board green (see Figure~\ref{fig:greenblue}). To obtain a division into two pieces on the $2\times(j+1)$ board, there are two cases to consider. First, there's the case where the $2\times j$ sub-board is divided into only one piece. In this case, there are three ways to obtain a division of the $2\times (j+1)$ board into two pieces. Two divisions can be obtained by cutting off one of the blue squares and attaching the other to the $2\times j$ sub-board, and one division is obtained by cutting off both blue squares into their own piece (see Figure~\ref{fig:greentogether}). 
\begin{figure}
\centering
\includegraphics[width=5cm]{twocolor.eps}
\caption{Coloring argument that is used in the proof of Theorem~\ref{the:twopieces}.}
\label{fig:greenblue}
\end{figure}

The remaining divisions can be obtained by dividing the $2\times j$ sub-board into two pieces and adding the blue squares onto them. Recall from Lemma~\ref{lem:separation} that the number of divisions of the $2\times j$ sub-board is partitioned by whether or not the green squares separate. Furthermore, for each division, there will be some number of ways to add the blue squares to obtain a division of the $2\times (j+1)$ board. Therefore, we can write:
\begin{equation}
\label{eq:divisionsincomplete}
d_2^2(j+1)=3+At_2^2(j)+Bs_2^2(j)
\end{equation}
For some positive integers $A,B$. To find $A$, note that when the green squares do not separate, the blue squares must remain connected and attach to the green squares, or else the board will be divided into more than two pieces. Therefore, for each division of the $2\times j$ sub-board where the green squares do not separate, there is one corresponding division in the $2\times (j+1)$ board. Thus, $A=1$

\begin{figure}
\centering
\includegraphics[width=12 cm]{sep.eps}
\caption{The three ways for the blue squares to be added to the board when the $2\times j$ sub-board remains fully intact. The case on the left accounts for two ways, depending on which blue square becomes its own piece.}
\label{fig:greentogether}
\end{figure}

When the green squares do separate, there are three possible sub-cases: i) both blue squares attach to the top green square, ii) both blue squares attach to the bottom green square, or iii) the blue squares separate and attach one to each green square (see Figure~\ref{fig:addgreenseparate}). Therefore, for each division of the $2\times j$ board where the green squares do separate, there are 3 corresponding divisions in the $2\times (j+1)$ board, thus $B=3$.

\begin{figure}
\centering
\includegraphics[width=12cm]{threesep.eps}
\caption{The three ways to add the blue squares to a division of the $2\times j$ sub-board where the green squares separate.}
\label{fig:addgreenseparate}
\end{figure}



Rewriting Equation~\ref{eq:divisionsincomplete} using Lemma~\ref{lem:separation}:
\begin{equation}
d_2^2(j+1)=3+t_2^2(j)+3s_2^2(j)=3+2s_2^2(j)+d_2^2(j)
\label{eq:divisionscomplete}
\end{equation}

To count $s_2^2(j)$, note that the only divisions of the $2\times j$ sub-board that cause the green squares to separate are the division that divides the board along the horizontal middle and the divisions that remove only the corner of the board. To remove only a corner of the board, place a vertical cut along any of the $j-1$ vertical edges that are contained in the interior of the board (ie, those edges that are not on the outer boundary). Then, make a horizontal cut along the horizontal middle of the board in the direction of the corner to be removed (See Figure~\ref{fig:greenseparate}). Thus, there are $j-1$ ways to remove one corner from the board, and because there are two corners being considered, the total number of divisions that separate the green squares is
\begin{equation*}
s_2^2(j)=2(j-1)+1=2j-1
\end{equation*}

Substituting this into Equation~\ref{eq:divisionscomplete}, and using the inductive assumption:
\begin{equation*}
d_2^2(j+1)=3+2(2j-1)+j(2j-1)=2j^2+3j+1=(j+1)(2(j+1)-1)
\end{equation*}
Which completes the induction.
\end{proof}
\begin{figure}
\centering
\includegraphics[width=4cm]{endoff.eps}
\caption{Each vertical red line is a possible edge to place a vertical cut that, when paired with the horizontal cut to the right edge of the board, removes the upper right corner of the board and results in the green squares becoming separated.}
\label{fig:greenseparate}
\end{figure}
The ``adding squares" approach from this section forms the core of our arguments for the next section. This strategy highlights how the number of divisions depends on the number of divisions of the board into a smaller number of pieces. In addition, there is a further dependence on \textit{how} the divisions are structured, particularly by whether or not the rightmost squares end up in separate pieces.

2021-07-23T02:02:23.000
2106
2106.14755
en
https://arxiv.org/abs/2106.14755
Consider a $2\times n$ rectangular grid composed of $1\times 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$.
Combinatorics (math.CO)
Counting Divisions of a $2\times n$ Rectangular Grid
Qwen/Qwen-72B
1. YES
2. YES