\documentclass[12pt,reqno]{article}

\usepackage[usenames]{xcolor}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\usepackage{authblk}
\usepackage{tikz}
\usetikzlibrary{arrows.meta}
\usetikzlibrary{decorations.pathreplacing}
\usepackage{cases} % for subnumcases
\usepackage{subcaption}
\usepackage{bbm}
\delimitershortfall=-1pt

\usepackage{enumitem}


\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}

\DeclareMathOperator{\fxpt}{fxpt}
\DeclareMathOperator{\lcm}{lcm}
\DeclareMathOperator{\id}{id}

\begin{document}

\begin{center}
\includegraphics[width=4in]{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\newtheorem{exampleGrid}[theorem]{Illustration}

\newcommand{\RG}{\text{RG}}
\newcommand{\SG}{\text{SG}}
\newcommand{\CY}{\text{C}}
\newcommand{\RT}{\text{RT}}
\newcommand{\ST}{\text{ST}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\ps}[3]{\left((#1,#2),#3\right)}
\newcommand{\xyd}{{\ps xyd}}
\newcommand{\abg}{{\ps abg}}
\newcommand{\grid}{\Z/n\Z \times \Z/m\Z}
\newcommand{\cylinderSymmetries}{\Z/n\Z \rtimes R}
\newcommand{\torusSymmetries}{(\grid) \rtimes R}
\newcommand{\NA}{\multicolumn{1}{c|}{---}}
\newcommand{\orb}[2]{\mathcal{O}^{\langle #1 \rangle}_{\langle #2 \rangle}}
\newcommand{\orbid}[1]{\mathcal{O}^{\langle #1 \rangle}_{\mathbbm 1}}

\newcommand{\appendixpagenumbering}{
  \break
  \pagenumbering{arabic}
  \renewcommand{\thepage}{\thesection-\arabic{page}}
}

\newcommand{\seqTableEntry}[2]{
  \begin{tabular}[c]{@{}l@{}}
    Sequence \ref{seq:#1}\\
    \seqnum{#2}
  \end{tabular}
}

\newcommand{\tableTableEntry}[2]{
  \begin{tabular}[c]{@{}l@{}}
    Table \ref{tabl:#1}\\
    \seqnum{#2}
  \end{tabular}
}


\input{Illustrations/commands_grid_illustration.tex}
\input{Illustrations/commands_tile_descriptions.tex}

\begin{center}
  \vskip 1cm{\LARGE\bf Counting Tilings of the $n \times m$ Grid, \\
  \vskip .1in
  Cylinder, and Torus
  }
  \vskip 1cm
  \large
  Peter Kagey\\
  Department of Mathematics\\
  Harvey Mudd College\\
  Claremont, CA 91711\\
  USA\\
  \href{mailto:pkagey@g.hmc.edu}{\tt pkagey@g.hmc.edu} \\
  ~\\
  William Keehn\\
  Prison Mathematics Project\\
  Phoenix, AZ 85028\\
  USA
  \end{center}

  \vskip .2 in
  \begin{abstract}
    We count tilings of the rectangular grid, cylinder, and
    torus with arbitrary tile designs up to arbitrary symmetries of the
    square and rectangle, along with cyclic shifting of rows and columns,
    generalizing and classifying a a tiling problem first enumerated by
    M. C. Escher in May 1942.
    This provides a unifying framework for understanding a family of
    counting problems, expanding on the work by Ethier and Lee counting
    tilings of the torus by tiles of two colors.
  \end{abstract}

In 1704 the Dominican priest, mathematician, and typographer S\'ebastien Truchet,
wrote a manuscript \textit{M\'emoire sur les combinaisons} \cite{Truchet}, which illustrates
designs that can be made from many copies and rotations of the ``Truchet tile''
$\inlineTileNW$, one of which is reproduced in Figure
\ref{fig:TruchetIllustration}. In 1722, Douat published a book
containing futher analysis and illustrations of these tilings \cite{Douat}.
Truchet's and Douat's work resurfaced in Cyril Stanley Smith and Pauline
Boucher's translation \cite{Smith}, which also introduced another tile design
which is also, somewhat ambiguously, called a Truchet tile: \inlineTileDiag.

The earliest record of attempting to count these configurations
was perhaps the artist M. C. Escher, who in May 1942 explicitly
enumerated all of the $23$ configurations of what we call the $2 \times 2$
grid on a torus by rotationally asymmetric tiles up to $90^\circ$ rotation,
as verified by  Schattschneider \cite{Schattschneider1990, Schattschneider}.
(An illustration of this can be found in the appendix in Figure \ref{fig:nXnTorus_r__id}.)

Given some set of arbitrary tile designs, we are interested in counting ways of
tiling the $n \times m$ square grid, of tiling the infinite strip in a
periodic way, and of tiling the Euclidean plane in a way that is periodic both
left-to-right and top-to-bottom, up to various symmetries.
Both Truchet's and Douat's work were, at least in part, meant to be useful as a
reference for artists, architects, and designers. In this way, the counting
problems are of physical interest as they count the essentially different ways of
tiling a square table, knitting a scarf with a repeating motif, or tiling the
floor of a large room with a repeating design.

\input{Illustrations/fig_truchetIllustration.tex}

Ultimately, we will construct a framework for counting the number of ways of
tiling the grid up to various symmetries. This provides a unifying theory for a
family of problems that appear to have only been analyzed in an
\textit{ad hoc} manner. This will give a unifying framework for over a dozen OEIS
sequences including but not limited to
\seqnum{A047937},
\seqnum{A054247},
\seqnum{A086675},
\seqnum{A179043},
\seqnum{A184271},
\seqnum{A184277},
\seqnum{A184284},
\seqnum{A200564},
\seqnum{A222187},
\seqnum{A222188},
\seqnum{A225910},
\seqnum{A255015},
\seqnum{A255016},
\seqnum{A295223},
\seqnum{A295229},
\seqnum{A302484},
\seqnum{A343095}, and
\seqnum{A343096}.
Applying this framework has resulted in the addition of 49 new sequences to the On-Line Encyclopedia of Integer Sequences (OEIS) \cite{OEIS}.


When we consider at the grid up to symmetries of the square or rectangle, we call this the
$n \times m$ grid, an example of which is illustrated in Figure \ref{fig:TruchetIllustration}.
When we additionally allow cyclic shifting of columns, we call this the
$n \times m$ cylinder, which is illustrated in Figure \ref{fig:cylinderIdentification}.
When we allow cyclic shifting of the rows in addition to the above symmetries,
we call this the $n \times m$ torus, which is illustrated in Figure \ref{fig:torusIdentification}.

\input{Illustrations/fig_cylinderIdentification.tex}
\input{Illustrations/fig_torusIdentification.tex}

The number of such tilings depends on
the size of the grid,
the symmetries of the grid under consideration,
the symmetries of the tile designs, and
the number of tile designs with a given symmetry.
We formalize each of these four notions below, and use them to give a formula
that counts the number of corresponding tile designs.

\section{Background}
Many mathematicians, architects, artists, and others have studied and
generalized Truchet tiles, starting with Douat \cite{Douat}, who illustrated examples of
rosettes, which are tilings of the grid with dihedral symmetry, and which were
studied mathematically by Hall, Almeida, and Teixeira \cite{Hall}.
M. C. Escher, Schattschneider \cite{Schattschneider}, and \cite{Davis} were
perhaps the earliest to count these tilings on a torus, and Schattschneider is
perhaps the earliest to ask about higher-dimensional analogs in the form of
cubic tiles.

Many others have considered generalizations of these tiles, in terms of
specific tile designs, other polygons, and higher dimensional analogs.
Lord and Ranganathan \cite{Lord} also looked at generalizations on rhombuses
and on cubes.
Browne considered different scales \cite{Browne2008} and generalizations to
hexagons \cite{Browne2008}.
Krawczyk generalized to other square tile designs, including tiling the faces
of a cube \cite{Krawczyk}.
Ahmed gave a catalog of square and hexagonal tile designs,
including tile designs for octagons and the truncated square tiling \cite{Ahmed}.
Borlenghi produced perhaps the richest catalog of examples of square tile designs and also has a related US Patent \cite{Borlenghi}.
Beveridge looked at generalizations of Truchet tiles to all $2n$-gons and the faces of a cube \cite{Beveridge}.
Carlson considered putting together tiles of different scales in a compatible manner \cite{Carlson}.
Mitchell gave further examples of triangular, square, hexagonal, and octagonal tile designs and corresponding Archimedean tilings of the Euclidean plane \cite{Mitchell}.
Walter, Ligler, and G\"{u}rsoy utilized ``shape rules'' to generate tile designs on the equilateral triangle, square, regular hexagon, and other convex polygons \cite{Walter}.
Knoll, McLellan, and Cox studied the $2 \times 2$ grid of Truchet tiles including some novel group actions related to flipping woven versions along with some constructions related to de Bruijn sequences \cite{Knoll}.

In the 1980s the following one-line Commodore 64 computer program was a popular
way to create an interesting output: \[
  \verb|10 PRINT CHR$(205.5+RND(1));: GOTO 10|
\] The program printed \verb|\| and \verb|/| to the display as an endless
loop, which
created maze-like figures that are closely related to those shown in Figure
\ref{fig:nXnTorus_r_f__rf}. This computer program is also the title of a book
by Montfort along with nine other authors which discusses the program along with
its cultural importance \cite{Montfort}.

In addition to the connections to M. C. Escher, art, programming, and
recreational mathematics, related concepts also come up in the context of
statistical mechanics (especially with Smith's version of the Truchet tile)
with the Completely Packed Loops model or $O(n)$ Loop Model.
See, for example,
Fonseca and Zinn-Justin's analysis of the $O(\tau)$-loop model on a cylider \cite{Fonseca},
Hooper's analysis of probabilities related to closed curves \cite{Hooper}, and
Nahum, Serna, Somoza, and Ortu\~no's loop models with crossings \cite{Nahum}.

\section{Notation and preliminaries}
In this section, we will
formalize the notation of a grid and its size,
the symmetries of the grid that we count up to,
the symmetries of the tile designs, and
the number of tile designs with a given symmetry.

\subsection{Tilings and the grid}
In order to talk about tilings of the $n \times m$ grid, cylinder, and torus,
it is important to first formalize what these are. All of these ideas start
with the fundamental idea of the $n \times m$ grid, which we define as
follows.
\begin{definition}
  The $n \times m$ \textbf{grid} is the set $\grid$, and the elements
  of this set are called \textbf{cells}.
\end{definition}
When illustrating grids, we use the convention that the $n \times m$ grid has
$n$ columns and $m$ rows, which are described using $0$-indexed Cartesian
coordinates, where
$(0,0)$ is the cell in the lower left corner and
$(n-1, m-1)$ is the cell in the upper right corner.

\subsection{Symmetries of the grid}
We will count grids up to various symmetries, some of which may be specified by
subgroups of the dihedral group of the square,
\(R \leq D_8 = \langle r, f \mid r^4 = f^2 = (rf)^2 = \id \rangle\).
Because this is a group of \underline{r}otations and \underline{r}eflections of
the grid, we call this subgroup $R$. When considering the $n \times m$ grid for
$n \neq m$, we will further specify that $R \leq D_4$, where
$D_4 = \langle r^2, f \mid (r^2)^2 = f^2 = \id \rangle$ is the dihedral
group of the rectangle.\footnote{We will later see that we use $D_4$ in the case of the
$n \times n$ cylinder as well.}

In all cases, we will use the convention that our symmetry groups act on the
grid via \textit{right actions},
illustrated in Figure \ref{fig:dihedralConvention}. We will also use the
conventions that
$r$ acts on the grid by $+90^\circ$ rotations and
$f$ acts on the grid by horizontal reflection (i.e., over the vertical line).
Because the group acts on the right,
$rf$ reflects the square grid over the line $y = x$ and
$r^3f$ corresponds to matrix transposition.

\input{Illustrations/fig_dihedralConvention.tex}

Formally, we describe the action on the cell by specifying how the generators of
$D_8$ act.
\begin{definition}
  The (right) action of an element of $D_4$ on a cell $(x, y) \in \grid$ is
  given by
  \begin{alignat*}{2}
    (x,y) &\cdot f    &&= (n-1-x,y), \qquad\text{ and} \\
    (x,y) &\cdot r^2  &&= (n-1-x,m-1-y).
  \end{alignat*}

  In the case of an $n \times n$ grid, the action of $r \in D_8$ is given by
  \begin{equation}
    (x,y) \cdot r = (n-1-y, x).
  \end{equation}
  \label{def:dihedralAction}
\end{definition}
These actions can be extended to all of $D_4$ and $D_8$ via the binary operation
of the group, since the group action is specified for the generators.

\subsection{Symmetries of the cylinder and torus}

Now that we know how the dihedral group acts on the $n \times n$ and
$n \times m$ grids, we can also look at symmetries of the grid by cyclic
shifting of rows and/or columns. When we shift just the columns, we call this
a \textit{cylindrical action}, which we describe with the group $\Z/n\Z$;
when we shift the rows and columns, we call this a \textit{toroidal},
which we describe with the group $\Z/n\Z \times \Z/m\Z$.
Both of these are named in reference to the corresponding topological
identification of the square.

\begin{definition}
  The \textbf{cylindrical action} of $a \in \Z/n\Z$ on a cell
  $(x,y) \in \grid$
  corresponds to a (rightward) cyclic shift of columns: \[
    (x,y) \cdot a = (x+a,y).
  \]
  \label{def:cylindricalAction}
\end{definition}

\begin{definition}
  The \textbf{toroidal} of
  $(a,b) \in \Z/n \Z \times \Z/m \Z$ on a cell
  $(x,y) \in \grid$
  corresponds to
  a (rightward) cyclic shift of columns and
  an (upward) cyclic shift of rows: \[
    (x,y) \cdot (a,b) = (x+a,y+b).
  \]
  \label{def:torusAction}
\end{definition}
Definition \ref{def:torusAction} is illustrated in Figure \ref{fig:torusAction}.
\input{Illustrations/fig_torusAction.tex}

\subsection{Compatibility of grid symmetries}
Notice that we can act on the grid with both the dihedral actions and the
cylindrical/toroidal actions.
In order to make the group actions of the dihedral group compatible with the
cylindrical action ($\Z/n\Z$)
or the toroidal action ($\grid$),
we define their (outer) semidirect product,
$\cylinderSymmetries$
or
$\torusSymmetries$ respectively.
As in the examples above, we define this as a right action,
thinking of this as first cyclically shifting the rows
and columns and then rotating or reflecting according to the element $R$.

The outer semidirect products are defined with respect to the homomorphisms
$\psi\colon D_4 \to \operatorname{Aut}(\Z/n\Z)$
and
$\phi\colon D_8 \to \operatorname{Aut}(\grid)$
respectively. (We use $D_4$ rather than $D_8$ in the case of the cylinder
because a $90^\circ$ rotation is not an isometry of the infinite strip, which
is the universal cover of the cylinder.)

\begin{definition}
Let $\psi\colon D_4 \to \operatorname{Aut}(\Z/n\Z)$ be
given by
\begin{alignat*}{2}
  \psi_f(x)     &= \psi_{r^2}(x)  &&= -x \text{ and}\\
  \psi_{\id}(x) &= \psi_{r^2f}(x) &&= x.
\end{alignat*}
Then the product of two elements in ${\Z/n\Z \rtimes D_4}$ is given by
\[
  \left(a_1,g_1\right)
  \left(a_2,g_2\right)
  =
  \left(a_1+\psi_{g_1}(a_1),g_1g_2\right).
\]
\end{definition}

In the case of the torus, the definition of the semidirect product
$\torusSymmetries$, where
$R \leq D_8$, is essentially similar.

\begin{definition}
  Let $\phi\colon D_8 \to \operatorname{Aut}(\grid)$
  be defined on the generators $r$ and $f$ by
  \begin{align*}
    \phi_f((x,y)) &= (-x,  y) \text{ and}\\
    \phi_r((x,y)) &= ( y, -x),
  \end{align*}
  and extended to the other elements of $D_8$.
  Then the binary operation of the semidirect product of
  $(\grid) \rtimes D_8$ is given by
  \[
    \ps{a_1}{b_1}{g_1}
    \ps{a_2}{b_2}{g_2}
    =
    \left((a_1,a_2)+\phi_{g_1}(a_1,a_2),g_1g_2\right).
  \]
\end{definition}
Using the facts that $r$ and $f$ generate $D_8$ and $\phi$ is a
homomorphism, together with function composition yields:
\begin{alignat*}{4}
  &\phi_{\id}  ((x,y)) &&= ( x, y), \hspace{0.45cm}
  &&\phi_{r}   ((x,y)) &&= ( y,-x), \\
  &\phi_{r^2}  ((x,y)) &&= (-x,-y), \hspace{0.45cm}
  &&\phi_{r^3} ((x,y)) &&= (-y, x), \\
  &\phi_f      ((x,y)) &&= (-x, y), \hspace{0.45cm}
  &&\phi_{rf}  ((x,y)) &&= ( y, x), \\
  &\phi_{r^2f} ((x,y)) &&= ( x,-y), \hspace{0.45cm}
  &&\phi_{r^3f}((x,y)) &&= (-y,-x).
\end{alignat*}

\begin{example}
  We check our work on an individual cell.
  For every choice of tile and pair of symmetries, we should have \[
    \left((x,y)\cdot\ps{a_1}{b_1}{g_1}\right) \cdot \ps{a_2}{b_2}{g_2}
    =
    (x,y) \cdot \left(\ps{a_1}{b_1}{g_1}\ps{a_2}{b_2}{g_2}\right).
  \]
  In particular, we check in the case of the $4 \times 4$ torus with
  $(x,y) = (1,0)$,
  $\ps{a_1}{b_1}{g_1} = \ps11f$
  and
  $\ps{a_2}{b_2}{g_2} = \ps20r$.

  \begin{align*}
    \left((1,0) \cdot \ps11f\right) \cdot \ps20r
    &= \left((2,1) \cdot f \right) \cdot \ps20r \\
    &= (1,1) \cdot \ps20r \\
    &= (3,1) \cdot r \\
    &= (2,3).
  \end{align*}
  Now using the semidirect product, \begin{align*}
    (1,0)    \cdot \left(\ps11f\ps20r\right)
    &= (1,0) \cdot \left((1,1) + \phi_f(2,0), fr\right) \\
    &= (1,0) \cdot \left((1,1) + (-2,0), r^3f\right) \\
    &= (1,0) \cdot \ps31{r^3f} \\
    &= (0,1) \cdot r^3f \\
    &= (2,3).
  \end{align*}
  This suggests that this semidirect product is the appropriate way to make the
  dihedral actions compatible with the toroidal action.
\end{example}

\subsection{Symmetries of tile designs}
We are now ready to start filling in our grid with tiles. Before defining
what tiles are, we introduce the following definition for convenience.
\begin{definition}
  If $X$ is a set and $G$ has a group action on $X$, then we call $X$ a $G$\textbf{-set}.
\end{definition}
\begin{definition}
  Given $R \leq D_8$, a \textbf{set of tile designs} is simply an $R$-set.
  A \textbf{tile design} is any element of such a set.
\end{definition}

We will always illustrate our tile designs with squares that have
designs in them, but any abstract $R$-set will work in place of these
illustrations. When we specify one of these tile designs together with a
cell, we get a tile.
\begin{definition}
  A \textbf{tile} in the $n \times m$ grid with the set of tile designs $T$ is
  an element of $(\grid) \times T$.
\end{definition}
Now we are ready to define a tiling of the grid, which is a specification of a
tile design for each cell.
\begin{definition}
  A \textbf{tiling} of the $n \times m$ grid with the set of tile designs $T$ is
  a map $f\colon(\grid) \to T$.
  The tiles associated with the tiling are elements of the graph of the map \[
    \{\ps xy{f(x,y)} \mid (x,y) \in \grid\}.
  \]
\end{definition}
We next give an example to illustrate all of these definitions.
\begin{example}
  Suppose that $R = D_4 = \langle r^2, f \rangle$, the dihedral group of the
  rectangle. Then \[
    T = \left\{
      \tileColor[black!90!white],
      \tileVert,
      \tileDiag,
      \tileAdiag,
      \tileAsym{0},
      \tileAsym{2},
      \tileAsym{5},
      \tileAsym{7},
      \tileRR{1},
      \tileRR{2},
      \tileU,
      \tileD
    \right\}.
  \]
  is a set of tile designs, because it is an $R$-set.
  The $3 \times 2$ tiling \[
    \begin{tikzpicture}
      \fill[black!90!white] (0,0) rectangle (1,1);
      \fill[black!90!white] (2,1) rectangle (3,2);
      \fill (0,1) rectangle (1/3,2)
            (2/3,1) rectangle (1,2);
      \fill (1,1) -- (1.5,2) -- (2,1) -- cycle;
      \fill (1,0) -- (2,0) -- (2,1/2) -- cycle;
      \fill (2,1) -- (2.5,0) -- (3,1) -- cycle;
      \draw[gray] (0,0) grid (3,2);
    \end{tikzpicture}
  \] consists of the six tiles \[
    \left\{
    \ps00{\tileColor[black!90!white]}
    \ps01{\tileVert}
    \ps10{\tileAsym{7}}
    \ps11{\tileU}
    \ps20{\tileD}
    \ps21{\tileColor[black!90!white]}
    \right\}.
  \]
\end{example}

Since we have now defined tiles, we are ready to talk about how the symmetries
of our grid, cylinder, or torus act on tiles: dihedral
actions can act on the tile design nontrivially, but cylindrical/toroidal
actions always act on a tile design by the identity.
We extend Definitions \ref{def:dihedralAction}, \ref{def:cylindricalAction}, and
\ref{def:torusAction} to this setting in a direct way, and illustrate this
in Figure \ref{fig:dihedralAction}.

\begin{definition}
  If $\xyd$ is a tile in an $n \times m$ grid, then
  $g \in D_4$ acts on $\xyd$ by \begin{alignat*}{2}
    \xyd &\cdot \id  &&= \xyd, \\
    \xyd &\cdot r^2  &&= \ps{n-1-x}{m-1-y}{d\cdot  r^2}, \\
    \xyd &\cdot f    &&= \ps{n-1-x}{    y}{d\cdot    f}, \text{ and} \\
    \xyd &\cdot r^2f &&= \ps{    x}{m-1-y}{d\cdot r^2f}.
  \end{alignat*}
  Furthermore, if $\xyd$ is a tile in an $n \times n$ grid, then
  $g \in D_8$ acts on $\xyd$ by the above actions together with
  \begin{alignat*}{2}
    \xyd &\cdot r    &&= \ps{n-1-y}{    x}{d\cdot    r}, \\
    \xyd &\cdot r^3  &&= \ps{    y}{n-1-x}{d\cdot  r^3}, \\
    \xyd &\cdot rf   &&= \ps{    y}{    x}{d\cdot   rf}, \text{ and} \\
    \xyd &\cdot r^3f &&= \ps{n-1-y}{n-1-x}{d\cdot r^3f}.
  \end{alignat*}
  \label{def:groupActionOnTile}
\end{definition}

\input{Illustrations/fig_dihedralAction.tex}

In order to understand what makes two tiles \textit{essentially different} with
respect to counting tilings, it is useful to define the notion of a stabilizer
subgroup.
\begin{definition}
  Let $X$ be a $G$-set. Then the \textbf{stabilizer subgroup} of an element
  $x \in X$ is the subgroup \[
    G_x = \{g \in G \mid x \cdot g = x\} \leq G.
  \]
\end{definition}

Because our set of tile designs $T$ is an $R$-set, the relevant difference
between different tile designs for the purpose of counting tilings is their
stabilizer subgroups.

\subsection{Classifying sets of tile designs}
In order to describe the essential features of a set of tile designs, we
partition it into orbits with respect to $R$. By counting up the number of
orbits and classifying each orbit by the (conjugacy class of the) stabilizer
subgroup of one of its representatives we can understand the combinatorics
of the set of tile designs completely.

\begin{definition}
  Let $R \subseteq D_8$ and let $T$ be a set of tile designs (with respect to $R$).
  Then for each (conjugacy class of) a subgroup $S \leq R$, let
  $\mathcal{O}^R_{S}$ denote the number of orbits that contain a tile
  whose stabilizer subgroup is conjugate to $S$.
\end{definition}

Notice that we classify up to conjugacy class because if $d$ is stable under
$S$, then $d \cdot g$ is stable under $g^{-1}Sg$
since $(d \cdot g)\cdot g^{-1}Sg = d \cdot Sg = d \cdot g$.

\begin{example}
  Suppose we are counting tilings of the grid, cylinder, or torus up to
  horizontal and vertical reflection with a set of tile designs given by
  \[
    T = \left\{
      \tileColor[black!90!white],
      \tileVert,
      \tileRR{3},
      \tileRR{0},
      \tileNW,
      \tileNE,
      \tileSW,
      \tileSE,
      \tileRR{1},
      \tileRR{2},
      \tileU,
      \tileD
    \right\}.
  \]
  Since the symmetry group $D_4 = \langle r^2, f \ |\ (r^2)^2 = f^2 = \id\rangle$
  has $5$ conjugacy classes of subgroups, there are five types of orbits:
  \begin{alignat*}{2}
    \orb{r^2,f}{r^2,f} &= 2 &&\qquad\text{via}\quad\left\{\tileColor[black!90!white]\right\} \text{ and } \left\{\tileVert\right\} \\
    \orb{r^2,f}{f}     &= 1 &&\qquad\text{via}\quad\left\{\tileU, \tileD\right\} \\
    \orb{r^2,f}{r^2}   &= 2 &&\qquad\text{via}\quad\left\{\tileRR{1}, \tileRR{2}\right\} \text{ and } \left\{\tileRR{3}, \tileRR{0}\right\} \\
    \orb{r^2,f}{r^2f}  &= 0 && \\
    \orbid{r^2,f}      &= 1 &&\qquad\text{via}\quad\left\{\tileNW,\tileNE,\tileSW,\tileSE\right\}.
  \end{alignat*}
  \end{example}

\begin{lemma}
The number of tilings for a given $R$-tiling $T$ only depends on the tuple
\[
  \bigoplus_{S \in \operatorname{conj}(R)} \mathcal{O}^R_{S},
\] where $\operatorname{conj}(R)$ is the set of equivalence classes of subgroups
of $R$ up to conjugacy.
\end{lemma}
\begin{proof}
  Suppose that we have two sets of tile designs $T$ and $T'$ with the same
  number of orbits for each stabilizer conjugacy class.
  There exists a bijection
  $f \colon T \to T'$ such that
  $f(d) = d'$ whenever $d$ and $d'$ have the same
  stabilizer subgroup in $R$, that is, $R_d = R_{d'}$.
  Then the induced map of $f$ to the tilings is also bijection of tilings.
\end{proof}
In Appendix \ref{apss:nXnTorusSequences}, we explicitly enumerate all of the
$R$-sets of tile designs that consist of a single orbit
for each subgroup $R \leq D_4$ or $R \leq D_8$.

\subsection{Counting strategy}
In order to count how many tilings exist up to various symmetries, we will use
Burnside's lemma.
\begin{theorem}[Burnside's lemma]
  Let $X$ be a $G$-set. Then the size of $X$ up to the action of $G$ is \[
    |X/G| = \frac{1}{|G|}\sum_{g \in G}|X^g|,
  \] where $|X^g|$ is the number of elements of $X$ that are fixed under the
  action of $g \in G$.
\end{theorem}
We want to understand how many tilings are fixed under various symmetries. To
do this it is necessary to categorize the symmetries of various tiles.
\begin{definition}
  Let $T$ be a set of tile designs, where $R \leq D_8$.
  For each $g \in R$, the set of tiles that are fixed by $g$ is denoted
  \[
    T^g = \{d \in T \mid d \cdot g = d\},
  \]
  and the size of this set is denoted
  \[
    t_g = |T^g|.
  \]
\end{definition}

Note that $T^{\id} = T$, so $t_{\id}$ is the total number of tile designs.

The following theorem gives us a strategy for counting the number of tilings
that are fixed under a given symmetry, which is
illustrated in Figure \ref{fig:cellOrbits}. For more thorough treatment in
the case of Truchet tiles in particular, see Hall, Almeida, and Teixeira \cite{Hall}.

\begin{theorem}
  Suppose that $s = g \in R$,
  $s = (a,g) \in \cylinderSymmetries$, or
  $s = \abg \in \torusSymmetries$.

  Since the set of cells $\grid$ form an $\langle s \rangle$-set, we
  partition the cells into orbits with respect to the cyclic subgroup
  $\langle s \rangle$, which we call $\Theta_s$, so that
  $\bigsqcup_{\vartheta \in \Theta_s} \vartheta = \grid$.

  Then if $X^s$ is the set of tilings of the $n \times m$ grid that are
  stable under $s$,
  \[
    |X^s| = \prod_{\vartheta \in \Theta_s} t_{g^{|\vartheta|}}.
  \]
\end{theorem}
\begin{proof}
  Because $\Theta_s$ partitions the cells into orbits with respect to the cyclic
  subgroup $\langle s \rangle$, the number of tilings that are fixed under $s$
  is equal to the product of the number of tilings of each orbit of cells
  under $\langle s \rangle$.

  The tiling of an orbit of cells can be specified by a single tile $d$, which
  then  determines the rest of the orbit by $\xyd \cdot s^k$ for
  $0 \leq k < |\vartheta|$. The only requirement for a valid tiling of a orbit
  is that \[
    \xyd = \xyd \cdot s^{|\vartheta|} = \ps{x}{y}{d \cdot g^{|\vartheta|}},
  \] thus $d$ must be fixed by $g^{|\vartheta|}$,
  and so $d \in T^{g^{|\vartheta|}}$.
  Therefore there are $t_{g^{|\vartheta|}}$ choices for $d$ and thus for the
  orbit of cells containing $(x,y)$.
\end{proof}

Thus, this reduces the problem to a matter of counting the orbits of cells
under each symmetry $s$ along with counting the sizes of each of these
orbits.

We proceed with Sections \ref{sec:grid}, \ref{sec:cylinder}, and
\ref{sec:torus}, which all implement the above strategy.
Each section consists broadly of fixed point counting theorems,
which count tilings of the grid that are fixed under the actions of
$D_4$ or $D_8$ for arbitrary sets of tile designs.

\input{Illustrations/fig_cellOrbits.tex}

\section{Grid}
\label{sec:grid}
For counting tilings of the $n \times m$ rectangular grid or $n \times n$ square
grid under subgroups $R \leq D_4$ and $R \leq D_8$ respectively, we
count the number of tilings that are fixed under each element of $R$.

In the following two subsections, we denote the rectangular grid by $\RG$
and the square grid $\SG$.
\subsection{The \texorpdfstring{$n \times m$}{n by m} grid}
We begin by specifying the number of tilings that are fixed under each symmetry.
\begin{definition}
  For a given set of tile designs $T$, and an element
  \(
    g \in R \leq D_4,
  \)
  the number of tilings of the $n \times m$ grid by tile designs in $T$
  that are fixed by $g$ is denoted $\fxpt^\RG_g(n,m)$.
\end{definition}

\begin{theorem}
  For a given set of tile designs $T$ and an element $g \in R \leq D_4$,
  the number of tilings of the $n \times m$ grid by tile designs in $T$
  that are fixed by $g$ is
  \begin{align}
    \fxpt^\RG_{\id}(n,m) &= t_{\id}^{nm}.
    \label{eq:fxpt_R_id}
    \\
    \fxpt^\RG_{r^2}(n,m) &= \begin{cases}
      t_{\id}^{nm/2},            & \text{if $nm$ is even;} \\
      t_{\id}^{(nm-1)/2}t_{r^2}, & \text{if $nm$ is odd.}
    \end{cases}
    \label{eq:fxpt_R_rr}
    \\
    \fxpt^\RG_{f}(n,m) &= \begin{cases}
      t_{\id}^{nm/2},            & \text{if $n$ is even;} \\
      t_{\id}^{(m(n-1))/2}t_f^m, & \text{if $n$ is odd.}
    \end{cases}
    \label{eq:fxpt_R_f}
    \\
    \fxpt^\RG_{r^2f}(n,m) &= \begin{cases}
      t_{\id}^{nm/2},                 & \text{if $m$ is even;} \\
      t_{\id}^{(n(m-1))/2}t_{r^2f}^n, & \text{if $m$ is odd.}
    \end{cases}
    \label{eq:fxpt_R_rrf}
  \end{align}
  Then the number of distinct tilings of the $n \times m$ grid up to action of
  $R$ is given by
  \begin{equation}
    \frac{1}{|R|}\sum_{g \in R} \fxpt^\RG_g(n,m).
    \label{eq:distinctTilingsR}
  \end{equation}
  \label{thm:nXmGridFormulae}
\end{theorem}
\begin{proof} The proof will consist of three cases.

  \begin{description}
    \item[Equation \eqref{eq:fxpt_R_id}.]
    This follows from the fact that $t_{\id}$ is the
    number of distinct tiles, and every tiling is fixed under $\id \in D_4$.
    \item[Equation \eqref{eq:fxpt_R_rr}.]
    This follows from the fact that the (right) action of $r^2$ on the cell
    $(x,y)$ is \[
      (x,y) \cdot r^2 = (n-x-1, m-y-1).
    \] Since $r^2$ has order $2$, each cell is in an orbit of size $1$ or $2$.
    The cell $(x,y)$ is fixed under the action of $r^2$ if and only if
    $n$ and $m$ are both odd and $(x,y) = (\frac{n-1}{2}, \frac{m-1}{2})$.

    Therefore when $nm$ is even, the grid is partitioned into $nm/2$ orbits of
    size $2$, so any fixed tiling can be specified by choosing any tile design
    in $T$ for each orbit.
    When $nm$ is odd, the grid is partitioned into one orbit of size $1$
    together with $(nm-1)/2$ orbits of size $2$,
    so any fixed tiling can be specified by choosing a tile design in $T^{r^2}$
    for the fixed point and any tile design in $T$ for each orbit.
    \item[Equations \eqref{eq:fxpt_R_f} and \eqref{eq:fxpt_R_rrf}.]
    These two equations are essentially the
    same, so without loss of generality, we will prove the case of
    Equation \eqref{eq:fxpt_R_f}. The right action of $f$ on $\xyd$ is \[
      \xyd \cdot f = ((n - x - 1, m), d \cdot f).
    \] Because $f$ is order $2$, we can conclude that $(x,y)$ is either a fixed
    point or a $2$-cycle with respect to $f$. It follows that $(x,y)$ is a fixed
    point if and only if $n$ is odd and $x = (n - 1)/2$, therefore when $n$ is
    odd the tiling has $m$ fixed cells.
    The fixed cells can be specified by any tile design in $T^f$, and the cells
    in orbits of size $2$ can be specified by any tile design in $T$.
    \item[Equation \eqref{eq:distinctTilingsR}] Finally, this is a direct
    application of Burnside's lemma.
  \end{description}
\end{proof}

\subsection{The \texorpdfstring{$n \times n$}{n by n} grid}
There are more symmetries and some specializations in the case of the
$n \times n$ grid, which we denote $\SG$ for ``square grid''.

\begin{definition}
  For a given set of tile designs $T$, and an element
  \(
    g \in R \leq D_8,
  \)
  the number of tilings of the $n \times n$ grid by tile designs in $T$
  that are fixed by $g$ is denoted $\fxpt^\SG_g(n)$.
\end{definition}

\begin{theorem}
  For a given set of tile designs $T$ and an element $g \in R \leq D_8$,
  the number of tilings of the $n \times m$ grid by tile designs in $T$
  that are fixed by $g$ is \begin{align}
    \fxpt^{\SG}_{\id}(n)
    &= \fxpt^\RG_{\id}(n,n) = t_{\id}^{n^2}
    \label{eq:fxpt_S_id}
    \\
    \fxpt^{\SG}_{r^2}(n)
    &= \fxpt^\RG_{r^2}(n,n) = \begin{cases}
      t_{\id}^{n^2/2},            & \text{if $n$ is even;} \\
      t_{\id}^{(n^2-1)/2}t_{r^2}, & \text{if $n$ is odd.}
    \end{cases}
    \label{eq:fxpt_S_rr}
    \\
    \fxpt^{\SG}_{f}(n)
    &= \fxpt^\RG_f(n,n) = \begin{cases}
      t_{\id}^{n^2/2},            & \text{if $n$ is even;} \\
      t_{\id}^{(n^2-n)/2}t_{f}^n, & \text{if $n$ is odd.}
    \end{cases}
    \label{eq:fxpt_S_f}
    \\
    \fxpt^{\SG}_{r^2f}(n)
    &= \fxpt^\RG_{r^2f}(n,n) = \begin{cases}
      t_{\id}^{n^2/2},               & \text{if $n$ is even;} \\
      t_{\id}^{(n^2-n)/2}t_{r^2f}^n, & \text{if $n$ is odd.}
    \end{cases}
    \label{eq:fxpt_S_rrf}
    \\
    \fxpt^{\SG}_r(n)
    &= \fxpt^{\SG}_{r^3}(n) = \begin{cases}
      t_{\id}^{n^2/4},          & \text{if $n$ is even;} \\
      t_{\id}^{(n^2-1)/4}t_{r}, & \text{if $n$ is odd.}
    \end{cases}
    \label{eq:fxpt_S_r}
    \\
    \fxpt^{\SG}_{rf}(n)
    &= t_{\id}^{(n^2-n)/2}t_{rf}^n.
    \label{eq:fxpt_S_rf}
    \\
    \fxpt^{\SG}_{r^3f}(n)
    &= t_{\id}^{(n^2-n)/2}t_{r^3f}^n.
    \label{eq:fxpt_S_rrrf}
  \end{align}
  Then the number of distinct tilings of the $n \times n$ grid up to the
  dihedral action of the square is given by
  \begin{equation}
    \frac{1}{|R|}\sum_{g \in R} \fxpt^{\SG}_g(n).
    \label{eq:distinctTilingsS}
  \end{equation}
  \label{thm:nXnGridFormulae}
\end{theorem}
\begin{proof} This proof proceeds with four cases.
  \begin{description}
    \item[Equations \eqref{eq:fxpt_S_id}, \eqref{eq:fxpt_S_rr}, \eqref{eq:fxpt_S_f}, and \eqref{eq:fxpt_S_rrf}.]
    These follow directly from Theorem \ref{thm:nXmGridFormulae}, by specifying $m = n$.
    \item[Equation \eqref{eq:fxpt_S_r}.]
    Firstly, notice that the tilings that are fixed under $r$ are identically
    those that are fixed under $r^{-1} = r^3$.
    The (right) action of $r \in D_8$ on a cell $(x,y)$ is \[
      (x,y) \cdot r = (n - y - 1, x)
    \] therefore $(a,b)$ is a fixed point if and only if it satisfies the
    system of equations \begin{align}
      a &= n - b - 1 \\
      b &= a,
    \end{align} which has an integer solution only when $n$ is odd and when
    $(a,b) = (\frac{n - 1}{2}, \frac{n - 1}{2})$.
    Also, there are no cells that occur in $2$-cycles. This can be seen by
    noticing that cells that occur in $2$-cycles are also fixed points under
    $r^2$, and by the proof of Theorem \ref{thm:nXmGridFormulae}, we know that
    this occurs under the same conditions as the fixed points under $f$.
    Therefore all other cells occur in $4$-cycles.

    Therefore when $n$ is even, the grid is partitioned into $n^2/4$ orbits of
    size $4$, each of which can be specified by any tile design in $T$;
    when $n$ is odd, the grid has one fixed point, which must be tiled with a
    tile design in $T^r$, and the remaining cells can be partitioned
    into $(n^2 - 1)/4$ orbits of size $4$,
    each of which can be specified by any tile design in $T$.
    \item[Equations \eqref{eq:fxpt_S_rf} and \eqref{eq:fxpt_S_rrrf}.]
    Because $rf$ and $r^3f$ are conjugate, these are essentially similar, so
    without loss of generality, we will prove Equation \eqref{eq:fxpt_S_rf}.

    The (right) action of $rf \in D_8$ on a cell $(x,y)$ is \[
      (x,y) \cdot rf = (y,x).
    \] Thus, $(x,y)$ is a fixed point if and only if $x = y$, otherwise it is
    a part of a $2$-cycle. Therefore there are $n$ fixed points, which can be
    specified by a tile design in $T^{rf}$ and $(n^2 - n)/2$ $2$-cycles, which
    can be specified with any tile design in $T$.
    \item[Equation \eqref{eq:distinctTilingsS}.]
    The final equation follows by a direct application of Burnside's lemma.
  \end{description}
\end{proof}

\section{Cylinder}
\label{sec:cylinder}
Here we use the convention that the $n \times m$ cylinder is identified along
its left and right sides, as illustrated in Figure \ref{fig:cylinderIdentification}.

Even in the case of $n \times n$ grids, we only consider tilings of cylinders up
to subgroups of the dihedral group of the rectangle,
because other symmetries of the square would result in swapping
the pair of identified sides (the right and left side) of the grid with the pair
of non-identified sides (the top and bottom).

In both the case of the cylinder and the torus, we will repeatedly use the
following observation.
\begin{lemma}
  For fixed values of $n$ and $a$, the equation \begin{equation}
    x \equiv -1 - x - a \pmod n
    \label{eq:flip_solution}
  \end{equation} has solutions that depend on the parity of $n$ and $a$.

  \noindent
  When $n$ is odd, there is one solution: \begin{equation}
    x \equiv \frac{n+1}{2}(-1-a) \pmod{n}.
    \label{eq:flip_solution_odd_n}
  \end{equation}
  When $n$ is even and $a$ is odd, there are two solutions: \begin{align}
    x &\equiv \frac{-1-a}{2} \pmod n
    \label{eq:flip_solution_even_n1}
    \\[10pt]
    x &\equiv \frac{n-1-a}{2} \pmod n.
    \label{eq:flip_solution_even_n2}
  \end{align}
  When $n$ and $a$ are both even, there are no solutions.
  \label{lem:flip_solution}
\end{lemma}
\begin{proof}
  In both cases, we write equation \eqref{eq:flip_solution} as \[
    2x \equiv -1 - a \pmod{n}.
  \]
  \begin{description}
    \item[Odd $n$.] When $n$ is odd, $2$ has a multiplicative inverse of
    $(n+1)/2$, so multiplying gives the unique solution described in
    equation \eqref{eq:flip_solution_odd_n}.
    \item[Even $n$ and odd $a$.] When $n$ is even and $a$ is odd,
    $-1-a$ is even. Dividing by $2$ gives the solution given in
    equation \eqref{eq:flip_solution_even_n1}, and
    adding $n$ and dividing by $2$ gives the solution in equation
    \eqref{eq:flip_solution_even_n2}.
    \item[Even $n$ and $a$.] When both $n$ and $a$ are even,
    $2x$ is even and $-1-a$ is odd, so there are no solutions.
  \end{description}
\end{proof}
Similarly, we will repeatedly use the following lemma when counting fixed points
for both the cylinder and the torus.
\begin{lemma}[\cite{MacMahon}]
  Given some $a \in \Z/n\Z$, if $d$ is a minimal solution to the equation \[
    da \equiv 0 \pmod n
  \] then $d \mid n$.
  Moreover, when $d$ is a divisor of $n$, there are $\varphi(d)$ choices for
  $a$ that result in $d$ being a minimal solution, where $\varphi$ is
  Euler's totient function.
  \label{lem:eulerPhi}
\end{lemma}
\begin{proof}
  First, we can see that the least value of $da$ will occur when
  $da = \lcm(a,n)$, and thus \[d = \lcm(a,n)/a = n/\gcd(a,n).\]
  Therefore $d$ must be a divisor of $n$.
  The $\varphi(d)$ choices for $a$ such that $d$ is a minimal solution to
  ${da \equiv 0 \pmod n}$ are
  $a \in \left\{kn/d \mid 1 \leq k \leq d\ \text{and}\ \gcd(k,d) = 1\right\}$.
\end{proof}
\subsection{The \texorpdfstring{$n \times m$}{n by m} cylinder}
We denote the $n \times m$ cylinder by the superscript $\CY$.
\begin{definition}
  For a given set of tile designs $T$, and an element
  \(g \in R \leq D_4\)
  the sum over all cyclic shifts of the number of tilings of the $n \times m$
  cylinder by tile designs in $T$ that are fixed by
  $(a,g) \in \cylinderSymmetries$
  is denoted \[
    \fxpt^\CY_g(n,m) = \sum_{a \in \Z/n\Z} X^{(a,g)},
  \] where $X^{(a,g)}$ is the number of tilings fixed by $(a,g)$.
\end{definition}

\begin{theorem}
  The sum over all cyclic shifts of the number of tilings of the $n \times m$
  cylinder by tile designs in $T$ that are fixed by
  $(a,\id) \in \cylinderSymmetries$
  is given by
  \begin{equation}
    \fxpt^\CY_{\id}(n,m) = \sum_{d | n} \varphi(d)t_{\id}^{nm/d}.
    \label{eq:fxpt_C_id}
  \end{equation}
\end{theorem}
\begin{proof}
  For each element $(a, \id) \in \cylinderSymmetries$, the size of the orbits
  is the least $d$ such that \(
      da \equiv 0 \pmod n.
  \)
  By Lemma \ref{lem:eulerPhi}, when $d \mid n$ there are $\varphi(d)$ choices
  for $a$ that result in orbits of size $d$, and each choice partitions the
  $n \times m$ grid into $nm/d$ orbits.
\end{proof}

The next theorem concerns the action of $(a,r^2) \in \cylinderSymmetries$, which is illustrated in Figure \ref{fig:cylinderShiftAndRotate}.
\begin{theorem}
  The sum over all cyclic shifts of the number of tilings of the $n \times m$
  cylinder by tile designs in $T$ that are fixed by
  $(a,r^2) \in \cylinderSymmetries$
  is given by
  \begin{subnumcases}{\fxpt^\CY_{r^2}(n,m) =}
      nt_{\id}^{nm/2},
      & if $m$ is even; \label{eq:fxpt_C_rr_1}
      \\[10pt]
      \displaystyle
      n\!\left(
        \frac12 t_{\id}^{nm/2} +
        \frac12 t_{\id}^{(nm-2)/2}t_{r^2}^{2}
      \right),
      & if $m$ is odd and $n$ is even; \label{eq:fxpt_C_rr_2}
      \\[10pt]
      nt_{\id}^{(nm-1)/2}t_{r^2},
      & if $m$ and $n$ are odd. \label{eq:fxpt_C_rr_3}
  \end{subnumcases}
\end{theorem}
\begin{proof}
  The right action of $(a,r^2)$ on $\xyd$ is \begin{equation}
    \xyd \cdot (a,r^2) = ((n - 1 - x - a, m - 1 - y), d \cdot r^2).
  \end{equation}
  By applying this map twice, we see that $\xyd^2 = \id$, so each
  orbit is either size $1$ or size $2$. Orbits are size $1$ precisely when
  \begin{align}
    x &\equiv -1 - x - a \pmod n \\
    y &= m - y - 1.
  \end{align}
  \begin{description}
    \item[Equation \eqref{eq:fxpt_C_rr_1}.]
    When $m$ is even, $2y \neq m - 1$, so there are no solutions to this
    system of equations. Thus all orbits have size $2$ totaling $nm/2$ orbits.
    We can choose any tile design in $T$ to start this orbit. Then we sum this
    over all $n$ choices of $a \in \Z/n\Z$.
    \item[Equation \eqref{eq:fxpt_C_rr_2}.]
    When $m$ is odd, the second equation has the unique solution of
    $y = (m-1)/2$, which represents the middle row.
    The solutions for the second equation follow directly from Lemma
    \ref{lem:flip_solution}, which states that when $n$ is even, the
    equation has two solutions when $x$ is odd and none otherwise;
    when $n$ is odd the second equation has a single solution.

    Therefore when $m$ is odd and $n$ is even, half of the choices of
    $a \in \Z/n\Z$ result in no orbits of size $1$, and the other half of
    choices of $x$ result in two orbits of size $1$.
    In the former case, the grid decomposes into $nm/2$ orbits of size $2$,
    each of which can be filled with any tile design.
    In the latter case, there are two orbits of size $1$, which must be filled
    with a tile that is fixed under $r^2$, and the rest of the grid decomposes
    into $(nm-2)/2$ orbits all of size $2$, which can be filled with any tile
    design.
    \item[Equation \eqref{eq:fxpt_C_rr_3}.]
    Lastly, when both $m$ and $n$ are odd, there is a single orbit of size $1$
    that must be filled with a tile that is fixed under $r^2$, the remaining
    $nm-1$ cells are partitioned into $(nm-1)/2$ orbits of size $2$ that can
    be filled with any tile design.
  \end{description}
\end{proof}

\input{Illustrations/fig_cylinderShiftAndRotate.tex}

The next theorem concerns the action of $(a,f) \in \cylinderSymmetries$, which is illustrated in Figure \ref{fig:cylinderShiftAndFlip}.
\begin{theorem}
  The sum over all cyclic shifts of the number of tilings of the $n \times m$
  cylinder by tile designs in $T$ that are fixed by
  $(a,f) \in \cylinderSymmetries$
  is given by
  \begin{subnumcases}{\fxpt^\CY_{f}(n,m) =}
    \displaystyle
    n\!\left(
      \frac12 t_{\id}^{nm/2} +
      \frac12 t_{\id}^{(nm-2m)/2}t_f^{2m}
    \right),
    & if $n$ is even; \label{eq:fxpt_C_f_1}
    \\[10pt]
    nt_{\id}^{(nm-m)/2}t_f^m,
    & if $n$ is odd. \label{eq:fxpt_C_f_2}
  \end{subnumcases}
\end{theorem}
\begin{proof}
  Since $(a,f)^2 = \id$, every tile is either a fixed point or
  appears in a $2$-cycle under $(a,f)$.
  The right action of $(a,f)$ on $\xyd$ is \[
    \xyd \cdot (a,f) = \ps{-x-a-1}{y}{d \cdot f}
  \] so the tiles that appear as fixed points are those that satisfy \[
    x = - 1 - x - a \pmod n.
  \]
  \begin{description}
    \item[Equation \eqref{eq:fxpt_C_f_1}.]
    When $n$ and $a$ are both even, there are no fixed points.
    When $n$ is even and $a$ is odd, there are two fixed points in each row:
    \begin{align}
      x &\equiv (n - a - 1)/2 \pmod n \qquad \text{and}\\
      x &\equiv (2n - a - 1)/2 \pmod n.
    \end{align}
    \item[Equation \eqref{eq:fxpt_C_f_2}.]
    When $n$ is odd, there is one fixed cell in each row, which occurs when
    $x \equiv (-a-1)(n+1)/2 \pmod n$.
  \end{description}
\end{proof}

\input{Illustrations/fig_cylinderShiftAndFlip.tex}

\begin{theorem}
  The sum over all cyclic shifts of the number of tilings of the $n \times m$
  cylinder by tile designs in $T$ that are fixed by
  $(a,r^2f) \in \cylinderSymmetries$
  is given by
  \begin{subnumcases}{\fxpt^\CY_{r^2f}(n,m) =}
    \sum_{d | n} \varphi(d) t_{\id}^{nm/\lcm(d,2)},
    & if $m$ is even; \label{eq:fxpt_C_rrf_1}
    \\[10pt]
    \sum_{d | n} \varphi(d) t_{\id}^{(nm-n)/\lcm(d,2)}t_{(r^2f)^d}^{n/d},
    & if $m$ is odd. \label{eq:fxpt_C_rrf_2}
  \end{subnumcases}
\end{theorem}
\begin{proof}
  We can see that $(a,r^2f)$ acts on the coordinates of $(x,y)$ separately,
  that is, \[
    (x,y)\cdot(a,r^2f)^k = \begin{cases}
      (x + ka, m-1-y), & \text{if $k$ is odd;}\\
      (x + ka, y),     & \text{if $k$ is even.}
    \end{cases}
  \]

  Notice that the orbits of the $y$-coordinates have size $2$, so it is enough
  to determine the size of the orbits of the $x$-coordinates.
  By Lemma \ref{lem:eulerPhi}, for each divisor $d \mid n$, there are
  $\varphi(d)$ choices for $a$ such that the size of the orbits of the
  $x$-coordinate is $d$.

  \begin{description}
    \item[Equation \eqref{eq:fxpt_C_rrf_1}.]
    When $m$ is even, we see that $y \neq m - y - 1$ has no solutions,
    the orbit of every $y$-coordinate has size $2$.
    For each $x$-orbit size $d \mid n$,
    each cell must be in an orbit of size $\lcm(d,2)$, and there must
    $nm/\lcm(d,2)$ of them. Each can be specified by any tile design, since all
    tile designs are stable under $(r^2f)^{\lcm(d,2)} = \id$.
    \item[Equation \eqref{eq:fxpt_C_rrf_2}.]
    When $m$ is odd, we see that $y = m - y - 1$ has a solution precisely when
    $y = (m-1)/2$.
    For each $x$-orbit size $d \mid n$, if $y = (m-1)/2$, then the orbit has
    size $d$, otherwise it has size $\lcm(d,2)$, as in the case above.
    Therefore there are $n$ cells that are in orbits of size $d$ resulting
    in $n/d$ orbits that can be specified by any tile design that is stable
    under $(r^2f)^{\lcm(d,2)}$. The remaining $n^2-n$ cells are partitioned
    into $(n^2-n)/\lcm(d,2)$ orbits of size $\lcm(d,2)$ that can be specified
    by any tile design.
  \end{description}
\end{proof}

\begin{theorem}
  For
  a given set of tile designs $T$,
  a symmetry group $R \leq D_4$, and
  an element $g \in R$,
  the number of distinct tilings of the $n \times m$ cylinder is
  \begin{equation}
    \frac{1}{n|R|}\sum_{g \in R} \fxpt^\CY_g(n,m).
    \label{eq:distinctTilingsC}
  \end{equation}
\end{theorem}
\begin{proof}
  We will use the convention that
  when we index over $g$, implicitly $g \in R$;
  when we index over $a$, implicitly $a \in \Z/n\Z$; and
  when we index over $(a,g)$, implicitly $(a,g) \in \cylinderSymmetries$.

  Since $\fxpt^\CY_g(n,m) = \displaystyle\sum_a X^{(a,g)}$, we can see that
  \begin{align*}
    \frac{1}{n|R|}\sum_{g} \fxpt^\CY_g(n,m)
    &= \frac{1}{n|R|}\sum_{g} \sum_{a} X^{(a,g)} \\
    &= \frac{1}{|\cylinderSymmetries|}\sum_{(a,g)} X^{(a,g)},
  \end{align*}
  which counts the number of distinct tilings by a direct application of
  Burnside's lemma.
\end{proof}

\section{Torus}
\label{sec:torus}
This section builds on the work of
Ethier \cite{Ethier} and
Ethier and Lee \cite{EthierLee}. By
specializing to the set of tile designs
$T = \left\{\tileColor[black!80],\tileColor[black!20]\right\}$, we recover
their work.
Irvine \cite{Irvine} generalized this in the specific context of a set
of tile designs of size $n$ in the specific case that no rotation or reflection
is allowed (only cyclic shifting of rows and columns), which we recover in
Theorem \ref{thm:fxpt_Rt_id}.

We distinguish between the rectangular torus, which we denoted by \RT, and
the square torus, which we denote by \ST.
\subsection{The \texorpdfstring{$n \times m$}{n by m} torus}
\begin{definition}
  For a given set of tile designs $T$, and an element
  \(g \in R \leq D_4\)
  the sum over all cyclic shifts of the number of tilings of the $n \times m$
  cylinder by tile designs in $T$ that are fixed by
  $\abg \in (\Z/n \Z \times \Z/m \Z) \rtimes R$
  is denoted \[
    \fxpt^\RT_g(n,m) = \sum_{(a,b) \in \Z/n\Z\times\Z/m\Z} X^{\abg},
  \] where $X^{\abg}$ is the number of tilings fixed by $\abg$.
\end{definition}
\begin{theorem}
  The sum over all cyclic shifts of the number of tilings of the $n \times m$
  torus by tile designs in $T$ that are fixed by
  $(a,\id) \in \torusSymmetries$
  is given by
  \begin{equation}
  \fxpt^\RT_{\id}(n,m) = \sum_{c \mid m}\sum_{d \mid n}\varphi(c)\varphi(d) t_{\id}^{mn/\lcm(c,d)}.
  \label{eq:fxpt_TR_id}
  \end{equation}
  \label{thm:fxpt_Rt_id}
\end{theorem}
\begin{proof}
  The size of an orbit of a tile under $\abg^k$ is the set of solutions to
  \begin{align*}
    ka &\equiv 0 \pmod n \\
    kb &\equiv 0 \pmod m.
  \end{align*}

  For each individual equation, the minimal choice for $k$ must be a divisor of
  $n$.
  For a given divisor $d \mid n$, there are $\varphi(d)$ choices for $a \in \Z/n\Z$ so
  that $da \equiv 0 \pmod n$. Namely if $i$ is coprime to $d$, then
  $a = i\left(n/d\right)$ will be a minimal solution.
  An analogous argument holds for the second equation.

  Therefore if $d \mid n$ and $c \mid m$, there are $\varphi(d)\varphi(c)$ pairs
  $(a,b) \in \grid$ where $a$ has order $d$ and $b$ has order
  $c$, and thus $(a,b)$ has order $\lcm(d,c)$. Therefore, each orbit of cells
  has size $\lcm(d,c)$, and so the number of orbits of cells is $nm/\lcm(d,c)$.

  Thus, the sum of the number of orbits over each pair
  $(a,b) \in \grid$ gives equation \eqref{eq:fxpt_TR_id}, as desired.
\end{proof}

The next theorem concerns the action of $\ps ab{r^2} \in \torusSymmetries$, which is illustrated in Figure \ref{fig:torusShiftAndRotate180}.

\begin{theorem}
  The sum over all cyclic shifts of the number of tilings of the $n \times m$
  torus by tile designs in $T$ that are fixed by
  $(a,r^2) \in \torusSymmetries$
  is given by
  \begin{subnumcases}{\fxpt^\RT_{r^2}(n,m) =}
    \displaystyle
    nm\left(\frac34t_{\id}^{nm/2} + \frac14t_{\id}^{nm/2-2}t_{r^2}^4\right),
    & if $n$ and $m$ are even; \label{eq:fxpt_TR_rr_a}
    \\[10pt]
    \displaystyle
    nm t_{\id}^{(nm-1)/2}t_{r^2},
    & if $n$ and $m$ are odd; \label{eq:fxpt_TR_rr_b}
    \\[10pt]
    \displaystyle \label{eq:fxpt_TR_rr_c}
    nm\left(\frac12 t_{\id}^{nm/2} + \frac12 t_{\id}^{nm/2-1}t_{r^2}^2\right),
    & otherwise.
  \end{subnumcases}
  \label{thm:fxpt_Rt_rr}
\end{theorem}
\begin{proof}[Proof of Theorem \ref{thm:fxpt_Rt_rr}]
  The orbits of cells under the group generated by $\ps ab{r^2}$ have size
  either $1$ or $2$, because of how we defined the semidirect product,
  $\ps ab{r^2}$ has order $2$: \begin{equation}
    \ps ab{r^2}^2
    = \ps ab{r^2}\ps ab{r^2}
    = \left((a,b)+(-a,-b),r^2r^2\right)
    = \ps00{\id}.
    \label{eq:abrr_order_2}
  \end{equation}
  Therefore, it is enough to count how many cells are stable under
  $\ps ab{r^2}$, which depends on the parity of $n$, $m$, $a$, and $b$.

  The element $\ps ab{r^2}$ fixes a cell $(x,y)$ when \[
    (x,y)\cdot\ps ab{r^2} = (n-1-(x+a),n-1-(y+b)).
  \]
  This corresponds to the system of equations \begin{align}
    x \equiv - 1 - x - a &\pmod n \label{eq:fxpt_TR_rr_d}
    \\
    y \equiv - 1 - y - b &\pmod m, \label{eq:fxpt_TR_rr_e}
  \end{align} whose solutions are given by Lemma \ref{lem:flip_solution}.

  Therefore we proceed by each case
  \begin{description}
    \item[Equation \eqref{eq:fxpt_TR_rr_a}.]
    When $n$ and $m$ are even, there are fixed cells only when both $a$ and $b$
    are odd, by Lemma \ref{lem:flip_solution}; in this case, there are exactly
    $4$ fixed cells, because each equation in the system of equations has two
    solutions. When this occurs, it partitions the cells into
    $4$ orbits of size $1$,
    which can be filled with tile designs that are fixed under $r^2$, and
    $(nm-4)/2$ orbits of size $2$,
    which can be filled with any tile design.

    When either $a$ or $b$ is even, there are no fixed cells, which partitions
    the cells into $nm/2$ orbits of size $2$, each of which can be filled with
    any choice of tile design.

    Since the $4$ fixed cells occur for exactly one quarter of the pairs
    $(a,b) \in \grid$, this results in the desired equation.
    \item[Equation \eqref{eq:fxpt_TR_rr_b}.]
    When $n$ and $m$ are both odd, Lemma \ref{lem:flip_solution} states that
    equations \eqref{eq:fxpt_TR_rr_d} and \eqref{eq:fxpt_TR_rr_e} have one
    solution.

    When this occurs, it partitions the cells into $1$ orbit of size $1$, which
    can be filled only with a tile design that is fixed by $r^2$,
    and
    $(nm-1)/2$ orbits of size $2$, which can be specified with any tile design.
    \item[Equation \eqref{eq:fxpt_TR_rr_c}.]
    Without loss of generality, we can assume that $n$ is even and $m$ is odd,
    because the proof is essentially similar in the opposite case.
    Lemma \ref{lem:flip_solution} states
    that equation \eqref{eq:fxpt_TR_rr_d} has no solutions when $a$ is even and
    $2$ solutions when $a$ is odd;
    it also states that \eqref{eq:fxpt_TR_rr_e} has one solution.

    Thus for half of the pairs $(a,b)$, there are no fixed cells, and so there
    are $nm/2$ orbits, each of which can be specified by any tile design.

    For the other half of the pairs, there are $2$ fixed cells, which can be
    specified by any tile design that is fixed under $r^2$ and $(nm-2)/2$ orbits
    of size $2$ that can be specified by any tile design.
  \end{description}
\end{proof}

\input{Illustrations/fig_torusShiftAndRotate180.tex}

\begin{theorem}
  The sum over all cyclic shifts of the number of tilings of the $n \times m$
  torus by tile designs in $T$ that are fixed by
  $(a,f) \in \torusSymmetries$
  is given by
  \begin{subnumcases}{\fxpt^\RT_{f}(n,m) =}
      \displaystyle
      n \sum_{c \mid m} \varphi(c) \left(
        \frac12 t_{\id}^{nm/\lcm(2,c)} +
        \frac12 t_{\id}^{(n-2)m/\lcm(2,c)}t_{f^c}^{2m/c}
      \right),
      & if $n$ is even; \label{eq:fxpt_Rt_f_even}
      \\[10pt]
      \displaystyle
      n \sum_{c \mid m} \varphi(c) t_{\id}^{(n-1)m/\lcm(2,c)}t_{f^c}^{m/c},
      & if $n$ is odd. \label{eq:fxpt_Rt_f_odd}
  \end{subnumcases}
  and
  \begin{equation*}
    \fxpt^\RT_{r^2f}(n,m) = \begin{cases}
      \displaystyle
      m \sum_{d \mid n} \varphi(d) \left(
        \frac12 t_{\id}^{nm/\lcm(d,2)} +
        \frac12 t_{\id}^{n(m-2)/\lcm(d,2)}t_{(r^2f)^d}^{2n/d}
      \right),
      & \text{if $m$ is even;} \\[10pt]
      \displaystyle
      m \sum_{d \mid n} \varphi(d) t_{\id}^{n(m-1)/\lcm(d,2)}t_{(r^2f)^d}^{n/d}, & \text{if $m$ is odd.}
    \end{cases}
    \label{eq:fxpt_TR_rrf}
  \end{equation*}
  \label{thm:fxpt_Rt_f}
\end{theorem}
\begin{proof}
  Since $f$ and $r^2f$ are conjugate as elements of $D_8$, these fixed point
  formulas have essentially the same proof, so we will prove
  equations \eqref{eq:fxpt_Rt_f_even} and \eqref{eq:fxpt_Rt_f_odd} specifically.

  Since $(x,y) \cdot \ps abf = (n-1-(x+a), y+b)$, we can view
  $\ps abf$ as acting on each coordinate separately. Since
  $\ps abf^2 = ((0,2b),\id)$, we can see that the orbits
  \textit{of the first coordinate} have either size $1$ or $2$.
  Moreover, by Lemma \ref{lem:flip_solution},
  there are no  fixed cells when $n$ is even and $a$ is even,
  there are $2$ fixed cells when $n$ is even and $a$ is odd, and
  there is $1$  fixed cell when $n$ is odd.

  Since $\ps abf$ acts on the second coordinate by shifting by $b$, we see
  that Lemma \ref{lem:eulerPhi} applies. Thus for each divisor $c \mid m$,
  there are $\varphi(c)$ choices of $b$ that produce orbits
  \textit{of the second coordinate} with size $c$.

  \begin{description}
    \item[Equation \eqref{eq:fxpt_Rt_f_even}.]
    When $n$ is even, then half of the values of $a \in \Z/n\Z$ are even, and each
    orbit has size $\lcm(2,c)$ and these can be specified by any tile design.

    The other half of values of $a$ are odd, which results in $2$ fixed points for
    the first coordinate, each of which results in an orbit of size $c$
    that can be specified by any tile design that is fixed by $f^c$.
    The remaining $(n-2)m$ cells then are partitioned into orbits of size
    $\lcm(2,c)$, which can be specified by any tile design.
    \item[Equation \eqref{eq:fxpt_Rt_f_odd}.]
    When $n$ is odd, then there is one fixed point for the first coordinate,
    resulting in $m$ cells where the first coordinate is fixed under the action
    of $\ps abf$. For each divisor $c \mid m$, there is a partition of these $m$
    cells into orbits of size $c$. The resulting $m/c$ orbits
    can be specified by any tile design that fixes $f^c$.
    The remaining $n(m-1)$ cells are partitioned into orbits of size
    $\lcm(2,c)$, resulting in $n(m-1)/\lcm(2,c)$ orbits
    which can be specified by any tile design.
  \end{description}
\end{proof}
\begin{theorem}
  Then the number of distinct tilings of the $n \times m$ torus up to
  $R \subseteq D_4$ is given by
  \begin{equation}
    \frac{1}{nm|R|}\sum_{g \in R} \fxpt^\RT_g(n,m).
    \label{eq:distinctTilingsTR}
  \end{equation}
  \label{thm:nXmTorusFormula}
\end{theorem}
\begin{proof}
  We will use the convention that
  when we index over $g$, implicitly $g \in R$;
  when we index over $(a,b)$, implicitly $(a,b) \in \Z/n\Z\times\Z/m\Z$; and
  when we index over $\abg$, implicitly $\abg \in \torusSymmetries$.

  Since $\fxpt^\RT_g(n,m) = \displaystyle\sum_{(a,b)} X^{\abg}$, we can see that
  \begin{align*}
    \frac{1}{nm|R|}\sum_{g} \fxpt^\RT_g(n,m)
    &= \frac{1}{nm|R|}\sum_{g} \sum_{(a,b)} X^{\abg} \\
    &= \frac{1}{|\torusSymmetries|}\sum_{\abg} X^{\abg},
  \end{align*}
  which counts the number of distinct tilings by a direct application of
  Burnside's lemma.
\end{proof}

\subsection{The \texorpdfstring{$n \times n$}{n by n} torus}
\begin{theorem}
  The sum over all cyclic shifts of the number of tilings of the $n \times n$
  square torus (denoted \ST) by tile designs in $T$ that are fixed by
  $\abg \in \torusSymmetries$ is given by \(\fxpt^\ST_g(n)\) where
  \begin{align}
    \fxpt^\ST_{\id}(n)    &= \sum_{d_1|n}\sum_{d_2|n}\varphi(d_1)\varphi(d_2)t_{\id}^{n^2/\lcm(d_1,d_2)},
    \\
    \fxpt^\ST_{r^2}(n)  &= \begin{cases}
      n^2t_{\id}^{(n^2-1)/2}t_{r^2}, & \text{if $n$ is odd;} \\
    \displaystyle
    n^2\!\left(
      \frac34 t_{\id}^{n^2/2} +
      \frac14 t_{\id}^{n^2/2-2}t_{r^2}^4
    \right), & \text{if $n$ is even.}
    \end{cases}
    \\
    \fxpt^\ST_{f}(n)    &= \begin{cases}
      \displaystyle
      n \sum_{d \mid n} \varphi(d) \left(
        \frac12 t_{\id}^{n^2/\lcm(2,d)} +
        \frac12 t_{\id}^{(n^2-2n)/\lcm(2,d)}t_{f^d}^{2n/d}
      \right), & \text{if $n$ is even;} \\[10pt]
      \displaystyle
      n \sum_{d \mid n} \varphi(d) t_{\id}^{(n^2-n)/\lcm(2,d)}t_{f^d}^{n/d}, & \text{if $n$ is odd.}
    \end{cases}
    \\
    \fxpt^\ST_{r^2f}(n) &= \begin{cases}
      \displaystyle
      n \sum_{d \mid n} \varphi(d) \left(
        \frac12 t_{\id}^{n^2/\lcm(2,d)} +
        \frac12 t_{\id}^{(n^2-2n)/\lcm(2,d)}t_{(r^2f)^d}^{2n/d}
      \right), & \text{if $n$ is even;} \\[10pt]
      \displaystyle
      n \sum_{d \mid n} \varphi(d) t_{\id}^{(n^2-n)/\lcm(2,d)}t_{(r^2f)^d}^{n/d}  & \text{if $n$ is odd.}
    \end{cases}
  \end{align}
\end{theorem}
\begin{proof}
  These equations follow directly from Theorems \ref{thm:fxpt_Rt_id},
  \ref{thm:fxpt_Rt_rr} and \ref{thm:fxpt_Rt_f} by specifying $m = n$.
\end{proof}
\begin{theorem}
  The sum over all cyclic shifts of the number of tilings of the $n \times n$
  torus by tile designs in $T$ that are fixed by
  $(a,r) \in \torusSymmetries$
  is given by
  \begin{subnumcases}{\fxpt^\ST_{r}(n) = \fxpt^\ST_{r^3}(n) =}
    n^2 t_{\id}^{(n^2-1)/4}t_r,
    & if $n$ is odd; \label{eq:fxpt_St_r_odd}
    \\
    \displaystyle
    n^2\!\left(
      \frac12 t_{\id}^{n^2/4} +
      \frac12 t_{\id}^{(n^2-4)/4}t_r^2t_{r^2}
    \right),
    & if $n$ is even. \label{eq:fxpt_St_r_even}
  \end{subnumcases}
\end{theorem}
\begin{proof}
  First, note that the first equality comes from the fact that tilings that are
  stable under $g$ are stable under $g^{-1}$.

  Next, note that $\ps abr$ is an element of order $4$, which follows from
  observing that $\ps abr = ((a',b'),r^2)$ together with
  equation \eqref{eq:abrr_order_2}.
  Therefore cells appear in orbits of size $1$, $2$, or $4$ under $\ps abr$,
  and we will count how many cells appear in each.

  We begin by counting cells $(x,y)$ that are fixed by $\ps abr$, that is
  they satisfy the system of equations
  \begin{alignat}{2}
    x &\equiv -y - b - 1 &\pmod n \label{eq:fxpt1} \\
    y &\equiv x + a      &\pmod n \label{eq:fxpt2},
  \end{alignat}
  where we can substitute $y$ with $x+a$ in the first equation to get
  \begin{equation}
    x \equiv -x - a - b - 1 \pmod n.
    \label{eq:fxpt3}
  \end{equation}

  Next we count cells $(x,y)$ that are fixed by $\ps abr^2$, but are not
  solutions to the above system of equations. These cells satisfy the system of
  equations \begin{alignat}{2}
    x &\equiv -1 - x - a - b &\pmod n \label{eq:twoCycle1} \\
    y &\equiv -1 - y - b + a &\pmod n \label{eq:twoCycle2}.
  \end{alignat}
  \begin{description}
    \item[Equation \eqref{eq:fxpt_St_r_odd}.]
    When $n$ is odd, we can solve equation \eqref{eq:fxpt3} using
    Lemma \ref{lem:flip_solution}.
    We can see that this has one solution when $n$ is odd,
    so in this case there is one fixed cell, which can be
    specified by any tile design that is stable under $r$.

    We can add equations \eqref{eq:twoCycle1} and \eqref{eq:twoCycle2} and use
    Lemma \ref{lem:flip_solution} to see that this system has a single solution
    when $n$ is odd. However, this is identically the solution that specifies
    the fixed point, so this does not describe an orbit of size $2$.

    Thus there are $n^2 - 1$ cells that are partitioned into $(n^2-1)/4$ orbits
    of size $4$, which can be specified by any tile design.

    \item[Equation \eqref{eq:fxpt_St_r_even}] When $n$ is even, we can see again
    by Lemma \ref{lem:flip_solution}, that there are two fixed cells when
    $a + b$ is odd and none when $a + b$ is even.

    When we check the number of orbits of size $2$, Lemma
    \ref{lem:flip_solution} shows that we have $4$ solutions when $a + b$ is odd
    and none when $a + b$ is even, $2$ of which were the fixed cells, resulting
    in a single orbit of size $2$.

    Therefore, we can specify a fixed tiling by
    specifying tile designs that are fixed under $r$ for each of the two fixed cells,
    specifying a tile design that is fixed under $r^2$ for the orbit of size $2$, and
    specifying any tile designs for each of the $(n^2 - 4)/4$ orbits of length $4$.
  \end{description}
\end{proof}

\begin{theorem}
  \begin{subnumcases}{\fxpt^\ST_{rf}(n) = n\sum_{d \mid n}}
    \varphi(d) t_{\id}^{(n^2-n)/(2d)}t_{rf}^{n/d},
    & if $d$ is odd; \label{eq:fxpt_St_rf_odd}
    \\
    \varphi(d) t_{\id}^{n^2/(2d)},
    & if $d$ is even. \label{eq:fxpt_St_rf_even}
  \end{subnumcases}
  and
  \begin{align}
    \fxpt^\ST_{r^3f}(n)   &= n\sum_{d \mid n}\begin{cases}
      \varphi(d) t_{\id}^{(n^2-n)/(2d)}t_{r^3f}^{n/d}, & \text{if $d$ is odd;} \\
      \varphi(d) t_{\id}^{n^2/(2d)},                   & \text{if $d$ is even.}
    \end{cases}
  \end{align}
\end{theorem}
\begin{proof}
  These situations are essentially the same because $rf$ and $r^3f$ are
  conjugate in $D_8$, so we prove the case for $\fxpt^\ST_{rf}(n)$.

  We can see that \begin{align*}
    (x,y) &\cdot \ps ab{rf}^{2k}   = (x+k(a+b), y+k(a+b)) \\
    (x,y) &\cdot \ps ab{rf}^{2k+1} = (y+k(a+b)+b, x+k(a+b)+a)
  \end{align*} and we can ask: what is the least $k$ such that either
  \begin{align}
    x &\equiv x + k(a+b) \pmod n \label{syseq:fxpt_St_rf_even_1}
    \\
    y &\equiv y + k(a+b) \pmod n \label{syseq:fxpt_St_rf_even_2}
  \end{align} or
  \begin{align}
    x &\equiv y + k(a+b) + b \pmod n \label{syseq:fxpt_St_rf_odd_1}
    \\
    y &\equiv x + k(a+b) + a \pmod n. \label{syseq:fxpt_St_rf_odd_2}
  \end{align}
  In the first case, we want to know when $k(a+b) \equiv 0 \pmod n$, which
  occurs first when $k = n/\gcd(a+b,n)$. We call this $d$ and note that
  $d \mid n$.
  In the second case, we can add equations \eqref{syseq:fxpt_St_rf_odd_1} and
  \eqref{syseq:fxpt_St_rf_odd_2} to get \begin{equation}
    (2k + 1)(a + b) = 0 \pmod n,
  \end{equation} which occurs when $2k+1 = n/\gcd(a+b,n)$.
  Again, this is a divisor of $n$, so we say $2k+1 = d$
  and note that this solution occurs only when $d$ is odd.

  \begin{description}
    \item[Equation \eqref{eq:fxpt_St_rf_odd}] Thus, when $d$ is odd,
    we have the system of equations \begin{align*}
      x &\equiv y + \frac{d-1}{2}(a+b) + b \pmod n \\
      y &\equiv x + \frac{d-1}{2}(a+b) + a \pmod n,
    \end{align*} which has $n$ solutions:
    for each choice of $x$, there is a unique choice of $y$ that satisfies both
    equations.
    Each of these solutions correspond to a cell in one of the $n/d$ orbits
    of length $d$, each of which can be specified by any tile design
    that is stabilized by $(rf)^d = rf$, since $d$ is odd.

    The other $n^2 - n$ cells occur in one of the $(n^2-n)/(2d)$ orbits of length
    $2d$ that are solutions to the first system of equations. Each of these
    orbits can be specified by any tile design at all.

    The $\varphi(d)$ comes from the fact that for any choice of $a$ there are
    precisely $\varphi(d)$ choices for $b$ such that $n/\gcd(a+b,n) = d$.
    \item[Equation \eqref{eq:fxpt_St_rf_even}] When $d$ is even, there are no
    choices of $(x,y)$ that simultaneously satisfy equations
    \eqref{syseq:fxpt_St_rf_odd_1} and \eqref{syseq:fxpt_St_rf_odd_2},
    so all $n^2$ of the tiles $(x,y)$ occur in orbits of size $2d$.
    Each of these $n^2/(2d)$ orbits can be specified by any tile design.
  \end{description}
\end{proof}

\begin{theorem}
  The number of distinct tilings of the $n \times n$ torus up to
  $R \leq D_8$ is given by
  \begin{equation}
    \frac{1}{n^2|R|}\sum_{g \in R} \fxpt^\ST_g(n).
  \end{equation}
  \label{thm:nXnTorusFormula}
\end{theorem}
\begin{proof}
  The proof of this theorem is essentially identical to the proof of
  Theorem \ref{thm:nXmTorusFormula}, which follows by definition together with
  Burnside's lemma.
\end{proof}

Thus for any arbitrary $R \subseteq D_8$ and set of tile designs, we have
a formula to count the number of tilings of the $n \times n$ torus up to $R$.
A formula for each choice of $R$ together with each $R$-set generated by a
single tile design can be found in Appendix \ref{apss:nXnTorusSequences};
the corresponding illustrations can be found in
Appendix \ref{apss:nXnTorusIllustrations}.

\section{Next steps}
In this section, we propose several different settings for studying similar
kinds of problems. Many of these may be subtle research problems,
many may be good undergraduate research problems, and many may be good homework
problems for a combinatorics class.
Many of them would make for interesting additions to the On-Line Encyclopedia
of Integer Sequences.
\subsection{Rectangular tori under \texorpdfstring{$90^\circ$}{90 degree} rotation}
We have used the $n \times m$ torus as a model for a repeating tiling of the
plane. However, in the case that $n \neq m$, we have only analyzed the case
where we count tilings up to $D_4$, the dihedral group of the rectangle.
However, for a given tile set, it is possible that a tiling of a
$n \times m$ and a tiling of a $m \times n$ torus describe the same
tiling of the plane; an example of this is given in Figure
\ref{fig:rectangularTorusRotation}.

\begin{conjecture}
  If a plane tiling described by an $n \times m$ torus is fixed under
  $\ps abr$,
  $\ps ab{r^3}$,
  $\ps ab{rf}$, or
  $\ps ab{r^3f}$,
  then it is equivalent to the tiling of a
  $\gcd(n,m) \times \gcd(n,m)$ torus.
\end{conjecture}

Similarly, it might be interesting to count \textit{irreducible} plane tilings:
tilings of the plane corresponding to a tiling of the $n \times m$ torus
that do not correspond to a smaller torus.

\input{Illustrations/fig_rectangularTorusRotation.tex}
\subsection{Other regions of the square grid.}
We also are interested in counting the number of ways of tiling shapes like
Aztec diamonds or centered square numbers, as shown in
Figure \ref{fig:centeredSquare}.

\input{Illustrations/fig_centeredSquare.tex}

\subsection{The M\"obius strip and Klein bottle}
Since we have looked at the orientable identifications of the grid, we are also
interested in the non-orientable identifications. The M\"obius strip has a
universal cover that is $[0,1] \times \R$, and the Klein bottle has a universal
cover of $\R \times \R$, so we can visualize them analogously to how we
visualized the cylinder and torus respectively.
An illustration of a tiling of the M\"obius strip in Figure \ref{fig:mobiusStrip}.
An illustration of a tiling of the Klein bottle in Figure \ref{fig:kleinBottle}.

We are also interested in counting tilings of the real projective plane, but
because the universal cover is not the Euclidean plane, it cannot be
illustrated in the same manner as the Klein bottle and the torus.

\input{Illustrations/fig_mobiusStrip.tex}
\input{Illustrations/fig_kleinBottle.tex}

\subsection{Tilings of the triangular and hexagonal grids}
While this paper explored tilings of the square grid and related settings,
it is equally natural to ask about tilings of the triangular grid and hexagonal
grid.
In particular, it would be interesting to explore the number of tilings of
(1) triangular regions of the triangular grid,
(2) hexagonal regions of the triangular grid,
(3) triangular regions of the hexagonal grid, or
(4) hexagonal regions of the hexagonal grid,
all of which are illustrated in Figure \ref{fig:hexagonTriangle}.

Hexagonal tile designs have appeared in several tile-based edge-matching games such as
Palago, Tantrix, Psyche-Paths, and Kaliko, which
Van Ness has coined as ``serpentiles'' \cite{VanNess}. Triangular,
hexagonal, and other polygonal tiles have been described by authors such as
Ahmed \cite{Ahmed}, Mitchell \cite{Mitchell}, Beveridge \cite{Beveridge}, Walter \cite{Walter}, Bosch \cite{Bosch}, Browne \cite{Browne2009}, and Lord and Ranganathan \cite{Lord}.

In the cases of tiling hexagons and triangles in the triangular grid, each can
be extended to a tiling of the plane, as described in
Figure \ref{fig:triangleHexagonTiling}.

\input{Illustrations/fig_hexagonTriangle.tex}

\input{Illustrations/fig_triangleHexagonTiling.tex}

\subsection{Other tilings of the Euclidean plane}
Extending this idea even further, we might be interested in ways of placing
multiple shapes of tiles on various tilings of the Euclidean plane by convex
polygons, such as the
truncated trihexagonal tiling,
the snub square tiling, or the
triakis triangular tiling.

Figure \ref{fig:truncatedSquareTiling} shows an example of such a setup on a
region of the truncated square grid.
Ahmed \cite{Ahmed} and Mitchell \cite{Mitchell} gave examples of tilings on the
truncated square grid and other Archimedean tilings of the Euclidean plane.
as well as
\input{Illustrations/fig_truncatedSquareTiling.tex}
\subsection{Polyhedra}
We are also interested in settings related to polyhedra.
For instance, one could use various tile designs to count the number of distinct
tilings of a $2 \times 2 \times 2$ Rubik's cube-like object, as illustrated in
Figure \ref{fig:TruchetCube}.

Similarly, one could do this analysis on other polyhedra.
In 1997, Colour of Strategy released a puzzle called ``Tantrix Rock,'' which
featured square and hexagonal tiles placed on the vertices of a truncated
octahedron \cite{Tantrix}.
Similar counting problems could be done on the other Platonic solids and
Archimedean solids in addition to Johnson solids, prisms, antiprisms, and
polyhedra whose faces are not regular polygons, such as the
rhombic dodecahedron.

\input{Illustrations/fig_TruchetCube.tex}

\subsection{Hyperbolic plane}
In addition to the settings with no curvature (the plane)
and positive curvature (polyhedra)
it is also interesting to look at this in the negative curvature setting of the
hyperbolic plane,
as described by Dunham \cite{Dunham}.
An example of this is illustrated in Figure \ref{fig:hyperbolicTiling}.

\input{Illustrations/fig_hyperbolicTiling.tex}

\subsection{Higher dimensional objects}
We are also interested in computing higher-dimensional analogs, such as where
the tile designs are space-filling polyhedra. In the context of cubes, these
have been considered by Schattschneider \cite{Schattschneider}, Lord and Ranganathan \cite{Lord}, Browne \cite{Browne2008}

\subsection{Permuting tile colors}
In some illustrations, one may observe that two tilings are equivalent up to
swapping the colors of the tiles, as illustrated in
Figure \ref{fig:PermuteColors}. In Appendix \ref{apss:nXnTorusIllustrations},
you may notice that for each
tiling in Figures \ref{fig:nXnTorus_r_f__rf} and
\ref{fig:nXnTorus_r_f__id}, swapping the colors of the tiling is equivalent to
a $180^\circ$ rotation, a property that we would like to understand better.

\input{Illustrations/fig_PermuteColors.tex}

\section{Acknowledgments}
The authors would like to especially thank Ben Jeffers, Lani Canadilla,
Christopher Havens, and all of the other volunteers at the Prison Mathematics
Project for facilitating our conversation.
Thank you also to Scott Reskey for your close reading.

Thank you to Shane Delmore; if you hadn't shown me the Commodore 64 program,
\verb|10 PRINT CHR\$(205.5+RND(1));: GOTO 10|, this paper likely would not
exist.

Lastly, thank you to the reviewers. Your suggestions strengthened the paper
tremendously, and without them we would have missed the connection to M. C.
Escher's work, which makes this story even more compelling to us.

\appendix
\appendixpagenumbering
\section{Sequences}
\label{apn:sequencesAndTables}
This section of the appendix gives examples of all of the different sequences
and tables of
integers that count tilings of the $n\times m$ grid, cylinder, and torus
for all valid choices of $R \leq D_8$ and all sets of tile designs
consisting of a single orbit.
\subsection{The \texorpdfstring{$n \times m$}{n by m} grid}
\input{Subsections/Tables/nXmGrid.tex}

\subsection{The \texorpdfstring{$n \times n$}{n by n} grid}
\input{Subsections/Tables/nXnGrid.tex}

\subsection{The \texorpdfstring{$n \times m$}{n by m} cylinder}
\input{Subsections/Tables/nXmCyl.tex}

\subsection{The \texorpdfstring{$n \times m$}{n by m} torus}
\input{Subsections/Tables/nXmTorus.tex}

\subsection{The \texorpdfstring{$n \times n$}{n by n} torus}
\label{apss:nXnTorusSequences}
\input{Subsections/Tables/nXnTorus.tex}

\appendixpagenumbering
\section{Illustrations}
This section of the appendix gives illustrations corresponding to all of the
sequences and tables described in Appendix \ref{apn:sequencesAndTables}, which
shows an example of the tilings arising from
all valid choices of $R \leq D_8$ and all sets of tile designs
consisting of a single orbit.
\subsection{The \texorpdfstring{$n \times m$}{n by m} grid}
\input{Subsections/AppendixIllustrations/nXmGrid.tex}

\subsection{The \texorpdfstring{$n \times n$}{n by n} grid}
\input{Subsections/AppendixIllustrations/nXnGrid.tex}

\subsection{The \texorpdfstring{$n \times m$}{n by m} cylinder}
\input{Subsections/AppendixIllustrations/nXmCyl.tex}

\subsection{The \texorpdfstring{$n \times m$}{n by m} torus}
\input{Subsections/AppendixIllustrations/nXmTorus.tex}

\subsection{The \texorpdfstring{$n \times n$}{n by n} torus}
\label{apss:nXnTorusIllustrations}
\input{Subsections/AppendixIllustrations/nXnTorus.tex}

\begin{thebibliography}{99}

\bibitem{Ahmed}
Abdalla G.~M. Ahmed, Line-based rendering with {T}ruchet-like tiles, In {\em
  Proceedings of the Workshop on Computational Aesthetics}, pp.  41--51.
  Association for Computing Machinery, 2014.

\bibitem{Beveridge}
Colin Beveridge, Too good to be {T}ruchet, {\em Chalkdust}  (2018).

\bibitem{Borlenghi}
Edward Borlenghi, The curse of {T}ruchet's tiles, 2014.
\newblock Available at
  \url{https://arearugscarpet.blogspot.com/2014/04/the-curse-of-truchets-tiles.html}.

\bibitem{Bosch}
Robert Bosch and Urchin Colley, Figurative mosaics from flexible {T}ruchet
  tiles, {\em J. Math. Arts} {\bf 7} (2013), 122--135.

\bibitem{Browne2009}
Cameron Browne, Duotone {T}ruchet-like tilings, {\em J. Math. Arts} {\bf 2}
  (2008), 189--196.

\bibitem{Browne2008}
Cameron Browne, {T}ruchet curves and surfaces, {\em Comput. Graph.} {\bf 32}
  (2008), 268--281.

\bibitem{Carlson}
Christopher Carlson, Multi-scale {T}ruchet patterns, In {\em Bridges 2018
  Conference Proceedings}, pp.  39--44, 2018.

\bibitem{Davis}
Dan Davis, On a tiling scheme from {M}. {C}. {E}scher, {\em Electron. J.
  Combin.} {\bf 4} (1996), \#R23.

\bibitem{Douat}
Dominique Douat, {\em {Methode pour faire une Infinité de Desseins Differens,
  avec des carreaux mi-partis de deux couleurs par une ligne diagonale}},
  Florentin de Laulne, 1722.

\bibitem{Dunham}
Douglas Dunham, Hyperbolic {T}ruchet tilings, In {\em Proceedings of Bridges
  2011: Mathematics, Music, Art, Architecture, Culture}, pp.  311--318.
  Tessellations Publishing, 2011.

\bibitem{Ethier}
S.~N. Ethier, Counting toroidal binary arrays, {\em J. Integer Sequences} {\bf 16}
  (2013),
  \href{https://cs.uwaterloo.ca/journals/JIS/VOL16/Ethier/ethier2.html}{Article
  13.4.7}.

\bibitem{EthierLee}
S.~N. Ethier and Jiyeon Lee, Counting toroidal binary arrays, {II}, {\em J.
  Integer Seq.} {\bf 18} (2015),
  \href{https://cs.uwaterloo.ca/journals/JIS/VOL18/Lee/lee6.html}{Article
  15.8.3}.

\bibitem{Fonseca}
Tiago Fonseca and Paul Zinn-Justin, On some ground state components of the
  ${O}(1)$ loop model, {\em J. Stat. Mech.}  (2009), P03025.

\bibitem{Hall}
Andreia Hall, Paulo Almeida, and Ricardo Teixeira, Exploring symmetry in
  rosettes of {T}ruchet tiles, {\em J. Math. Arts} {\bf 13} (2019), 308--335.

\bibitem{Hooper}
W.~Patrick Hooper, {T}ruchet tilings and renormalization, arxiv preprint
  ar{X}iv:1103.6046 [math.DS], 2012.
\newblock Available at \url{https://arxiv.org/abs/1103.6046}.

\bibitem{Irvine}
Veronika Irvine, {\em Lace tessellations: a mathematical model for bobbin lace
  and an exhaustive combinatorial search for patterns}, PhD thesis, University
  of Victoria, 2016.

\bibitem{Knoll}
Eva Knoll, Karyn McLellan, and Danielle Cox, The rhizomic tiles at {S}hooter's
  {H}ill: an application of {T}ruchet tiles, {\em J. Math. Arts}  (2024),
  1--22.

\bibitem{Krawczyk}
Robert~J. Krawczyk, {T}ruchet tilings revisited, In {\em Proceedings of ISAMA
  2011}, pp.  69--77. International Society of the Arts, Mathematics, and
  Architecture, 2012.

\bibitem{Lord}
Eric Lord and Srinivasa Ranganathan, {T}ruchet tilings and their
  generalisations, {\em Resonance} {\bf 11} (2006), 42--50.

\bibitem{MacMahon}
P.~A. MacMahon, Applications of a theory of permutations in circular procession
  to the theory of numbers, {\em Proc. Lond. Math. Soc.} {\bf 23} (1891),
  305--318.

\bibitem{Mitchell}
Kerry Mitchell, Generalizations of {T}ruchet tiles, In {\em Proceedings of
  Bridges 2020: Mathematics, Art, Music, Architecture, Education, Culture}, pp.
   191--198, 2020.

\bibitem{Montfort}
Nick Montfort, Patsy Baudoin, John Bell, Ian Bogost, and Jeremy Douglass, {\em
  {10 PRINT CHR\$(205.5+RND(1));: GOTO 10.}}, Software Studies, The MIT Press,
  2013.

\bibitem{Nahum}
Adam Nahum, P.~Serna, A.~M. Somoza, and M.~Ortu\~no, Loop models with
  crossings, {\em Phys. Rev. B} {\bf 87} (2013), 184204.

\bibitem{OEIS}
OEIS~Foundation Inc., The On-Line Encyclopedia of Integer Sequences, 2024.
\newblock Available at \url{https://oeis.org/}.

\bibitem{Schattschneider1990}
Doris Schattschneider, {\em {Visions of Symmetry}}, W. H. Freeman, 1990.

\bibitem{Schattschneider}
Doris Schattschneider, {E}scher's combinatorial patterns, {\em Electron. J.
  Combin.} {\bf 4} (1996), \#R17.

\bibitem{Smith}
Cyril~Stanley Smith and Pauline Boucher, The tiling patterns of {S}ebastien
  {T}ruchet and the topology of structural hierarchy, {\em Leonardo} {\bf 20}
  (1987), 373--385.

\bibitem{Tantrix}
Tantrix, The story so far, 2021.
\newblock Available at
  \url{https://www.tantrix.com/english/TantrixHistory.html}.

\bibitem{Truchet}
S\'ebastien Truchet, M\'emoire sur les combinaisons, {\em Mem. Acad. r. Sci.}
  (1704), 363--372.

\bibitem{VanNess}
Kurt~N. Van~Ness, Serpentiles, 2008.
\newblock Available at
  \url{http://www.van-ness.com/Kurt/Serpentiles/Serpentiles.htm}.

\bibitem{Walter}
Natalie Walter, Heather Ligler, and Benay G\"{u}rsoy, The {T}ruchet tile
  grammar: A generative system for versatile tile and pattern design, {\em
  Nexus Netw. J.}  (2024).

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification}:
Primary 05A05; Secondary 00A66, 00A08.

\noindent \emph{Keywords: } Truchet tile, Burnside's lemma, chessboard tiling, combinatorics.

\bigskip
\hrule
\bigskip

\begin{sloppypar}
\noindent
(Concerned with sequences
\seqnum{A047937},
\seqnum{A054247},
\seqnum{A086675},
\seqnum{A103488},
\seqnum{A179043},
\seqnum{A184271},
\seqnum{A184277},
\seqnum{A184284},
\seqnum{A200564},
\seqnum{A222187},
\seqnum{A222188},
\seqnum{A225910},
\seqnum{A255015},
\seqnum{A255016},
\seqnum{A295223},
\seqnum{A295229},
\seqnum{A302484},
\seqnum{A343095},
\seqnum{A343096},
%
\seqnum{A367522},
\seqnum{A367523},
\seqnum{A367524},
\seqnum{A367525},
\seqnum{A367526},
\seqnum{A367527},
\seqnum{A367528},
\seqnum{A367529},
\seqnum{A367530},
\seqnum{A367531},
\seqnum{A367532},
\seqnum{A367533},
\seqnum{A367534},
\seqnum{A367535},
\seqnum{A367536},
\seqnum{A367537},
\seqnum{A367538},
%
\seqnum{A368137},
\seqnum{A368138},
\seqnum{A368139},
\seqnum{A368140},
\seqnum{A368141},
\seqnum{A368142},
\seqnum{A368143},
\seqnum{A368144},
\seqnum{A368145},
%
\seqnum{A368218},
\seqnum{A368219},
\seqnum{A368220},
\seqnum{A368221},
\seqnum{A368222},
\seqnum{A368223},
\seqnum{A368224},
%
\seqnum{A368253},
\seqnum{A368254},
\seqnum{A368255},
\seqnum{A368256},
\seqnum{A368257},
\seqnum{A368258},
\seqnum{A368259},
\seqnum{A368260},
\seqnum{A368261},
\seqnum{A368262},
\seqnum{A368263},
\seqnum{A368264},
%
\seqnum{A368302},
\seqnum{A368303},
\seqnum{A368304},
\seqnum{A368305},
\seqnum{A368306},
\seqnum{A368307}, and
\seqnum{A368308}.)
\end{sloppypar}

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received January 2 2024;
revised versions received January 3 2024; May 15 2024; May 21 2024; June 5 2024; June 6 2024; June 8 2024; June 12 2024.
Published in {\it Journal of Integer Sequences}, June 13 2024.

\bigskip
\hrule
\bigskip

\noindent
Return to
\href{https://cs.uwaterloo.ca/journals/JIS/}{Journal of Integer Sequences home page}.
\vskip .1in

\end{document}
