\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\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,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\usepackage{geometry}
\DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `dirname #1`/`basename #1 .tif`.png}
\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 Restricted Tilings and Bijections
}
\vskip 1cm
\large
Barry Balof \\
Department of Mathematics\\
Whitman College\\
345 Boyer Avenue \\
Walla Walla, WA 99362 \\
USA\\
\href{mailto:balofba@whitman.edu}{\tt balofba@whitman.edu}\\
\end{center}
\vskip .2 in
\begin{abstract}
A classic problem in elementary combinatorics asks in how many ways one
can tile a $1\times n$ chessboard using $1\times 1$ and $1\times 2$
squares. The number of such tilings is the $n$th Fibonacci number. In
a 2010 paper, Grimaldi generalized this problem by allowing for
$1\times 1$ tiles to have one of $w$ types and $1\times 2$ tiles to
have one of $t$ types and found that the solutions, in $w$ and $t$,
satisfied many of the same properties as do the Fibonacci and Lucas
numbers. In this paper, we present a variant of this generalization.
Namely, we require that no two adjacent $1\times 1$ tiles be of the
same type. This restriction leads to interesting combinatorial
connections with coordination sequences and problems in enumerative set
theory. We explore these connections, as well as some formulas for
generating functions for the numbers of these types of tilings.
\end{abstract}
\section{The Basic Generalization}
In a 2010 paper, Ralph Grimaldi \cite{GR} presented the following generalized tiling problem:
\begin{quote}
In how many ways can one tile a $1\times n$ chessboard using $1\times 1$ tiles that come in $w$ types and $1\times 2$ tiles that come in $t$ types?
\end{quote}
Grimaldi found a second order recurrence relation, then solved that relation to come up with a set of numbers that satisfied many of the same properties as do the Fibonacci numbers and the Lucas numbers. In this paper, we consider the following variant:
\begin{quote}
In how many ways can one tile a $1\times n$ chessboard using $1\times 1$ tiles that come in $w$ types and $1\times 2$ tiles that come in $t$ types, such that {\em no two adjacent $1\times 1$ tiles are of the same type? }
\end{quote}
With this property, we are insisting that $1\times 1$ tiles `behave' like $1\times 1$ tiles. That is, they appear as single `distinguishable' tiles in the actual tilings. If, for example, the tiles come in different colors, then we can assign one set of $w$ colors to the $1\times 1$ tiles and a different set of $t$ colors to the $1\times 2$ tiles. Then, it would not be the case in any of our permissible tilings that two $1\times 1$ tiles would be mistaken for a $1\times 2$ tile. In the following, we will refer to tilings that follow this rule as {\em restricted tilings}.
\section{Recurrence Relations}
Grimaldi gives the following second-order linear recurrence relation for $a_n$, the number of tilings with no restrictions:
\begin{theorem}[Grimaldi 2010]
The number of tilings of a $1\times n$ chessboard with $1\times 1$ tiles in $w$ types and $1\times 2$ tiles in $t$ types is $a_n$, where $a_0=1, a_1=w$ and
$$a_n=wa_{n-1}+ta_{n-2} \; \; \;\; \; (n\geq 2).$$
\end{theorem}
\begin{proof}
There is one way to tile an empty board and $w$ choices for a tile to cover a $1\times 1$ board. To construct a tiling of a $1\times n$ board, one can either append a $1 \times 1$ tile to an existing tiling of a $1\times (n-1)$ board (in $w$ ways), or a $1\times 2$ tile to an existing tiling of a $1\times (n-2)$ board (in $t$ ways).
\end{proof}
This second order recurrence relation leads to a quadratic characteristic equation whose roots satisfy some interesting combinatorial properties similar to those satisfied by the Fibonacci and Lucas numbers.
The linear recurrence relation for the number of restricted tilings also has a straightforward and constructive proof, but is of third-order:
\begin{theorem}
The number of restricted tilings of a $1\times n$ chessboard with $1\times 1$ tiles in $w$ types and $1\times 2$ tiles in $t$ types is $a_n^*$ where $a_{-1}^*=0, a_0^*=1, a_1^*=w$ and $$a_n^*=(w-1)a_{n-1}^*+ta_{n-2}^*+ta_{n-3}^* \;\; \; \; \; (n\geq 2).$$
\label{recursion}
\end{theorem}
\begin{proof}
We assign $a^*_{-1}=0$ by convention, and as before, there are $1$ and $w$ ways to tile an empty board and a $1\times 1$ board, respectively. We have three possibilities to consider for the tiling of a $1\times n$ chessboard:
\begin{enumerate}
\item[Case (1)] Our tiling ends in a $1\times 2$ tile.
\item[Case (2)] Our tiling ends in exactly one $1\times 1$ tile.
\item[Case (3)] Our tiling ends in two or more $1\times 1$ tiles.
\end{enumerate}
Let $a_{n,1}^*$ (respectively, $a_{n,2}^*$) denote the number of tilings of a $1\times n$ board that end with a $1\times 1$ ($1\times 2$) tile. Then $a_n^*=a_{n,1}^*+a_{n,2}^*$. We count the tilings by cases.
\begin{itemize}
\item The tilings in case 1 are precisely those counted by $a_{n,2}^*$. We generate such a tiling by appending any of $t$ types of $1\times 2$ tile (without restrictions) to any tiling of a $1\times (n-2)$ board. Thus, we have $a_{n,2}^*=ta_{n-2}^*$ tilings in case 1.
\item The tilings in case 2 are generated by appending any of $t$ types of $1\times 2$ tile followed by any of $w$ types of $1\times 1$ tile (again, with no restrictions) to the end of any tiling of a $1\times (n-3)$ board. Thus, we have $wta_{n-3}^*$ tiling of boards in case 2.
\item If our tiling ends with two or more $1\times 1$ tiles (case 3), we can generate it by appending a $1\times 1$ tile to a $1\times (n-1)$ tiling that itself ends in a $1\times 1$ tile. This can be done in $(w-1)$ ways for any such tiling, as the types of the last two tiles must be distinct. Thus, the tilings in case 3 are counted by $(w-1)a_{n-1,1}^*$. By our earlier count of all of $a_n^*$, we have that $$(w-1)a_{n-1,1}^*=(w-1)[a_{n-1}^*-a_{n-1, 2}^*]=(w-1)a_{n-1}^*-(w-1)ta_{n-3}^*$$
\end{itemize}
We now combine the three cases to get our recursion formula for $a_n^*$.
$$a_n^*=ta_{n-2}^*+wta_{n-3}^*+(w-1)a_{n-1}^*-(w-1)ta_{n-3}^*$$
$$=(w-1)a_{n-1}^*+ ta_{n-2}^* + (wt-(w-1)t)a_{n-3}^*$$
$$=(w-1)a_{n-1}^*+ta_{n-2}^*+ta_{n-3}^*.$$
\end{proof}
Where necessary, we will use the notation $a_n^* (w,t)$ in place of $a_n^*$, as we now have that for each $n$, $a_n^*$ is a polynomial in $w$ and $t$. This notation will prove useful later when we examine some specific cases, especially those where we need a value for $w$ or for $t$ but not for both.
We pause here to note a similarity between our recursion formula and one for a non-restricted tiling involving squares in $(w-1)$ types, dominos in $t$ types, and triominos ($1\times 3$ tiles) in $t$ types. Though the recursion portions of the formulas are the same, the initial conditions are different (the number of tilings on a $1\times 1$ board in the restricted case is $w$, whereas the number in the non-restricted case is $w-1$, which leads to different numbers of these tilings for different sized boards). Benjamin and Quinn \cite{Benjamin} interpret this recursion with these initial conditions in terms of `phased' tilings (where an initial square has one of $w$ phases and all other squares coming in $w-1$ types, while dominos and triominos each coming in $t$ types).
The recursion proven in Theorem \ref{recursion} gives rise to the following cubic characteristic equation:
$$r^3-(w-1)r^2-tr-t=0$$
which gives rise to three roots, $\alpha, \beta$ and $\gamma$ which satisfy the following equations:
$$\alpha + \beta + \gamma = (w-1)$$
$$\alpha \beta +\alpha \gamma +\beta \gamma = -t$$
$$\alpha \beta \gamma = t,$$
which, when combined, yield:
$$\alpha+\beta+\gamma+\alpha\beta + \alpha \gamma + \beta \gamma + \alpha\beta\gamma = w-1$$
$$(\alpha +1)(\beta + 1)(\gamma + 1)-1=w-1,$$
or,
$$(\alpha +1)(\beta + 1)(\gamma + 1)=w.$$
Though we can use computational software to lay hands on explicit formulas for $\alpha, \beta$ and $\gamma$, we may be better served at this point to explore the combinatorics of some specific cases.
\section{Some Specific Values of $t$ and $w$}
When we allow ourselves only one type of $1\times 1$ tile, the number of tilings is quite restricted. Notice that we are not allowed consecutive $1\times 1$ tiles in any tilings. To form new tilings from existing tilings, we must append either a $1\times 2$ tile to any tiling of a $1\times (n-2)$ board, or append a $1\times 2$ tile followed by a $1\times 1$ tile to any tiling of a $1\times (n-3)$ board. These constructions play out in the recursion formula.
\begin{example}
For $w=1$ and $t=1$, we have $a_0^*= a_1^*=a_2^*=1$, and, for $n\geq 3$
$$a_n^*=a_{n-2}^* + a_{n-3}^*.$$
\end{example}
The sequence of values for $a_n^*$ in this case is the Padovan sequence
\seqnum{A000931} $$1,1,1,2,2,3,4,5, 7, 9, 12, 16, 21, 28 \dots
$$.
We find that the term $a^*_n$ counts the number of ordered partitions of $(n+4)$ into parts that are congruent to 2 modulo 3. (For example, $a^*_6=4$, with the partitions of 10 being 8+2, 2+8, 5+5, and 2+2+2+2+2.) The term $a^*_n$ also counts the number of ordered partitions of $(n+5)$ into parts that are odd and greater than 3. (For example, again, $a^*_6=4$, with the partitions of 11 being 5+3+3, 3+5+3, 3+3+5, and 11.) The reader is invited to come up with the appropriate bijections for these cases.
Our characteristic equation for this recurrence is $r^3-r-1=0$. It has, as its roots, the so called {\em plastic constant}
$$P=\frac{\,\sqrt [3]{108+12\,\sqrt {69}}}{6}+\,{
\frac {2}{\sqrt [3]{108+12\,\sqrt {69}}}} \approx 1.324717958,$$
as well as the conjugate imaginary roots
$$\scriptstyle \frac{-1}{12}\,(\sqrt [3]{108+12\,\sqrt {69}} \; - \; {\frac {1}{\sqrt [3]{108+12\,
\sqrt {69}}}}) \pm \frac{i\sqrt{3}}{2} \left( \frac{\sqrt [3]{108+12\,\sqrt {69}
}}{6}\,\;-\,{\frac {2}{\sqrt [3]{108+12\,\sqrt {69}}}} \right) .$$
The plastic constant, together with the Golden Ratio ($\phi=\frac{1+\sqrt{5}}{2}$) are the only {\em morphic numbers} \cite{AFK}.
When we have two types of $1\times 1$ tile and one type of $1\times 2$ tile, our recursion is of another semi-famous sequence:
\begin{example}
For $w=2$ and $t=1$, we have $a_0^*=1$, $a_1^*=2$, $a_2^*=3$, and, for $n\geq 3$,
$$a_n^*=a_{n-1}^*+a_{n-2}^* + a_{n-3}^*.$$
\end{example}
The sequence of values in this case is a Tribonacci sequence \seqnum{A001590}:
$$1,2,3,6,11,20,37,68,\dots .$$
\section{The Specific Value $w=2$}
When we allow for two types of $1\times 1$ tile, and an arbitrary number $t$ of types of $1\times 2$ tiles, we have the following recursion:
\begin{example}
For $w=2$ and $t$ arbitrary, we have $a_0^*=1$, $a_1^*=2$, $a_2^*=2+t$, and, for $n\geq 3$,
$$a_n^*=a_{n-1}^*+ta_{n-2}^* +t a_{n-3}^*.$$
\end{example}
Following this recursion formula, we get the following polynomials $P_n(t)$, which each give the number of restricted tilings of a $1\times n$ chessboard where the $1\times 1$ tiles come in two types. (Note: $P_n(t)=a_n^*(2,t)$, that is, $a_n^*$ evaluated when $w=2$.)
\begin{center}
\begin{tabular}{c|l}
$P_0(t)$ & $1$ \\
$P_1(t)$ & $2$ \\
$P_2(t)$ & $2+t$ \\
$P_3(t)$ & $2+4t$ \\
$P_4(t)$ & $2+8t+t^2$\\
$P_5(t)$ & $2+12t+6t^2$ \\
$P_6(t)$ & $2+16t+18t^2+t^3$ \\
$P_7(t)$ & $2+20t+38t^2+8t^3$\\
$P_8(t)$ & $2+24t+66t^2+32t^3+t^4$\\
$P_9(t)$ & $2+28t+102t^2+88t^3+10t^4$\\
\end{tabular}
\end{center}
The patterns in the coefficients on $t^k$ merit combinatorial explanations. The constant term in each polynomial after the trivial case is 2, owing to the fact that a $1\times n$ chessboard tiled entirely with $1\times 1$ squares must necessarily alternate types of square. Thus, when one chooses the type of the first square (in 2 ways), the remainder of the tiling is determined.
We notice that the coefficients on $t$ in each of the polynomials are all multiples of 4 (with the exception of $P_2(t)$), a fact which has a straightforward counting justification:
\begin{proposition} The coefficient of $t$ in $P_n(t)$, which counts the number of tilings of a $1\times n$ board that use exactly one $1\times 2$ tile, is 1 for $n=2$ and $4(n-2)$ for $n\geq 3$.
\end{proposition}
\begin{proof}
The case for $n=2$ is trivial (there is only one tiling, up to tile types, of a $1\times 2$ board with one $1\times 2$ tile). For $n\geq 3$, we look for possible placements of the one $1\times 2$ tile. It may be on either end, in which case there is one string of $1\times 1$ tiles. There are two such strings (as the $1\times 1$ tiles must necessarily alternate), giving a total of 4 tilings in which the $1\times 2$ tile is on either end. If that tile is not on either end, there are $n-3$ possible placements for it (the left-most square of the $1\times 2$ tile may not be in the first square or either of the last two squares). In these cases, there are two strings of $1\times 1$ tiles which come in two types each, for a total of $4(n-3)$ tilings where our $1\times 2$ tile is not on an end. Our total count of tilings is thus $4+4(n-3)=4(n-2)$.
\end{proof}
The sequence of coefficients on $t^2$ is a little bit less straightforward to deal with directly. A count similar to the one given above (where one counts possibilities for the two tiles to be together or separate, and on the ends or not) will justify the following formula.
\begin{proposition} The coefficient of $t^2$ in $P_n(t)$, which counts the number of tilings that use exactly two $1\times 2$ tiles, is 1 for $n=4$ and $$6+12(n-5)+4(n-5)(n-6)=4(n-4)^2+2$$ for $n\geq 5$.
\end{proposition}
The sequence of terms $$1,6,18,38,66, 102\dots$$
appears as \seqnum{A005899} in \cite{OEIS}, where it appears as the {\em coordination sequence} for the cubic lattice. A coordination sequence in an atomic framework is a sequence in which the $k$th term counts the number of atoms in the $k$th shell that are bonded to atoms in the ($k-1$)st shell \cite{GK}. As mathematicians, we can view this in terms of distances and metrics.
\begin{definition}
In a {\em coordination sequence} $\{a_i\}_{i=0}^\infty$, $a_k$ counts the number of lattice points in a fixed number of dimensions that are at a distance $k$ from the origin under the taxicab metric (i.e., the number of lattice points whose coordinates, in absolute value, sum to $k$).
\end{definition}
We now present a natural bijection between our tilings and these lattice points, which we generalize:
\begin{proposition}
The coefficient on $t^k$ in the polynomial $P_n(t)$ is the $(n-2k)$th term in the coordination sequence for the cubic\footnote{The term `cubic' here refers to the arrangement of the points within the lattice, and applies to all dimensions, including those other than 3.} lattice in $(k+1)$-dimensional space.
\end{proposition}
\begin{proof}
We give our proof by establishing a bijection between
\begin{itemize}
\item Restricted tilings of a $1\times n$ chessboard with $k$ $1\times 2$ tiles and $(n-2k)$ $1\times 1$ tiles in two types,
and
\item Lattice points in $(k+1)$-dimensional space that are distance $n-2k$ from the origin under the taxicab metric.
\end{itemize}
Start with a tiling of the $1\times n$ chessboard. This tiling has $k$ $1\times 2$ tiles, thus $n-2k$ $1\times 1$ tiles. The $k$ $1\times 2$ tiles break the remaining tiles into $k+1$ (possibly empty) strings of consecutive $1\times 1$ tiles that alternate types of tile, and whose total length must be $n-2k$. We assign this tiling to the point $(a_1, a_2, \dots, a_k, a_{k+1})$, where $|a_i|$ is the length of the $i$th string of $1\times 1$ tiles, and $a_i$ is positive or negative depending on whether the string starts with a tile of type 1 or of type 2, respectively. Note that an empty string does not start with either type of tile, nor do we need to choose a sign for the coordinate (0) in that case. The map is well-defined in that any given tiling leads to a unique lattice point.
If we start with the lattice point $(b_1, b_2, \dots, b_k, b_{k+1})$, where $\sum_{i} |b_i|=(n-2k)$, we construct a tiling consisting of $(k+1)$ strings of alternating $1\times 1$ tiles. The $i$th string is of length $|b_i|$, and starts with a tile of type 1 (type 2) if $b_i$ is positive (negative). Each of these strings are separated by a $1\times 2$ tile (of which there are $k$ in all), thus giving a restricted tiling of a $1\times n$ chessboard with $k$ $1\times 2$ tiles and $(n-2k)$ $1\times 1$ tiles in two types.
\end{proof}
We have thus generalized our result for coordination sequences to all coefficients on the $P_n(t)$, that is:
\begin{itemize}
\item The coefficients on $t^3$ are the coordination sequence for the $4$-dimensional cubic lattice: $1,8,32,88, 192, 360, \dots$
\item The coefficients on $t^4$ are the coordination sequence for the $5$-dimensional cubic lattice: $1,10,50,170,450,1002\footnote{Curiously, while all other terms are multiples of 10, every fifth term of this sequence is of the form $1000m+2$.}, \dots$
\item The coefficients on $t^5$ are the coordination sequence for the $6$-dimensional cubic lattice: $1, 12, 72, 292, 912, 2364, \dots$
\end{itemize}
We give a few examples to illustrate our bijection. In the following, we use $a$ and $b$ to denote $1\times 1$ tiles of the first and second type, and a $2$ to denote a $1\times 2$ tile. Each tiling is of a $1\times 14$ board.
$$ababa2aba2ab \leftrightarrow (5,3,2)$$
$$ababa2bab2ab \leftrightarrow (5,-3,2)$$
$$bab2bab2a2b \leftrightarrow (-3,-3,1,-1)$$
$$a22bab2a2b \leftrightarrow (1,0,-3,1,-1)$$
\section{Tilings and Subsets}
In the description of \seqnum{A005899}, we have the following
explanation of the aforementioned sequence of coefficients on $t^2$ in
the polynomials $P_n(t)$ due to Milan Janjic \cite{MJ}.
\begin{quote}
If $X$ is an n-set and $Y_i$ (i=1,2,3) are mutually disjoint 2-subsets of $X$ then $a^*_{n-5}$ is equal to the number of 5-subsets of X intersecting each $Y_i$ (i=1,2,3).
\end{quote}
We will establish, and generalize, a natural bijection between these subsets and our tilings, through the following investigation. Suppose our set $X$ consists of the first $n$ integers, our sets $Y_i$ are the subsets $\{1,2\}, \{3,4\}$ and $\{5,6\}$. Suppose also that we have a tiling of a $1\times (n-1)$ board with two $1\times 2$ tiles and $(n-5)$ $1\times 1$ tiles in two types, with no two adjacent $1\times 1$ tiles of the same type. Our two $1\times 2$ tiles split the remaining $(n-5)$ tiles into three (possibly empty) strings of $1\times 1$ tiles. We wish to use the tiling to construct a subset of size 5 which intersects each of the sets $Y_i$, which we do as follows:
\begin{itemize}
\item If the $i$th string begins with a $1\times 1$ tile of type $a$, we take the first element in $Y_i$.
\item If the $i$th string begins with a $1\times 1$ tile of type $b$, we take the second element in $Y_i$.
\item If the $i$th string is empty, we take both elements in $Y_i$.
\end{itemize}
For any tiling with at least one $1\times 1$ tile, we have either zero, one, or two empty substrings of $1\times 1$ tiles, which means that we have taken either three, four, or five elements, respectively, from the $Y_i$ into our subset. If we have all five elements (and hence, only one non-empty string), we're done. Otherwise, our non-zero strings give an ordered partition of $n-5$ into two or three non-zero parts. We choose our first elements using the method above. Our $n$ set has $n-6$ elements which are {\em not} part of any of the $Y_i$. We must choose some of these elements to complete our subset of five elements. This can be done in a natural way. If we think of our $n-5$ tiles as `stars', then there are $n-6$ places between consecutive stars to place `bars'. Our placement of these bars will determine which elements from the last $n-6$ elements in $X$ will complete our subset. Note that
\begin{itemize}
\item If we have one empty string of $1\times 1$ tiles, then the $Y_i$ have contributed 4 elements to our subset. Thus, we need one element to complete our subset. Our two non-empty strings divide the ($n-5$) $1\times 1$ tiles into two parts, which requires 1 `bar'. We take the position of that bar as our extra element.
\item If we have no empty strings of $1\times 1$ tiles (hence, three elements from the $Y_i$), we need two elements to complete our subset. Our three non-empty strings divide the $(n-5)$ $1\times 1$ tiles into three parts, which requires 2 `bars'. We take the positions of these bars as our extra elements.
\end{itemize}
We illustrate our bijection with a few examples. In the following, as above, we use $a$ and $b$ to denote $1\times 1$ tiles of the first and second parts, respectively, and a $2$ to denote a $1\times 2$ tile. Our tilings are of a $1\times 11$ board, which we are placing in correspondence with 5-subsets of the set $X=\{1, 2, \dots 12\}$
$$22abababa \leftrightarrow \{1,2,3,4,5\}$$
$$22bababab \leftrightarrow \{1,2,3,4,6\}$$
$$ab2babab2 \leftrightarrow \{1,4,5,6,8\}$$
$$aba22baba \leftrightarrow \{1,3,4,6,9\}$$
$$baba2a2ab \leftrightarrow \{2,3,5,10,11\}$$
This construction of the correspondence between certain subsets of a ground set and our restricted tilings of a $1\times n$ chessboard has a natural generalization, which we give here.
\begin{proposition}
There is a bijection between the following sets:
\begin{itemize}
\item The set of tilings of a $1\times (j+2k)$ chessboard using $j$ $1\times 1$ tiles in two types and $k$ $1 \times 2$ tiles, such that no two consecutive $1\times 1$ tiles are of the same type.
\item The set of $2k+1$-subsets of a $(j+2k+1)$ set $X$, which intersect each of $k+1$ mutually disjoint 2-subsets $Y_i$ $(i=1,2,\dots ,k,k+1)$.
\end{itemize}
\end{proposition}
\begin{proof}
We generalize our construction from above. The $k$ $1\times 2$ tiles break our $j$ $1\times 1$ tiles into $k+1$ (possibly empty) strings of tiles, which must necessarily alternate. As before, we use our strings to build our subset of the set $X=\{1,2,3,\dots, 2k+j+1\}$. We first choose those elements from our sets $Y_i=\{2i-1, 2i\}$ (that is, as before, $Y_1=\{1,2\}$, $Y_2=\{3,4\}$, etc.).
\begin{itemize}
\item If the $i$th string begins with a $1\times 1$ tile of the first type, we take the first element in $Y_i$.
\item If the $i$th string begins with a $1\times 1$ tile of the second type, we take the second element in $Y_i$.
\item If the $i$th string is empty, we take both elements in $Y_i$.
\end{itemize}
This process gives us at least $k+1$ of our $2k+1$ elements for our subset. For any tiling with at least one $1\times 1$ tile, we have anywhere between 0 and $k$ empty strings. As each empty string gives us one extra element from the $Y_i$, we need to choose between $k$ and 0 more elements for our subset from the $j-1$ elements in $X$ but not in any $Y_i$. Suppose that we have $k-l$ empty strings, and thus need $l$ elements to complete our subset. Then we have $l+1$ non-empty strings in which to partition the $j$ $1\times 1$ tiles. If, as above, we view the $j$ $1\times 1$ tiles as `stars', we have $j-1$ spaces between the tiles in to place `bars.' Thus we assign each space to one of our elements in $X$ but not in any $Y_i$. Creating a partition into $l+1$ non-empty strings will require choosing $l$ positions in which to place our `bars'. We take the $l$ elements corresponding to those positions to complete our subset.
Given a subset with an odd number of elements (which meets the intersection conditions) and the size of the ground set from which it was taken, we can reconstruct an appropriate tiling. We do this by working backwards through the algorithm used to create the subset. If our subset was of size $2s+1$ and the ground set of size $t$, our tiling will be of a $1\times (t-1)$ board and use $s$ $1\times 2$ tiles (and would have to intersect each of the first $(s+1)$ 2-element subsets.
\end{proof}
We present a few examples below, using our notation from above.
\begin{example}
$abab2bab2ab2bab2$
\end{example}
For this example, we have four $1\times 2$ tiles in a restricted tiling of a $1\times 20$ board. Thus, our ground set is $X=\{1, 2, \dots 21\}$ and there are five sets $Y_i$, from which we seek a 9-element subset. Based on the types of $1\times 1$ tiles, we take the elements $1, 4, 5, 8,9,10$ (the last two coming from the empty string at the end of the tiling). We need three more elements, and we see that the $1\times 1$ tiles are parted in the fourth, seventh, and ninth possible positions. Thus, we add elements $14, 17$ and $19$ to complete our subset:
\[abab2bab2ab2bab2\leftrightarrow \{1,4,5,8,9,10,14,17,19 \}\]
\begin{example}
$babab2a2ba2ba$
\end{example}
For this example, we have three $1\times 2$ tiles in a restricted tiling of a $1\times 16$ board. Thus, our ground set is $X=\{1,2,\dots,17\}$ and there are four sets $Y_i$, from which we seek a seven element subset. Based on the types on $1\times 1$ tiles, we take the elements $2, 3, 6$ and $8$ into our subset. We need three more elements, based on the fact that we have four nonempty strings of $1\times 1$ tiles. These tiles are parted in the fifth, sixth, and eighth possible places. We take the corresponding elements from those not in the $Y_i$, namely $13, 14$ and $16$, which completes our subset:
\[ babab2a2ba2ba\leftrightarrow \{2,3,6,8,13,14,16\} \] \
Given a subset and the size of the ground set from which it was taken, we can determine a unique restricted tiling, as shown in the next example.
\begin{example}
$\{1,3,4,6,7,10,12\}$ as a 7-element subset of $\{1,2,\dots, 15\}$.
\end{example}
Based on the sizes of our sets, we are seeking a restricted tiling of a $1\times (15-1)=1\times 14$ board using $\frac{7-1}{2}$, or three $1\times 2$ tiles and eight $1\times 1$ tiles. It is important that we first check that we have a valid subset for our bijection, namely one that intersects each of the sets $\{1,2\}$, $\{3,4\}$ $\{5,6\}$, and $\{7,8\}$ (which it does).
We next look to our elements outside of these sets, namely $10$ and $12$. These tell us that there are three nonempty strings (of the four total) of $1\times 1$ tiles totaling eight tiles in length, and they are divided in the second and fourth possible place (as 10 and 12 are the second and fourth elements beyond our designated subsets). Thus, our nonempty strings are of lengths two, two, and four. Based on the initial elements of the subset (1,3,4, 6, and 7), we have that the four strings are, in order, of the first type, empty, of the second type, and of the first type. Thus, we have our tiling corresponding to the subset:
$$\{1,3,4,6,7,10,12\} \leftrightarrow ab22ba2abab $$
\section{Generating Functions for Sequences of Coefficients}
In this section, we extend our analysis of the sequences of
coefficients on the polynomials $P_n(t)$ to values of $w$ other than
2. To that end, we will generalize our polynomials from the previous
section. Recall that $a_n^*$, which counts the number of restricted
tilings on a $1\times n$ board, is a polynomial in $w$ and $t$. As we
wish to compute for specific values of $w$, we will let
$P_{w_0,n}(t)=a_n^*(w_0, t)$ (that is, $a_n^*$ evaluated at the value
$w=w_0$). Below, we rewrite our polynomials from above using our
amended notation, as well as presenting the next three values for $w$.
\begin{center}
\begin{tabular}{c|l||c|l}
$\scriptstyle P_{2,0}(t)$ & $\scriptstyle 1$ & $\scriptstyle P_{3,0}(t)$& $\scriptstyle 1$\\
$\scriptstyle P_{2,1}(t)$ & $\scriptstyle 2$ & $\scriptstyle P_{3,1}(t)$& $\scriptstyle 3$\\
$\scriptstyle P_{2,2}(t)$ & $\scriptstyle 2+t$ & $\scriptstyle P_{3,2}(t)$& $\scriptstyle 6+t$ \\
$\scriptstyle P_{2,3}(t)$ & $\scriptstyle 2+4t$ & $\scriptstyle P_{3,3 }(t)$& $\scriptstyle 12+6t$\\
$\scriptstyle P_{2,4}(t)$ & $\scriptstyle 2+8t+t^2$& $\scriptstyle P_{3,4 }(t)$& $\scriptstyle 24+21t+t^2$\\
$\scriptstyle P_{2,5}(t)$ & $\scriptstyle 2+12t+6t^2$ & $\scriptstyle P_{3,5 }(t)$& $\scriptstyle 48+60t+9t^2$\\
$\scriptstyle P_{2,6}(t)$ & $\scriptstyle 2+16t+18t^2+t^3$ & $\scriptstyle P_{3,6 }(t)$& $\scriptstyle 96+156t+45t^2+t^3$\\
$\scriptstyle P_{2,7}(t)$ & $\scriptstyle 2+20t+38t^2+8t^3$& $\scriptstyle P_{3, 7}(t)$& $\scriptstyle 192+384t+171t^2+12t^3$\\
$\scriptstyle P_{2,8}(t)$ & $\scriptstyle 2+24t+66t^2+32t^3+t^4$& $\scriptstyle P_{3,8 }(t)$& $\scriptstyle 384+912t+558t^2+78t^3+t^4$\\
$\scriptstyle P_{2,9}(t)$ & $\scriptstyle 2+28t+102t^2+88t^3+10t^4$& $\scriptstyle P_{3,9 }(t)$& $\scriptstyle 768+2112t+1656t^2+372t^3+15t^4$\\
\end{tabular}
\vspace{1cm}
\begin{tabular}{c|l||c|l}
$\scriptstyle P_{4,0}(t)$ & $\scriptstyle 1$ & $\scriptstyle P_{5,0}(t)$& $\scriptstyle 1$ \\
$\scriptstyle P_{4,1}(t)$ & $\scriptstyle 4$ & $\scriptstyle P_{5,1}(t)$& $\scriptstyle 5$\\
$\scriptstyle P_{4,2}(t)$ & $\scriptstyle 12+t$ & $\scriptstyle P_{5,2}(t)$& $\scriptstyle 20+t$ \\
$\scriptstyle P_{4,3}(t)$ & $\scriptstyle 36+8t$ & $\scriptstyle P_{5,3 }(t)$& $\scriptstyle 80+10t$\\
$\scriptstyle P_{4,4}(t)$ & $\scriptstyle 108+40t+t^2$& $\scriptstyle P_{5,4 }(t)$& $\scriptstyle 320+65t+t^2$\\
$\scriptstyle P_{4,5}(t)$ & $\scriptstyle 324+168t+12t^2$ & $\scriptstyle P_{5,5 }(t)$& $\scriptstyle 1280+360t+15t^2$\\
$\scriptstyle P_{4,6}(t)$ & $\scriptstyle 972+648t+84t^2+t^3$ & $\scriptstyle P_{5,6 }(t)$& $\scriptstyle 5120+1840t+135t^2+t^3$\\
$\scriptstyle P_{4,7}(t)$ & $\scriptstyle 2916+2376t+460t^2+16t^3$& $\scriptstyle P_{5, 7}(t)$& $\scriptstyle 20480+8960t+965t^2+20t^3$\\
$\scriptstyle P_{4,8}(t)$ & $\scriptstyle 8748+8424t+2196t^2+144t^3+t^4$& $\scriptstyle P_{5,8 }(t)$& $\scriptstyle 81920+42240+6060t^2+230t^3+t^4$\\
\end{tabular}
\vspace{1cm}
\end{center}
We now give a generating function relation involving our restricted tilings which will generate the coefficients on the above polynomials in a natural fashion.
\begin{proposition}
If $c_j(w)$ is the number of restricted tilings (up to domino types) of a $1\times (j+2k)$ board that use exactly $j$ $1\times 1$ tiles in $w$ types, then
$$\left(\frac{1+x}{1-(w-1)x}\right)^{k+1}=\sum c_j(w) x^j$$
\end{proposition}
That is to say, the sequence of coefficients $c_j$ is the sequence of positive coefficients on $t^k$ in the polynomials $P_{w,n}(t)$.
\begin{proof}
We look at an algebraic construction of the given function. We note first that
$$\frac{1}{1-(w-1)x}=1+(w-1)x+(w-1)^2x^2+(w-1)^3x^3 \dots$$
as an ordinary geometric series. Continuing with our construction gives
\begin{eqnarray*} \nonumber
\lefteqn{ \frac{1+x}{1-(w-1)x} =(1+x)(1+(w-1)x+(w-1)^2x^2+(w-1)^3x^3 \dots} \nonumber\\
& = 1+(w-1)x+(w-1)^2x^2+(w-1)^3x^3 \dots \nonumber\\
& \hspace{.3in} { } +x+(w-1)x^2+(w-1)^2x^3+(w-1)^3x^4 \dots \nonumber\\
& = 1+(w-1+1)x+((w-1)^2+(w-1))x^2+((w-1)^3+(w-1)^2)x^3 +\dots\nonumber\\
&=1+wx+(w-1)wx^2+(w-1)^2 w x^3+ (w-1)^3 w x^4 +\dots \nonumber\\
\end{eqnarray*}
giving our overall function:
$$\left(\frac{1+x}{1-(w-1)x}\right)^{k+1}= (1+wx+(w-1)wx^2+(w-1)^2 w x^3+ (w-1)^3 w x^4 +\dots )^{k+1}.$$
We complete the proof by commenting on the form of the coefficients we've generated in terms of our tilings. Note that $w(w-1)^{r-1}$ is the number of restricted tilings of a string of $r$ $1\times 1$ tiles in $w$ types.
Our coefficient $c_j$ can thus be justified directly. We partition $j$ into $k+1$ (possibly empty) ordered parts. Each non-zero part $p_i$ will contribute $w(w-1)^{p_i-1}$ towards our coefficient. Thus, our coefficient $c_j$ is given by
$$c_j=\sum_{i=1}^{k+1} \sum_{p_1+p_2+\dots +p_i =j} w (w-1)^{p_1-1} w (w-1)^{p_2-1} \dots w (w-1)^{p_i-1}.$$
When we combine the `$w$' and `$(w-1)$' terms in the summation, we find that we have one `$w$' term for each non-zero part. We also have total of $j$ `($w-1$)' terms, less one ($`w-1'$) term for each non-zero part, simplifying our summation to
$$\sum_{i=1}^{k+1} \sum_{p_1+p_2+\dots +p_i =j} w^i (w-1)^{j-i}.$$
As there are ${j-1 \choose i-1}$ ways to write $j$ as the ordered sum of $i$ positive integers (see, for example, Chapter 13 of Wilson and van Lint \cite{WVL}), the sum for our coefficient further simplifies to
$$\sum_{i=1}^{k+1}{j-1 \choose i-1}w^i (w-1)^{j-i}.$$
We also get this count on our tilings, in the same vein as our earlier bijection in the case where $w=2$. Our $k$ $1\times 2$ tiles break the $1\times (j+2k)$ board into $k+1$ (possibly empty) strings. Each non-empty string has one first tile ($w$ choices) and possibly more tiles ($(w-1)$ choices each). Thus, we make our count based on $i$ nonempty strings (which amounts to choosing $i-1$ of $j-1$ possible places to break up the $1\times 1$ tiles, and sum over all $i\leq j$).
$$c_j=\sum_{i=1}^{k+1} {j-1 \choose i-1} w^i (w-1)^{j-i}.$$
\end{proof}
We note that the generating function works for all positive values of $w$, specifically in the case where $w=1$, which we enumerated earlier in the specific case of $t=1$. The polynomials $P_{1,n}(t)=a_n^*(1, t)$ (that is, $a_n^*$ evaluated at $w=1$) form the following sequence:
$$1,1,t,2t, t+t^2, 3t^2, 3t^2+t^3, t^2+4t^3, 6t^3+t^4, 4t^3+5t^4\dots$$
which gives the following recognizable coefficients:\
\begin{tabular}{c l}
Powers of $t$ & Sequence of Coefficients \\
$t$ & 1,2,1 \\
$t^2$ & 1,3,3,1 \\
$t^3$ & 1,4,6,4,1 \\
$t^4$ & 1,5,10,10,5,1 \\
$t^5$ & 1,6,15,20,15,6,1 \\
\end{tabular}
\vspace{1cm}
which makes sense given our generating function:
$$\left(\frac{1+x}{1-(1-1)x}\right)^{k+1}=(1+x)^{k+1}.$$
\section{Future Directions}
Many of the questions and properties posed by Grimaldi \cite{GR} extend
naturally to our restricted tilings, namely that we can analyze the
number of rises and levels in these tilings as functions of $w$ and
$t$. We can also look at {\em circular} restricted tilings, which may
have as straightforward a recursion as do the linear restricted
tilings. It may also be feasible to extend our subset example to those
cases beyond $w=2$.
\section{Acknowledgements}
The author would like to thank Dominc Klyve who provided useful
feedback on an earlier draft of this article. The author would also
like to thank the anonymous referee who provided numerous helpful
comments that improved the exposition and streamlined the proof of
Theorem \ref{recursion}.
\begin{thebibliography}{7}
\bibitem{AFK}
J. Aarts, R. Fokkink, and G. Kruijtzer,
\newblock Morphic numbers,
\newblock {\it Nieuw Arch. Wisk.} {\bf 5} (2001), 56--58.
\bibitem{Benjamin}
A. T. Benjamin and J. J. Quinn,
\newblock {\em Proofs that Really Count: The Art of Combinatorial Proof,}
\newblock Mathematical Association of America, 2003.
\bibitem{GR}
R. P. Grimaldi,
\newblock Tilings, compositions, and generalizations,
\newblock {\em J. Integer Seq.} {\bf 13}, 2010,
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL13/Grimaldi/grimaldi5.html}{Article 10.6.5}.
\bibitem{MJ}
Milan Janjic,
\newblock Two enumerative functions, preprint, available at \hfil
\newblock \url{www.pmfbl.org/janjic/enumfor.pdf}.
\bibitem{GK}
R. W. Grosse-Kunstleve, G. O. Brunner, and N. J. A. Sloane,
\newblock Algebraic description of coordination sequences and exact topological densities for zeolites,
\newblock {\it Acta Cryst.} {\bf A52} (1996), 879--889.
\newblock Available at \hfil
\url{http://www2.research.att.com/~njas/doc/ac96cs/}.
\bibitem{WVL}
J. H. van Lint and R. M. Wilson,
\newblock {\em A Course in Combinatorics}, 2nd edition,
\newblock Cambridge University Press, 2001.
\bibitem{OEIS}
N. J. A. Sloane,
\newblock The Online Encyclopedia of Integer Sequences,\hfil
\url{http://oeis.org/}.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05A15; Secondary 05B45.
\noindent \emph{Keywords: }
chessboard tiling, Fibonacci number, Tribonacci number, coordination sequence,
combinatorial bijections.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A000931},
\seqnum{A001590}, and
\seqnum{A005899}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received April 4 2011;
revised versions received November 15 2011; December 29 2011.
Published in {\it Journal of Integer Sequences}, December 30 2011.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}