\documentclass[12pt,reqno]{article}

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

\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{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\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{\rb}{rb}
\DeclareMathOperator{\rs}{rs}
\DeclareMathOperator{\cb}{cb}
\DeclareMathOperator{\cs}{cs}
\DeclareMathOperator{\cf}{cf}
\DeclareMathOperator{\cl}{cl}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{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}


\begin{center}
\vskip 1cm{\LARGE\bf 
Colorful Tilings and Permutations}
\vskip 1cm
\large
Jonathan Beagley and Lara Pudwell \\
Department of Mathematics and Statistics\\
Valparaiso University\\
Valparaiso, IN 46383\\
USA \\
\href{mailto:jon.beagley@valpo.edu}{\tt jon.beagley@valpo.edu} \\
\href{mailto:lara.pudwell@valpo.edu}{\tt lara.pudwell@valpo.edu}
\end{center}

\vskip .2 in

\begin{abstract}
We study tilings of rectangular and circular arrays with specified sets of colored rectangular tiles.  In particular, we consider rectangular tiles of arbitrarily large size, but where the number of colors available to use on a particular tile is determined by its position on the array.  While tiling enumeration is often used to prove identities involving Fibonacci and Lucas numbers, the tilings we examine yield natural connections with sets of permutations.
\end{abstract}

\section{Introduction}

We consider tilings of rectangular and circular arrays with colored tiles. It is well known that the number of ways to tile an $n \times 1$ rectangle with dominoes and squares is given by the $n$th Fibonacci number, and the number of ways to tile an $n$-cell circular array with dominoes and squares is given by the $n$th Lucas number.  These types of tilings have been generalized in a number of ways, and an excellent survey of enumerative and bijective results resulting from tilings is given by Benjamin and Quinn \cite{BQ03}.  

A recent paper of Dresden and Xiao \cite{DXTBA} considers tilings of $n \times 1$ rectangles and $n$-cell circular arrays with tiles of any size $i \times 1$, where $1 \leq i \leq n$ and where $i \times 1$ tiles come in $i$ different colors.  They use these colored tilings to prove identities involving weighted sums of Fibonacci numbers.  In any Fibonacci or Lucas-type tiling, a tile is uniquely described by its size and position.  While Dresden and Xiao determined the number of colors of a tile by the size, in this paper we ask the analogous enumeration questions when the number of colors available to a tile is determined by its position.  In particular, we number the cells of an $n \times 1$ rectangle consecutively from left to right, and we number the cells of an $n$-cell circular array consecutively in a clockwise fashion as shown in Figure \ref{fig:boards}. We consider a family of six enumeration questions, determined by the following parameters:

\begin{figure}
    \centering
\raisebox{0.5in}{\begin{tikzpicture}
\draw[gray, dashed] (1,0)--(1,1);
\draw[gray, dashed] (2,0)--(2,1);
\draw[gray, dashed] (4,0)--(4,1);
\node at (0.5,0.5) {1};
\node at (1.5,0.5) {2};
\node at (3,0.5) {\dots};
\node at (4.5,0.5) {$n$};
\draw[thick] (0,0)--(5,0)--(5,1)--(0,1)--(0,0);
\end{tikzpicture}} \hspace{0.1in}
\begin{tikzpicture}
\draw[gray, dashed] (0,1)--(0,1.75);
\draw[gray, dashed] (0.5,0.866)--(0.875,1.515);
\draw[gray, dashed] (-0.5,0.866)--(-0.875,1.515);
\draw[gray, dashed] (0.866,0.5)--(1.515,0.875);
\node at (0.355,1.328) {1};
\node at (0.972,0.972) {2};
\node at (0,-1.375) {\dots};
\node at (-0.355,1.328) {$n$};
\draw[thick](0,0) circle (1.75);
\draw[thick](0,0) circle (1);
\end{tikzpicture}
    \caption{An $n$-cell rectangular board and an $n$-cell circular array.}
    \label{fig:boards}
\end{figure}

\begin{itemize}
    \item What board is to be tiled? ($n \times 1$ rectangle or $n$-cell circular array)
    \item What is the number of possible colors of a tile? (determined by the biggest cell that is covered, the smallest cell that is covered, the last value cell that is covered, or the first value cell that is covered)
\end{itemize}

In a circular array, the first and last valued cells are determined by reading the cells in clockwise order.  In a rectangle tiling, ``first'' and ``smallest'' are equivalent, as are ``last'' and ``biggest''.  The same is true for many tiles on a circular array; however, in a circular array, tiles of size 2 or more may cover both cell $n$ and cell 1 simultaneously, and these conventions differ for these ``straddling tiles''.  

We explore each of these questions in turn and analyze the resulting enumeration sequences.  In particular, rather than having connections to Fibonacci and Lucas numbers, this new family of tilings results in connections with various families of permutations. Throughout this paper, we think of permutations combinatorially, rather than algebraically.  That is, a permutation $\pi$ of size $n$ is a list of the numbers $1,2,\dots, n$ where order matters.  In particular, it will be useful to think about the inversions of the permutations in question.  An \emph{inversion} in a permutation $\pi=\pi_1\cdots \pi_n$ is a pair of entries $\pi_i$ and $\pi_j$ such that $i<j$ but $\pi_i>\pi_j$.

In Section \ref{S:rectangles} we consider tilings of an $n\times 1$ rectangle according to two different conventions for the number of colors available to each tile, and in Section \ref{S:circular arrays} we consider tilings of an $n$-cell circular array according to four different conventions for the number of colors available to each tile.  For each tiling problem, we give both an enumeration of the possible tilings and a bijective connection with a specific family of permutations.

\section{Rectangle tilings} \label{S:rectangles}

Let $r_n$ be the number of tilings of an $n \times 1$ rectangular board with $i \times 1$ tiles where $1 \leq i \leq n$.  Clearly $r_0 = r_1 = 1$.  In general, we can divide the tilings into cases by conditioning on the size of the last tile.  If the last tile is of size $i$, then the rest of the board is an $(n-i) \times 1$ board with the same tiling rules, so we have $$r_n = \sum_{i=1}^n r_{n-i}.$$  This recurrence yields $r_n=2^{n-1}$; this is sequence
\seqnum{A000079} in the {\it On-Line Encyclopedia of Integer Sequences} (OEIS).  We can see this result more directly, since any tiling of an $n \times 1$ rectangle corresponds to a composition of $n$, i.e., an ordered list of positive integers whose sum is $n$.  We really must decide whether each of the $n-1$ boundaries between cells is a boundary between two distinct tiles or not, yielding $2^{n-1}$ possible uncolored tilings.

Now that we understand the monochromatic tiling case, we consider colored tilings where each tile is assigned a color and the number of colors available to a tile is determined by the tile's position.
\begin{theorem}\label{T:big_rectangles}
Let $\rb_n$ be the number of tilings of an $n \times 1$ rectangle where the number of possible colors of a tile $t$ is determined by the biggest cell $t$ covers.  Then for $n \geq 1$ we have
$$\rb_n=n \cdot n!. \text{ \rm (OEIS \seqnum{A094258})}$$
\end{theorem}

\begin{proof}
Notice that for $n \geq 1$, $n \cdot n!$ is the number of permutations of $[n+1]=\{1,\dots, n+1\}$ whose final digit is not $n+1$. 

Now consider a tiling of an $n \times 1$ rectangle where the number of colors available to a tile is determined by the largest cell it covers and name the tiles $t_1, t_2, \ldots, t_m$ from left to right.  Given tile $t_i$ of length $\ell_i$ and color $c_i$ let $\hat{f}(t_i)$ be the sequence $0^{\ell_i-1},c_i$.  Now, for any tiling $t_1t_2\cdots t_m$ of an $n \times 1$ rectangle, we may associate a sequence $s=s_1\cdots s_{n+1}$ formed by concatenating $0\hat{f}(t_1)\hat{f}(t_2)\cdots \hat{f}(t_m)$.  To find the permutation $f(t_1t_2\cdots t_m)$ that corresponds to the entire tiling, begin with the permutation $12\cdots (n+1)$.  Then, for $1 \leq i \leq n+1$, move the digit $i$ to the left $s_i$ positions.  Since $s_{n+1} \geq 1$, this generates a permutation of $[n+1]$ that does not end in $n+1$.  In the resulting permutation, $j$ is the larger digit in $s_j$ inversions.

This construction is invertible.  Consider a permutation $\pi$ of length $n+1$.  The position of $n+1$ determines the color of the last tile.  Also, after deleting the digit $n+1$, the longest run of digits where $\pi_i=i$ at the end of the permutation (possibly of length 0) is one less than the length of the last tile.  We can then delete these final digits and recursively determine the size and length of each successive tile from right to left.
\end{proof}

As an example, consider the tiling $t_1t_2t_3t_4$ in Figure \ref{fig:7board}.  We have $\hat{f}(t_1)=02$, $\hat{f}(t_2)=004$, $\hat{f}(t_3)=6$, and $\hat{f}(t_4)=5$.  Together this tells us that $s=00200465$. Reading this sequence from left to right, we begin with 12345678. Since $s_1=s_2=0$, we see that 1 and 2 are involved in 0 inversions, but since $s_3=2$, the digit 3 appears ahead of 1 and 2, and alters our permutation to 31245678.  Similarly, 4 and 5 are involved in no inversions, but $s_6=4$ tells us that 6 is involved in 4 inversions so our permutation becomes 36124578. Since $s_7=6$, we move 7 to the left by 6 positions to obtain 73612458.  Since $s_8=5$ we move 8 to the left by 5 positions to obtain $\pi=f(t_1t_2t_3t_4)=73861245$.  Similarly, the permutation $\pi=3216475$ corresponds to the tiling shown in Figure \ref{fig:6board}. In general, the colors of tiles correspond to the number of inversions involving a specified digit, so these tilings are an alternate representation of inversion sequences.  In Section \ref{S:circular arrays} we will use variations of this bijection to understand tilings of circular arrays.
\begin{figure}[hbt]
    \centering
\begin{tikzpicture}
\draw[black] (2,0)--(2,1);
\draw[gray,dashed] (1,0)--(1,1);
\draw[gray,dashed] (3,0)--(3,1);
\draw[gray,dashed] (4,0)--(4,1);
\draw[black] (5,0)--(5,1);
\draw[black] (6,0)--(6,1);
\node at (1,0.5) {2};
\node at (3.5,0.5) {4};
\node at (5.5,0.5) {6};
\node at (6.5,0.5) {5};
\draw[thick] (0,0)--(7,0)--(7,1)--(0,1)--(0,0);
\end{tikzpicture}
    \caption{A 7-cell biggest-color rectangle tiling, where each tile is labeled with its color, corresponding to 73861245.}
    \label{fig:7board}
\end{figure}


\begin{figure}[htb]
    \centering
\begin{tikzpicture}
\draw[black] (1,0)--(1,1);
\draw[black] (2,0)--(2,1);
\draw[gray,dashed] (3,0)--(3,1);
\draw[gray,dashed] (4,0)--(4,1);
\draw[black] (5,0)--(5,1);
\draw[black] (6,0)--(6,1);
\node at (0.5,0.5) {1};
\node at (1.5,0.5) {2};
\node at (3.5,0.5) {2};
\node at (5.5,0.5) {1};
\draw[thick] (0,0)--(6,0)--(6,1)--(0,1)--(0,0);
\end{tikzpicture}
    \caption{A 6-cell biggest-color rectangular board, where each tile is labeled with its color, corresponding to 3216475.}
    \label{fig:6board}
\end{figure}

Next, we consider an alternate coloring rule that is related to a different family of permutations.
\begin{theorem}\label{T:small_rectangles}
Let $\rs_n$ be the number of tilings of an $n \times 1$ rectangle where the number of possible colors of a tile $t$ is determined by the smallest cell $t$ covers.  Then 
$$\rs_n=\dfrac{(n+1)!}{2}. \text{ \rm (OEIS \seqnum{A001710})}$$
\end{theorem}

\begin{proof}
We prove this inductively.

When $n=1$, there is one tiling, as expected.

Now suppose $\rs_n=\frac{(n+1)!}{2}$ and consider a tiling of an $(n+1) \times 1$ board.  Either the last tile is a square with one of $n+1$ colors, and the rest of the tiling is a tiling of an $n \times 1$ board, or the last tile is a $k \times 1$ tile ($k>1$) with the number of colors determined by its first cell.  We can shrink this last tile to be a $(k-1) \times 1$ tile with the same color to obtain a tiling of an $n \times 1$ board.  Either way, each $n \times 1$ tiling corresponds to $n+2$ different tilings of an $(n+1) \times 1$ board; $n+1$ that end in squares, and one that results from stretching the size of the final tile.  This tells us $\rs_{n+1} = (n+2)\rs_n = \dfrac{(n+2)!}{2}$, as desired.
\end{proof}

An \emph{even} (resp.\ \emph{odd}) \emph{permutation} is a permutation with an even (resp.\ odd) number of inversions.  Among the $n!$ permutations of length $n$ (where $n \geq 2)$, exactly half of them are even.  (To see this, notice that transposing the final two digits of a permutation provides a bijection between odd permutations and even permutations of the same length.)  Although the proof of Theorem \ref{T:small_rectangles} is relatively succinct, we may also give a bijection $g(T)$ between the tilings counted by $\rs_n$ and the even permutations of length $n+1$. 

As a base case, when $n=1$, there is one tiling, and there is one even permutation of length 2, namely 12.

Now, for $n \geq 2$, we show that if there is a bijection between tilings counted by $\rs_{n-1}$ and even permutations of length $n$, then this extends to a bijection between tilings counted by $\rs_n$ and even permutations of length $n+1$.

Consider a tiling counted by $\rs_n$.  If the last tile has length 2 or greater, find the permutation that corresponds to shrinking the last tile by 1 square and append $n+1$ on the end of the permutation.  This is guaranteed to be an even permutation because there are still an even number of inversions among the digits $1,2,\dots,n$, and $n+1$ is involved in no inversions.

Otherwise, the last tile has size 1 and color $c$ where $1 \leq c \leq n$.  Consider the permutation $\pi^\prime$ that corresponds to the tiling where this final tile is removed.  $\pi^\prime$ is necessarily even.  Now, if $c$ is even, insert $n+1$ in position $n+1-c$, which involves $n+1$ in $c$ inversions and produces an even permutation.  On the other hand if $c$ is odd, then transpose the last two digits of $\pi^\prime$ to get an odd permutation of length $n$ and then insert $n+1$ in position $n+1-c$ to involve $n+1$ in an odd number of inversions and produce an even permutation.  

This procedure is invertible.  The position of the largest digit in an even permutation uniquely determines whether the last tile has length 1 or is longer.  If the last tile is square, the position of $n+1$ also determines its color.  We may delete digit $n+1$ from the permutation and recursively determine the unique tiling that goes with this new permutation of length $n$ and then either extend the last tile or add an appropriately-colored square to complete the tiling.

As an example, Table \ref{T:altrect} gives the twelve possible smallest-color tilings of a $3\times 1$ rectangle along with their corresponding even permutations of length 4.
\begin{table}
\begin{center}
\begin{tabular}{c|c||c|c}
tiling $T$&permutation $g(T)$&tiling $T$&permutation $g(T)$\\
\hline
\scalebox{0.6}{\begin{tikzpicture}
\node at (1.5,0) {1};
\draw[thick] (0,-0.5)--(3,-0.5)--(3,0.5)--(0,0.5)--(0,-0.5);
\end{tikzpicture}}
&1234&
\scalebox{0.6}{\begin{tikzpicture}
\draw[black] (1,-0.5)--(1,0.5);
\draw[black] (2,-0.5)--(2,0.5);
\node at (0.5,0) {1};
\node at (1.5,0) {1};
\node at (2.5,0) {1};
\draw[thick] (0,-0.5)--(3,-0.5)--(3,0.5)--(0,0.5)--(0,-0.5);
\end{tikzpicture}}
&2143\\

\scalebox{0.6}{\begin{tikzpicture}
\draw[black] (1,-0.5)--(1,0.5);
\node at (0.5,0) {1};
\node at (2,0) {1};
\draw[thick] (0,-0.5)--(3,-0.5)--(3,0.5)--(0,0.5)--(0,-0.5);
\end{tikzpicture}}
&2314&
\scalebox{0.6}{\begin{tikzpicture}
\draw[black] (1,-0.5)--(1,0.5);
\draw[black] (2,-0.5)--(2,0.5);
\node at (0.5,0) {1};
\node at (1.5,0) {1};
\node at (2.5,0) {2};
\draw[thick] (0,-0.5)--(3,-0.5)--(3,0.5)--(0,0.5)--(0,-0.5);
\end{tikzpicture}}
&2431\\


\scalebox{0.6}{\begin{tikzpicture}
\draw[black] (1,-0.5)--(1,0.5);
\node at (0.5,0) {1};
\node at (2,0) {2};
\draw[thick] (0,-0.5)--(3,-0.5)--(3,0.5)--(0,0.5)--(0,-0.5);
\end{tikzpicture}}
&3124&
\scalebox{0.6}{\begin{tikzpicture}
\draw[black] (1,-0.5)--(1,0.5);
\draw[black] (2,-0.5)--(2,0.5);
\node at (0.5,0) {1};
\node at (1.5,0) {1};
\node at (2.5,0) {3};
\draw[thick] (0,-0.5)--(3,-0.5)--(3,0.5)--(0,0.5)--(0,-0.5);
\end{tikzpicture}}
&4213\\

\scalebox{0.6}{\begin{tikzpicture}
\draw[black] (2,-0.5)--(2,0.5);
\node at (1,0) {1};
\node at (2.5,0) {1};
\draw[thick] (0,-0.5)--(3,-0.5)--(3,0.5)--(0,0.5)--(0,-0.5);
\end{tikzpicture}}
&1342&
\scalebox{0.6}{\begin{tikzpicture}
\draw[black] (1,-0.5)--(1,0.5);
\draw[black] (2,-0.5)--(2,0.5);
\node at (0.5,0) {1};
\node at (1.5,0) {2};
\node at (2.5,0) {1};
\draw[thick] (0,-0.5)--(3,-0.5)--(3,0.5)--(0,0.5)--(0,-0.5);
\end{tikzpicture}}
&3241\\


\scalebox{0.6}{\begin{tikzpicture}
\draw[black] (2,-0.5)--(2,0.5);
\node at (1,0) {1};
\node at (2.5,0) {2};
\draw[thick] (0,-0.5)--(3,-0.5)--(3,0.5)--(0,0.5)--(0,-0.5);
\end{tikzpicture}}
&1423&
\scalebox{0.6}{\begin{tikzpicture}
\draw[black] (1,-0.5)--(1,0.5);
\draw[black] (2,-0.5)--(2,0.5);
\node at (0.5,0) {1};
\node at (1.5,0) {2};
\node at (2.5,0) {2};
\draw[thick] (0,-0.5)--(3,-0.5)--(3,0.5)--(0,0.5)--(0,-0.5);
\end{tikzpicture}}
&3412\\

\scalebox{0.6}{\begin{tikzpicture}
\draw[black] (2,-0.5)--(2,0.5);
\node at (1,0) {1};
\node at (2.5,0) {3};
\draw[thick] (0,-0.5)--(3,-0.5)--(3,0.5)--(0,0.5)--(0,-0.5);
\end{tikzpicture}}
&4132&
\scalebox{0.6}{\begin{tikzpicture}
\draw[black] (1,-0.5)--(1,0.5);
\draw[black] (2,-0.5)--(2,0.5);
\node at (0.5,0) {1};
\node at (1.5,0) {2};
\node at (2.5,0) {3};
\draw[thick] (0,-0.5)--(3,-0.5)--(3,0.5)--(0,0.5)--(0,-0.5);
\end{tikzpicture}}
&4321\\

\end{tabular}
\end{center}
\caption{All smallest-color tilings of a $3\times 1$ rectangular board and their corresponding even permutations of length 4.}
\label{T:altrect}
\end{table}

\section{Circular array tilings}\label{S:circular arrays}

Next we consider tilings of an $n$-cell circular array.  As in the rectangular case, it is instructive to first count uncolored tilings.  Consider the tile covering $1$ to be the ``first'' tile.  This tile has size $i$ where $1 \leq i \leq n$, and there are $i$ positions this tile could have (depending on whether cell 1 is the first, second, \ldots, or $i$th cell covered by the tile).  Then there are $n-i$ remaining cells, which can be covered in $2^{n-i-1}$ ways if $i<n$ (or 1 way if $i=n$), since tiling this portion of the circle is equivalent to covering an $(n-i) \times 1$ rectangle.  Therefore, there are $n+\sum_{i=1}^{n-1} i2^{n-i-1} = 2^n-1$ (OEIS \seqnum{A000225}) ways to tile an $n$-cell circular array.  We can also see this enumeration more directly; we either choose to include or omit each of the $n$ boundaries between adjacent cells as a boundary between distinct tiles, and the only invalid choice is to select 0 such boundaries.

Now, consider the situation where the number of colors available to a tile is determined by its position.  Just as the number of uncolored tilings of a circular array is a weighted sum of tilings of rectangles, the same general idea holds when we introduce colored tiles to circular arrays.  In this section, we consider four conventions: the number of colors available to a tile is given by the first, smallest, last, or biggest cell covered.  For many tiles the first two conventions will be the same and the last two conventions will be the same, but circular arrays may have tiles that simultaneously cover both cell $n$ and cell 1, and these cells will be treated differently by the various conventions.  For example, a $4 \times 1$ tile that covers cells $n-1$, $n$, 1, and 2 has $n-1$ as its first cell, 1 as its smallest cell, 2 as its last cell, and $n$ as its biggest cell.  Similar to the enumerations in Section \ref{S:rectangles}, in this section we find sequences connected with specific families of permutations.  While two of these enumerations are equal and the resulting sequence is in the
{\it On-Line Encyclopedia of Integer Sequences} \cite{OEIS}, the other two appear to be new to the literature.

\begin{theorem}\label{T:last_circular}
Let $\cl_n$ be the number of tilings of an $n$-cell circular array where the number of possible colors of a tile $t$ is determined by the last cell $t$ covers, and let $\cf_n$ be the number of tilings of an an $n$-cell circular array where the number of possible colors of a tile $t$ is determined by the first cell $t$ covers.  Then 

$$\cl_n=\cf_n=(n+1)!-1. \text{ (OEIS \seqnum{A033312})}$$
\end{theorem}

\begin{proof}
Consider an uncolored tiling $T$ of an $n$-cell circular array whose tiles have last cells $c_1,\dots, c_m$.  Rotating this tiling counterclockwise by one position yields tiling $T^{\prime}$ whose tiles have first cells $c_1, \dots, c_m$.  Therefore the number of colorings of $T$ counted by $\cl_n$ equals the number of colorings of $T^{\prime}$ counted by $\cf_n$.


Now, we focus on $\cl_n$ and show that $\cl_n = \rb_n + \cl_{n-1}$. Consider a tiling counted by $\cl_n$.  Either the colored tile covering position $n$ also covers position 1 or not. If not, by cutting the circular array between cells 1 and $n$, we have a tiling equivalent to one of the $\rb_n$ tilings counted by Theorem \ref{T:big_rectangles}. Alternatively, if the colored tile covering position $n$ also covers position 1, then we may shrink the tile by 1 square and remove position $n$ from the circular array to obtain a colored tiling counted by $\cl_{n-1}$, provided $n > 1$.

Assuming that $\cl_n = (n+1)! - 1$, consider $\cl_{n+1} = \rb_{n+1} + \cl_{n}$. Using Theorem \ref{T:big_rectangles}, $\rb_n = n\cdot n!$ and by our inductive hypothesis we conclude that $\cl_{n+1} = (n+1)\cdot (n+1)! + (n+1)!-1 = (n+2)! -1$, as desired.
\end{proof}

While Theorem \ref{T:last_circular} enumerates the relevant circular array tilings,  we can also find a bijection between the tilings counted by $\cl_n$ and the permutations of $n+1$ that are not the identity permutation. Consider a tiling where cell $n$ and cell 1 are covered by different tiles.  Since this tiling is equivalent to a tiling counted by $\rb_n$, then via bijection $f$ in the proof of Theorem \ref{T:big_rectangles} it can be mapped to a unique permutation of length $n+1$ where $n+1$ is not last.  On the other hand, if cells $n$ and $1$ are covered by the same tile, suppose that there are $i$ cells covered by this tile to the left of 1.  Delete these $i$ cells and shrink this tile by size $i$ to obtain a tiling counted by $\cl_{n-i}$ where cells 1 and $n-i$ are covered by different tiles.  We can find the unique permutation of length $n+1-i$ corresponding to this tiling via bijection $f$ and then append the digits $n-i+2,\dots,n+1$ in order to complete the non-identity permutation of length $n+1$.


\begin{theorem}
Let $\cb_n$ be the number of tilings of an $n$-cell circular array where the number of possible colors of a tile $t$ is determined by the biggest cell $t$ covers.  Then 

$$\cb_n= n  \displaystyle\sum_{k=1}^n \frac{n!}{k!}. \text{ (OEIS \seqnum{A345887})}$$
\end{theorem}


\begin{proof}
Let $\rb^i_k$ be the number of tilings of an $k \times 1$ rectangle where the number of possible colors of a tile $t$ is determined by the biggest cell $t$ covers, starting at position $i+1$. With this notation, Theorem \ref{T:big_rectangles} addresses the case where $i = 0$.  When $i>0$, we understand positions $1,\dots, i$ to be all covered by the first tile, whose size is at least $i+1$. 

Consider a tiling counted by $\cb_n$.  Then the tile covering position $n$ covers $i$ positions to the right of $n$ where $i \geq 0$. If $i=0$, by cutting the circular array between cells $n$ and 1, we obtain one of the $\rb_n = n \cdot n!$ tilings of a rectangular array. Alternatively, if $i > 0$, we can remove the positions $1, 2, \ldots, i$ from the tiling without changing the number of tilings. There are exactly $\rb^i_{n-i}$ such tilings. These can be counted in a manner similar to Theorem \ref{T:big_rectangles}, where the ordering of $1,\ldots,i+1$ in the corresponding permutation does not matter, and thus $\rb^i_{n-i} = n \frac{n!}{(i+1)!}$. We sum over all relevant values of $i$ to determine $$\cb_n =   \displaystyle\sum_{i=0}^{n-1} \rb^i_{n-i} = \sum_{i=0}^{n-1} n \frac{n!}{(i+1)!} = n \sum_{k=1}^n \frac{n!}{k!}.$$
\end{proof}

While $\cb_n$ is new to OEIS, $\frac{\cb_n}{n}$ is given by \seqnum{A002627}, which is known to be the number of permutations of proper subsets of a set of $n$ objects. We can see this by modifying bijection $f$ from the proof of Theorem \ref{T:big_rectangles}.  Consider a tiling and focus on the tile covering cell $n$.  Suppose this tile covers $i$ cells to the right of $n$.  Necessarily, $0 \leq i \leq n-1$.  Delete cells $1,\dots, i$ from the tiling (and shrink this tile by $i$ cells) to obtain a tiling of cells $i+1,\dots,n$ of the circular array.  Now, to generate a (partial) permutation, begin with $i+1$ blanks, and then proceed similarly to bijection $f$, reading tiles from left to right.  When a tile has color $c$ and covers cells $j,\dots,  j+a$, append the digits $j-i,\dots, j+a-i-1$ to the end of the partial permutation, and then place digit $j+a-i$ in the $(c+1)$st position from the end.  This produces a permutation consisting of $i+1$ blanks along with the digits $1,\dots,  n-i$.  Since there are always $n$ choices for the color of the last tile, there are always $n$ possible positions of the digit $n+1$ relative to the other digits in any underlying partial permutation.  If digit $n+1$ is removed, then we produce all ways to generate a permutation of $i+1$ blanks and $n-i-1$ digits.  Now, if there is a digit in position $p$, consider $p$ to be in our chosen subset, and if there is a blank in position $p$, $p$ is not in the subset.  The digits $1,\dots,n-i$ in the non-blank positions produce a permutation of our chosen elements.  Since there is always at least one blank, we always have a proper (possibly empty) subset of $\{1,\dots,n\}$ that has been chosen.

As an example, consider the coloring of a 6-cell circular array shown in the left of Figure \ref{fig:circle}.  In this diagram, the tile covering cell 6 also covers cells 1 and 2 so, $i=2$, and if we ignore the first two cells, we have a rectangular tiling of cells 3, 4, 5, and 6 of the form shown on the right of Figure \ref{fig:circle}.  Since $i=2$, we begin with three blanks.  Now, the tile covering cell 3 is of size 1 and has color 2, so we place the digit 1 in the third position from the right to obtain \underline{\phantom{X}} 1 \underline{\phantom{X}} \underline{\phantom{X}}.  Next, the tile covering cell 4 is of size 1 and has color 4, so we place the digit 2 in the fifth position from the right to obtain 2 \underline{\phantom{X}} 1 \underline{\phantom{X}} \underline{\phantom{X}}.  Finally, the tile covering cells 5 and 6 has size 2 and color 5, so we place 3 at the end of the partial permutation and then place 4 in the sixth position from the end to obtain 2 4 \underline{\phantom{X}} 1 \underline{\phantom{X}} \underline{\phantom{X}} 3.  Disregarding the 4 gives 2 \underline{\phantom{X}} 1 \underline{\phantom{X}} \underline{\phantom{X}} 3.  There are digits in positions 1, 3, and 6, and so this corresponds to a permutation of the subset $\{1,3,6\}$.  Since the 1 is in position 3, the 3 comes first; since the 2 is in position 1, the 1 comes second, and finally 6 comes last.  This tiling corresponds to the ordered arrangement 316.

\begin{figure}
\centering
\begin{tikzpicture}
\draw[gray, dotted] (0,1)--(0,1.75);
\draw[gray, dotted] (0.866,0.5)--(1.515,0.875);
\draw[black] (0.866,-0.5)--(1.515,-0.875);
\draw[black] (0,-1)--(0,-1.75);
\draw[gray, dotted] (-0.866,0.5)--(-1.515,0.875);
\draw[black] (-0.866,-0.5)--(-1.515,-0.875);
\node at (0.6875,-1.191) {2};
\node at (-0.6875,-1.191) {4};
\node at (0,1.375) {5};
\draw[thick](0,0) circle (1.75);
\draw[thick](0,0) circle (1);
\end{tikzpicture}
\hspace{0.5in}
\begin{tikzpicture}
\draw[black] (1,-0.5)--(1,0.5);
\draw[black] (2,-0.5)--(2,0.5);
\node at (0.5,0) {2};
\node at (1.5,0) {4};
\node at (3,0) {5};
\draw[thick] (0,-0.5)--(4,-0.5)--(4,0.5)--(0,0.5)--(0,-0.5);
\end{tikzpicture}
    \caption{A $6$-cell biggest-color circular array tiling and its corresponding partial rectangular board tiling, which map to the ordered arrangement 316 of the subset $\{1,3,6\}$.}
    \label{fig:circle}
\end{figure}



\begin{theorem}\label{T:small_circular array}
Let $\cs_n$ be the number of tilings of an $n$-cell circular array where the number of possible colors of a tile $t$ is determined by the smallest cell $t$ covers.  Then 

$$\cs_n= \sum_{k=2}^{n+1} \frac{k!}{2}. \text{ (OEIS \seqnum{A345889})}$$
\end{theorem}


\begin{proof}
Consider a tiling counted by $\cs_n$. Either the tile covering position $n$ also covers position 1 or it does not. For the first case, since the tile covering position $n$ also covers position 1, we can remove position $n$ from the circular tiling and shrink the tile by size 1 to obtain one of $\cs_{n-1} = \displaystyle\sum_{k=2}^{n} \frac{k!}{2}$ possible colored tilings of an $(n-1)$-cell circular array. For the later case, since the tile covering array position $n$ does not cover position 1, by cutting the array between cells $n$ and 1, we obtain one of the $\rs_{n} = \frac{(n+1)!}{2}$ colored tilings of Theorem \ref{T:small_rectangles}. Since these cases are mutually exclusive, we conclude that $\cs_n = \displaystyle\sum_{k=2}^{n} \frac{k!}{2} + \frac{(n+1)!}{2} = \sum_{k=2}^{n+1} \frac{k!}{2}$ as desired.

\end{proof}

While $\cs_n$ is new to OEIS, $\cs_n-\cs_{n-1}$ is given by \seqnum{A001710}, which we saw in Theorem \ref{T:small_rectangles} as the number of even permutations of size $n+1$.  In other words, $\cs_n$ corresponds to the number of even permutations of size \emph{at most} $n+1$ (and at least 2).  We can see this as a corollary to the proof of Theorem \ref{T:small_circular array} since, if we consider the tile covering cell 1 and delete the $i$ cells left of 1 ($0 \leq i \leq n-1$) that are covered with this tile, we obtain a tiling of an $n-i$ cell circular array where different tiles cover cell 1 and cell $n-i$.  In this situation, the tiling is equivalent via bijection $g$ to a tiling counted by $\rs_{n-i}$, which we know to be in bijection with the even permutations of size $n-i+1$, so after running over all possible values of $i$, we have tilings in correspondence with all even permutations of lengths between 2 and $n+1$ inclusive.


\section{Acknowledgments}

We are thankful to an anonymous referee whose suggestions improved the clarity of this paper.


\begin{thebibliography}{9}
\bibitem{BQ03} A. Benjamin and J. Quinn, \emph{Proofs that Really Count: The Art of Combinatorial Proof}, MAA Press, 2003.
\bibitem{DXTBA} G. Dresden and Y. Xiao, Weighted sums of Fibonacci and Lucas numbers through colorful tilings, preprint, 2021. To appear in \emph{Fibonacci Quart.}. Available at \newblock \url{https://dresden.academic.wlu.edu/files/2021/01/WeightedSumsWebsite.pdf}.
\bibitem{OEIS} N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, published electronically at \url{https://oeis.org}, 2021.
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05B45, Secondary 05A05, 05A10.

\noindent \emph{Keywords: }
tiling, rectangle, inversion, permutation.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000079},
\seqnum{A000225},
\seqnum{A001710},
\seqnum{A002627},
\seqnum{A033312},
\seqnum{A094258},
\seqnum{A345887}, and
\seqnum{A345889}.)


\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received June 29 2021;
revised version received November 9 2021.
Published in {\it Journal of Integer Sequences}, November 26 2021.

\bigskip
\hrule
\bigskip

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



\end{document}
