\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}
\usepackage{tikz}
\DeclareMathOperator{\Ones}{Ones}
\DeclareMathOperator{\Rows}{Rows}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\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}
\newtheorem{result}[theorem]{Result}
\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
On Counting the Number of Tilings of a \vskip .03in
Rectangle with Squares of Size 1 and 2 \\
}
\vskip 1cm
\large
Johan Nilsson\\
LIPN Universit\'e Paris 13 \\
93430 Villetaneuse \\
France\\
\href{mailto:nilsson@lipn.univ-paris13.fr}{\tt nilsson@lipn.univ-paris13.fr} \\
\end{center}
\vskip .2 in
\begin{abstract}
We consider tilings of a rectangle of size $n\times k$ with square tiles of size $1\times1$ and $2\times2$. We present a method to calculate the number of such tilings via matrix multiplication, where we optimize the number of multiplications needed and reduce the space required for the matrix multiplication by dynamically generating the matrices involved.
\end{abstract}
\section{Introduction}
In this paper we study the problem of calculating the number of tilings of a rectangle $R$ with square tiles of size $1\times1$ and $2\times2$. This tiling problem is easily seen to be equivalent to another classical problem, the problem of counting the number of ways of placing non-attacking kings on a rectangular chessboard. Our version and the chess formulation of the problem have been widely studied in different formulations and aspects; see \cite{calkin, race, wilf}, as well as the sequences \seqnum{A063443}, \seqnum{A193580} and \seqnum{A245013} in the On-Line Encyclopedia of Integer Sequences OEIS \cite{oeis}.
Here we discuss a method using matrix multiplication to calculate the number of tilings of $R$. The algorithm we introduce uses the idea of transforming the problem into a graph problem and then applies the corresponding transition matrix $A_n$ for the calculation. Our way of approach is optimized in the number of multiplications needed to be done, with respect to the non-zero entries of the sparse matrix $A_n$, which is exponentially less than the size of $A_n$. The method we give here improves the idea by Race et al.\ \cite{race}, since we generate the matrix on the fly and thereby substantially reduce the space needed. By running an implementation of our algorithm we have extended the sequence \seqnum{A063443} with 15 new entries. A summary of our results can be found below.
\begin{result}
We present an algorithm for calculating the number of tilings of an $n\times k$ rectangle $R$ via matrix multiplication. The number of operations needed to generate the matrix $A_n$ is linear in the number of non-zero entries in $A_n$ and requires only $O(n)$ space. The space required to perform the actual multiplication is linear in the number of rows of $A_n$.
\end{result}
The paper is organized as follows. In the next section,
we give necessary definitions and formulate the ideas of our method to calculate the number of tilings in detail. Thereafter we present how to generate the adjacency matrix $A_n$ for the matrix multiplication, and then how to perform the actual calculation.
\section{Graphs and matrices}
In order to count the number of ways to tile an $(n+1)\times (k+1)$ rectangle $R$ with square tiles of size $1\times 1$ and $2\times2$, we introduce a binary $k\times n$ matrix, $M_{k,n}$, to represent one such tiling. The ones in $M_{k,n}$ represent the lower left corner of a big tile; see Figure \ref{fig:Tiling}. The zeros represent the small tiles or work as space fillers in the 3 remaining parts of a big tile. We see a row in $M_{k,n}$ as a binary word. Our use of the ones implies that we cannot have two consecutive ones in a row. It suffices to consider the $k\times n$ matrix $M_{k,n}$ instead of a $(k+1)\times(n+1)$ matrix, since the rightmost column and the top row of the latter would just contain zeros.
\begin{figure}[H]
\begin{center}
\begin{tikzpicture}[scale = 1.25]
\draw (0 ,0 ) rectangle (0.5,0.5);
\draw (0.5,0 ) rectangle (1.5,1.0);
\draw (1.5,0 ) rectangle (2.0,0.5);
\draw (0 ,0.5) rectangle (0.5,1.0);
\draw (1.5,0.5) rectangle (2.0,1.0);
\draw (0 ,1.0) rectangle (0.5,1.5);
\draw (0.5,1.0) rectangle (1.0,1.5);
\draw (1.0,1.0) rectangle (2.0,2.0);
\draw (0 ,1.5) rectangle (1.0,2.5);
\draw (1.0,2.0) rectangle (1.5,2.5);
\draw (1.5,2.0) rectangle (2.0,2.5);
\node[anchor=south west] at ( 0 ,0 ) {{\footnotesize\texttt{0}}};
\node[anchor=south west] at ( 0.5,0 ) {{\footnotesize\texttt{1}}};
\node[anchor=south west] at ( 1 ,0 ) {{\footnotesize\texttt{0}}};
\node[anchor=south west] at ( 0 ,0.5) {{\footnotesize\texttt{0}}};
\node[anchor=south west] at ( 0.5,0.5) {{\footnotesize\texttt{0}}};
\node[anchor=south west] at ( 1 ,0.5) {{\footnotesize\texttt{0}}};
\node[anchor=south west] at ( 0 ,1 ) {{\footnotesize\texttt{0}}};
\node[anchor=south west] at ( 0.5,1 ) {{\footnotesize\texttt{0}}};
\node[anchor=south west] at ( 1 ,1 ) {{\footnotesize\texttt{1}}};
\node[anchor=south west] at ( 0 ,1.5) {{\footnotesize\texttt{1}}};
\node[anchor=south west] at ( 0.5,1.5) {{\footnotesize\texttt{0}}};
\node[anchor=south west] at ( 1 ,1.5) {{\footnotesize\texttt{0}}};
\end{tikzpicture}
%
\hspace{2cm}
%
\begin{picture}(100,60)(10,-30)
\put(0,0){
$\displaystyle{M_{4,3} =
\begin{pmatrix}
1 & 0 & 0 \\
0 & 0 & 1 \\
0 & 0 & 0 \\
0 & 1 & 0
\end{pmatrix}}$}
\end{picture}
%
\hspace{2cm}
%
\begin{tikzpicture}
\node (d) at ( 0,2.7) {{\small\texttt{100}}};
\node (c) at ( 0,1.8) {{\small\texttt{001}}};
\node (b) at ( 0,0.9) {{\small\texttt{000}}};
\node (a) at ( 0,0) {{\small\texttt{010}}};
\draw[->] (a) -- (b);
\draw[->] (b) -- (c);
\draw[->] (c) -- (d);
\end{tikzpicture}
\end{center}
\caption{\label{fig:Tiling}A tiling of a $4\times 5$ square and its representation by the $M_{4,3}$ matrix and by a sequence of words of length 3.}
\end{figure}
Further, a row in $M_{k,n}$ is dependent on its neighboring rows. Hence, we may view the rows in $M_{k,n}$ as nodes in a graph $G_n$, where we have an edge between two rows $r_1 = (r_{1,1},r_{1,2},\ldots,r_{1,n})$ and $r_2= (r_{2,1},r_{2,2},\ldots,r_{2,n})$ if and only if $r_1$ can be placed next to $r_2$; see \mbox{Figure \ref{fig:GraphMatrix}} and compare \mbox{Figure \ref{fig:Tiling}}. The row $r_1$ can be placed next to $r_2$ if and only if $r_{2,j}=\mathtt{0}$ for $j\in\{i-1,i,i+1\}\cap\{1,\ldots,n\}$ for all $i$ such that $r_{1,i} = \mathtt{1}$.
\begin{figure}[H]
\begin{center}
\begin{tikzpicture}
\node (a) at ( 0,0) {{\small\texttt{101}}};
\node (b) at ( 2,0) {{\small\texttt{010}}};
\node (c) at ( 0,2) {{\small\texttt{100}}};
\node (d) at ( 2,2) {{\small\texttt{001}}};
\node (e) at ( 1,1) {{\small\texttt{000}}};
\draw[<->] (c) -- (d);
\draw[<->] (e) -- (a);
\draw[<->] (e) -- (b);
\draw[<->] (e) -- (c);
\draw[<->] (e) -- (d);
\draw[<->] (e) to [out=250,in=290, looseness=10] (e);
\end{tikzpicture}
\qquad
\begin{picture}(145,95)(-70,-5)
\put(-65,30){$A_3 = $}
\put( 0,75){\rotatebox{75}{{\footnotesize\texttt{000}}}}
\put(15,75){\rotatebox{75}{{\footnotesize\texttt{001}}}}
\put(30,75){\rotatebox{75}{{\footnotesize\texttt{010}}}}
\put(45,75){\rotatebox{75}{{\footnotesize\texttt{100}}}}
\put(60,75){\rotatebox{75}{{\footnotesize\texttt{101}}}}
\put(-30,60){{\footnotesize\texttt{000}}}
\put(-30,45){{\footnotesize\texttt{001}}}
\put(-30,30){{\footnotesize\texttt{010}}}
\put(-30,15){{\footnotesize\texttt{100}}}
\put(-30, 0){{\footnotesize\texttt{101}}}
\put(-15,30){$\left(\rule{0pt}{40pt}\right.$}
\put( 70,30){$\left.\rule{0pt}{40pt}\right)$}
\put(0,60){1} \put(15,60){1} \put(30,60){1} \put(45,60){1} \put(60,60){1}
\put(0,45){1} \put(15,45){0} \put(30,45){0} \put(45,45){1} \put(60,45){0}
\put(0,30){1} \put(15,30){0} \put(30,30){0} \put(45,30){0} \put(60,30){0}
\put(0,15){1} \put(15,15){1} \put(30,15){0} \put(45,15){0} \put(60,15){0}
\put(0, 0){1} \put(15, 0){0} \put(30, 0){0} \put(45, 0){0} \put(60, 0){0}
\put(-4,-4){\line( 1,0){29}}
\put(-4,-4){\line( 0,1){75}}
\put(-4,71){\line( 1,0){74}}
\put(-4,26){\line( 1,0){45}}
\put(25,-4){\line( 0,1){30}}
\put(41,26){\line( 0,1){45}}
\put(41,41){\line( 1,0){29}}
\put(70,41){\line( 0,1){30}}
\end{picture}
\end{center}
\caption{\label{fig:GraphMatrix}A graph and its corresponding adjacency matrix representing the ways to tile a $4\times n$ rectangle $R$. A path of length $n-1$ in the graph corresponds to a tiling of $R$.}
\end{figure}
Having the graph $G_n$, it is easy to get its corresponding adjacency matrix $A_n$. We index the rows and the columns in $A_n$ with the allowed words (or rows) that can occur in $M_{k,n}$ in lexicographical order. We denote the set of these allowed words by $T_n$, that is,
\[
T_n = \big\{ t\in\{\mathtt{0},\mathtt{1}\}^n : t_i t_{i+1} \neq \mathtt{11} \textnormal{ where } t = t_1\cdots t_n \big\}.
\]
It is easy to see (and a standard exercise to show) that
\begin{equation}
\label{eq:SizeTn}
|T_n| = F_{n+2},
\end{equation}
where $|\cdot|$ denotes the cardinality of a set, and $F_n$ is the $n$th Fibonacci number (that is, $F_n= F_{n-1}+F_{n+2}$ with $F_0=0$ and $F_1=1$; see \seqnum{A000045}). By looking at the structure of the set $T_n$, we see that we can give a recursive definition of the adjacency matrix $A_n$, as previously noted in \cite{calkin, race}. We define
\begin{equation}
\label{eq:RecDefOfAn}
A_n =
\begin{pmatrix}
A_{n-1} & A_{n-2}\\
A_{n-2} & 0\\
\end{pmatrix},
\qquad
A_{0} = \begin{pmatrix} 1 \end{pmatrix},
\quad\textnormal{and}\qquad
A_1 =
\begin{pmatrix}
1 & 1\\
1 & 0
\end{pmatrix},
\end{equation}
where we fill the missing space in $A_n$ with zeros; see again the matrix in Figure \ref{fig:GraphMatrix}. The number of rows in $A_n$ is given by the size of $T_n$, that is,
\begin{equation}
\label{eq:RowsInAn}
\Rows(A_n) = |T_n| = F_{n+2},
\end{equation}
where $\Rows$ gives the number of rows of a square matrix. From the recursion in \eqref{eq:RecDefOfAn}, together with its initial conditions, we have that the number of ones in $A_n$ satisfies the recursion
\[
\Ones(A_{n}) = \Ones(A_{n-1}) + 2 \cdot \Ones(A_{n-2}),
\]
with $\Ones(A_{0}) = 1$ and $\Ones(A_{1}) = 3$, where the function $\Ones$ gives the number of ones in a matrix; see Table \ref{table:Ones}.
\begin{table}[ht]
\centering
\texttt{
\begin{tabular}{|c*{8}{|r}|}
\hline
$n$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ \hline
$\Ones(A_{n})$ &
\phantom{00}3 &
\phantom{00}5 &
\phantom{0}11 &
\phantom{0}21 &
\phantom{0}43 &
\phantom{0}85 &
171 &
341
\\ \hline
\end{tabular}
}
\caption{\label{table:Ones}The number of ones in $A_n$ for small values of $n$. The numbers follow the Jacobsthal sequence; see \seqnum{A001045}.}
\end{table}
It is straightforward to find a closed expression for the number of ones in $A_n$. Standard techniques give
\begin{equation}
\label{eq:NbrOfOnes}
\Ones(A_{n}) = \frac{4}{3}\,2^n - \frac{1}{3}\,(-1)^n,
\end{equation}
for $n\geq 0$. This shows that $A_n$ is a sparse matrix, since its number of entries are $(F_{n+2})^2$, by \eqref{eq:RowsInAn}.
The question of finding the number of tilings of an $n\times k$ rectangle now reduces to making a series of matrix multiplications. If we let $a(n,k)$ be the number of tilings of such a rectangle then
\begin{equation}
\label{eq:NbrTilingsMatrixMul}
a(n,k) = \boldsymbol{1}^T \, A_{n-1}^{k-2} \, \boldsymbol{1},
\end{equation}
where $\boldsymbol{1}$ is a column vector of ones. This formula was also considered by Calkin et al.\ and Race et al.\ \cite{calkin,race}. Note that we have $a(n,k)= a(k,n)$. The number of matrix multiplications can be reduced by noticing the following, which holds since the adjacency matrix $A_n$ is symmetric,
\begin{equation}
\label{eq:MatrixScalarProduct}
\boldsymbol{1}^T \, A_{n}^{\alpha+\beta} \, \boldsymbol{1}
= \boldsymbol{1}^T \, A_{n}^{\alpha} \, \cdot \,A_{n}^{\beta} \, \boldsymbol{1}
= (A_{n}^{\alpha} \,\boldsymbol{1})^T \, (A_{n}^{\beta} \, \boldsymbol{1}).
\end{equation}
For the case when $\alpha + \beta = 2\gamma$ in the above expressions we have $ \boldsymbol{1}^T \, A_{n}^{2\gamma} \, \boldsymbol{1} = |A_{n}^{\gamma} \, \boldsymbol{1}|^2$.
If we perform the matrix multiplications in \eqref{eq:NbrTilingsMatrixMul} with iterations, that is,
\begin{equation}
\label{eq:IteratedMatrixMul}
v_{j+1} = A_{n-1} v_j,
\quad j = 1,\ldots, k-2 \quad \textnormal{with}
\quad v_1 = \boldsymbol{1}
\end{equation}
then the number of multiplications needed to be done is $O(2^nk)$, which is not symmetric in $n$ and $k$. So, making several matrix multiplications with a small matrix is often less costly than few matrix multiplications with a large matrix. On the other hand, if we do the matrix multiplications in \eqref{eq:NbrTilingsMatrixMul} via squaring (\mbox{i.e.} by calculating $A_n^2$, $A_{n}^4$, \ldots) then we need to make $O(\log k)$ matrix multiplications, resulting in $O\big((F_n)^3 \log k\big)$ multiplications. This occurs because the matrix $A_n^2$ is no longer sparse, it contains only non-zero entries. Also, the space needed is substantially larger, as we need to store the matrix $A_n^j$. In this paper we shall apply the method of iterated matrix multiplications.
\begin{example}
\label{ex:ExampleCalculation}
The number of ways to tile a $4 \times 4$ square is given by
\[
a(4,4)=\boldsymbol{1}^T \,A_3 ^2 \, \boldsymbol{1}
= (A_3 \,\boldsymbol{1} )^T \, (A_3 \,\boldsymbol{1} )
= |A_3 \,\boldsymbol{1}|^2
= 35,
\]
and the number of ways to tile a $5 \times 9$ rectangle is given by
\[
a(5,9)
=\boldsymbol{1}^T \,A_4 ^7 \, \boldsymbol{1}
= (A_4^4 \,\boldsymbol{1} )^T \, (A_4^3 \,\boldsymbol{1} )
=a(9,5)
=\boldsymbol{1}^T \,A_8 ^3 \, \boldsymbol{1}
= (A_8^2 \,\boldsymbol{1} )^T \, (A_8 \,\boldsymbol{1} )
= 59925.
\]
The number of multiplications made in the two different ways to find the result in the calculation above is for $a(5,9)$
\[ 4\cdot\Ones(A_4) + \Rows(A_4) = 4\cdot21 + 8 = 92
\]
compared to
\[ 2\cdot\Ones(A_8) + \Rows(A_8) = 2\cdot 341 + 54 = 736,
\]
for $a(9,5)$, clearly in favor of the method using the smaller matrix.
\hfill$\diamond$
\end{example}
\section{Generating the adjacency matrix $A_n$}
In general the matrix $A_n$ is too large to store in the memory of a computer. It is better to generate it dynamically when performing a matrix multiplication. In this section we will show that this way of dealing with $A_n$ can be done in asymptotically optimal time. This means that the time needed to generate $A_n$ is linear in the number of multiplications performed in the matrix multiplication -- or similarly, linear in the number of ones in $A_n$. The space required for this is of order $O(n)$.
\subsection{Binary counters}
To develop a method to generate the adjacency matrix $A_n$, we start by considering \emph{binary counters}. A binary counter is a binary vector $p = p_1 \cdots p_n \in\{\mathtt{0,1}\}^n$ in which we step through all the $2^n$ possible words in lexicographical order by flipping the bits (or entries) in $p$. It is a standard exercise to show that each increment (or to generate the next word) of the counter can be made in amortized constant time; see \cite{cormen}. Recall that amortized constant time means that on average we have to make $O(1)$ operations, for more of this, again see \cite{cormen}.
We give an algorithm (see Figure \ref{algo:Bincounter}) implemented by the function \texttt{Increment\_P}, which given $p\in T_n$ generates the lexicographically next word in $T_n$. We will show that the function \texttt{Increment\_P} makes such an incrementation of $p$ in amortized constant time. An incrementation is made by the function call \texttt{Increment\_P(n,p)}, which changes the bits in $p$ and returns true if a word in $T_n$ has been generated and false when there are no more elements to generate.
{\centering
\begin{figure}[H]
{\footnotesize
\begin{verbatim}
boolean Increment_P(i,p)
{ flip p[i]
if( p[i] == 0 )
{ if( i > 1 )
{ return Increment_P(i-1,p)
}else
{ return false
}
}else
{ if( i > 1 and p[i-1] == 1 )
{ flip p[i]
return Increment_P(i-1,p)
}else
{ return true
}
}
}
\end{verbatim}
}
\caption{\label{algo:Bincounter} The pseudocode for the function \texttt{Increment\_P}
that increments the vector $p$.
A call of the function gives the lexicographically next word of $p$ in $T_n$. It returns true if the next word has been found and false if we have generated all words.}
\end{figure}
}
The idea in the function \texttt{Increment\_P} is to check for the subpattern $\texttt{11}$ or $\texttt{0}$ when flipping bit $i$ in $p$. If one of these subpatterns exists, we have to go deeper in the recursion and flip bits closer to the front of $p$. See Figure \ref{fig:IncOfP} for a walk--through of the case when $p$ is of length three.
\begin{figure}[H]
\begin{center}
\begin{tabular}{*{5}{c}}
\begin{tikzpicture}
\node[rotate=65] at (-0.2,1) {{\tiny\texttt{p[1]}}};
\node[rotate=65] at ( 0.1,1) {{\tiny\texttt{p[2]}}};
\node[rotate=65] at ( 0.4,1) {{\tiny\texttt{p[3]}}};
\node at (-0.8,0.43) {{\small\texttt{p =}}};
\node at ( 0,0.5) {{\small\texttt{0\,\,0\,\,0}}};
\node at ( 0,0 ) {{\small\texttt{0\,\,0\,\,1}}};
\node at ( 0,-2.25) {{\small(a)}};
\draw[->] (0.33,0.35) -- (0.33,0.15);
\end{tikzpicture}
&
\begin{tikzpicture}
\node[rotate=65] at (-0.2,1.5) {{\tiny\texttt{p[1]}}};
\node[rotate=65] at ( 0.1,1.5) {{\tiny\texttt{p[2]}}};
\node[rotate=65] at ( 0.4,1.5) {{\tiny\texttt{p[3]}}};
\node at (-0.8,0.93) {{\small\texttt{p =}}};
\node at ( 0 ,1 ) {{\small\texttt{0\,\,0\,\,1}}};
\node at ( 0 ,0.5) {{\small\texttt{0\,\,0\,\,0}}};
\node at ( 0 ,0 ) {{\small\texttt{0\,\,1\,\,0}}};
\node at ( 0,-1.75) {{\small(b)}};
\draw[->] (0.33,0.85) -- (0.33,0.65);
\draw[->] (0 ,0.35) -- (0 ,0.15);
\end{tikzpicture}
&
\begin{tikzpicture}
\node[rotate=65] at (-0.2,2.5) {{\tiny\texttt{p[1]}}};
\node[rotate=65] at ( 0.1,2.5) {{\tiny\texttt{p[2]}}};
\node[rotate=65] at ( 0.4,2.5) {{\tiny\texttt{p[3]}}};
\node at (-0.8,1.93) {{\small\texttt{p =}}};
\node at ( 0 ,2 ) {{\small\texttt{0\,\,1\,\,0}}};
\node at ( 0 ,1.5) {{\small\texttt{0\,\,1\,\,1}}};
\node at ( 0 ,1 ) {{\small\texttt{0\,\,1\,\,0}}};
\node at ( 0 ,0.5) {{\small\texttt{0\,\,0\,\,0}}};
\node at ( 0 ,0 ) {{\small\texttt{1\,\,0\,\,0}}};
\node at ( 0,-0.75) {{\small(c)}};
\draw[->] (0.33,1.85) -- (0.33,1.65);
\draw[->] (0.33,1.35) -- (0.33,1.15);
\draw[->] (0 ,0.85) -- (0 ,0.65);
\draw[->] (-.33,0.35) -- (-.33,0.15);
\end{tikzpicture}
&
\begin{tikzpicture}
\node[rotate=65] at (-0.2,1) {{\tiny\texttt{p[1]}}};
\node[rotate=65] at ( 0.1,1) {{\tiny\texttt{p[2]}}};
\node[rotate=65] at ( 0.4,1) {{\tiny\texttt{p[3]}}};
\node at (-0.8,0.43) {{\small\texttt{p =}}};
\node at ( 0,0.5) {{\small\texttt{1\,\,0\,\,0}}};
\node at ( 0,0 ) {{\small\texttt{1\,\,0\,\,1}}};
\node at ( 0,-2.25) {{\small(d)}};
\draw[->] (0.33,0.35) -- (0.33,0.15);
\end{tikzpicture}
&
\begin{tikzpicture}
\node[rotate=65] at (-0.2,2.5) {{\tiny\texttt{p[1]}}};
\node[rotate=65] at ( 0.1,2.5) {{\tiny\texttt{p[2]}}};
\node[rotate=65] at ( 0.4,2.5) {{\tiny\texttt{p[3]}}};
\node at (-0.8,1.93) {{\small\texttt{p =}}};
\node at ( 0,2 ) {{\small\texttt{1\,\,0\,\,1}}};
\node at ( 0,1.5) {{\small\texttt{1\,\,0\,\,0}}};
\node at ( 0,1 ) {{\small\texttt{1\,\,1\,\,0}}};
\node at ( 0,0.5) {{\small\texttt{1\,\,0\,\,0}}};
\node at ( 0,0 ) {{\small\texttt{0\,\,0\,\,0}}};
\node at ( 0,-0.75) {{\small(e)}};
\draw[->] (0.33,1.85) -- (0.33,1.65);
\draw[->] (0 ,1.35) -- (0 ,1.15);
\draw[->] (0 ,0.85) -- (0 ,0.65);
\draw[->] (-.33,0.35) -- (-.33,0.15);
\end{tikzpicture}
\end{tabular}
\caption{\label{fig:IncOfP} The function \texttt{Increment\_P} applied to the vector $p$ of length $n=3$. The function is called 5 times, illustrated in (a)--(e), where all but the last time (e) returns true. The arrows indicate how the function flips the bits in $p$. Starting in (a) with $p$ equal to zero, we flip the last bit and return true. In (b) we see that we have to flip bits closer to the front before finding an allowed word. Similar recursive steps happen in (c) and (e).}
\end{center}
\end{figure}
Let us turn to the performance of this increment function. For this, let $f(n)$ denote the total number of flips of bits in $p$ performed by the function \texttt{Increment\_P} when called $F_{n+2}$ times starting form the zero word, that is, during the walk--through of the elements of $T_n$. Similarly, let $f(n,i)$ be the total number of times that the bit $i$ is flipped during these $F_{n+2}$ calls. Then clearly
\[
f(n) = \sum_{i=1}^{n} f(n,i).
\]
In Table \ref{table:FlipsIncrementP} the result of a computer enumeration of $f(n)$ for some small values of $n$ is presented.
\begin{table}[th]
\centering
\texttt{
\begin{tabular}{|c*{8}{|r}|}
\hline
$n$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ \hline
$f(n)$ &
\phantom{00}2 &
\phantom{00}6 &
\phantom{0}12 &
\phantom{0}22 &
\phantom{0}38 &
\phantom{0}64 &
106 &
174 \\ \hline
\end{tabular}
}
\caption{\label{table:FlipsIncrementP} The number of flips performed by \texttt{Increment\_P} when stepping through the words of length $n$ without the pattern $\texttt{11}$.}
\end{table}
\begin{proposition}
\label{prop:NbrFlipsFib}
The number of times that, starting form the zero word, bit $i$ in a binary counter of length $n$ is flipped during $F_{n+2}$ calls of the function \texttt{Increment\_P} is given by
\begin{equation}
\label{eq:NbrFlipsFib}
f(n,i)= 2F_{i+1},
\end{equation}
for $n \geq 1$ and $1\leq i \leq n$.
\end{proposition}
\begin{proof}
We give a proof by induction on $n$. By inspection it is clear that $f(n,i)= 2F_{i+1}$ for $n =1,2$ and $1\leq i \leq n$.
Now assume for induction that \eqref{eq:NbrFlipsFib} holds for $1\leq n \leq k$. For the induction step $n=k+1$, notice first that the function \texttt{Increment\_P} sets all bits back to zero once it has listed all words. This implies that generating the words in $T_{k+1}$ from $\mathtt{00} \cdots {\tt 0}$ to $\mathtt{10} \cdots {\tt 0}$ uses precisely $f(k,i-1)$ flips for bit number $2 \leq i \leq k+1$ and one flip for bit number $1$.
Similarly, to generate all words in $T_{k+1}$ from $\mathtt{100} \cdots {\tt 0}$ to $\mathtt{110} \cdots {\tt 0}$ requires precisely $f(k-1,i-2)$ flips for bit number $3 \leq i \leq k+1$ and one flip for bit number $2$. Thus
\begin{align*}
f(k+1,i)
&= f(k,i-1) + f(k-1,i-2) \\
&= 2F_{i-1+1} + 2F_{i-2+1} \\
&= 2F_{i+1},
\end{align*}
for $3\leq i \leq k+1$. For bit number $2$, we see that we have flipped it two times when listing the words from $\mathtt{00}\cdots{\tt 0}$ to $\mathtt{10} \cdots {\tt 0}$ and then one more time when listing the words from
$\mathtt{100} \cdots {\tt 0}$ to $\mathtt{110} \cdots {\tt 0}$, and then finally one more to set it back to $\mathtt{0}$. We get $f(k+1,2) = 4 = 2F_3$. For bit number $1$ it is clear that it is flipped twice, once when listing the words from $\mathtt{00} \cdots {\tt 0}$ to $\mathtt{10} \cdots {\tt 0}$ and then one more to reset it.
\end{proof}
From Proposition \ref{prop:NbrFlipsFib} we find the total number of flips performed to generate all words in $T_n$ to be given by
\begin{equation}
\label{eq:TotalNbrOfFlips}
f(n) = \sum_{i=1}^{n} 2\,F_{i+1}
= 2\,F_{n+3}-4.
\end{equation}
\begin{corollary}
An incrementation of the binary vector $p$ of length $n$ with a call of the function \texttt{Increment\_P} is made with an amortized constant number of flips.
\end{corollary}
\begin{proof}
From \eqref{eq:SizeTn} and \eqref{eq:TotalNbrOfFlips} we have the bound
\[
\frac{2F_{n+3}-4}{|T_n|}
= \frac{2F_{n+3}-4}{F_{n+2}}
= 2 \frac{F_{n+3}}{F_{n+2}} - \frac{4}{F_{n+2}}
\leq 4,
\]
since $F_{n+1}\leq 2 F_n$, which implies that we on average have to do less than 4 flips for each call of the function \texttt{Increment\_P}.
\end{proof}
The average number of flips to perform in each call of the incrementation function tends to
\[
\lim_{n\to\infty} \frac{2F_{n+3}-4}{|T_n|}
= \lim_{n\to\infty} \frac{2F_{n+3}-4}{F_{n+2}}
= 1+\sqrt{5}
\approx 3.2360\cdots
\]
To conclude, we have shown that the words in $T_n$ can be generated in linear time in the size of $T_n$, that is, in $O\big((\frac{1+\sqrt{5}}{2})^n\big)$ time. The space needed to generate these words is $O(n)$, since we only need to store the vector $p$ of length $n$.
\subsection{Side conditions}
In the previous section, we showed how to efficiently generate all the tuples in a matrix representing a tiling. Applying this method to generate the adjacency matrix $A_n$ would require at least $O\big((\frac{1+\sqrt{5}}{2})^{2n}\big)$ operations. This occurs since, for each row in $A_n$ we have a second binary counter generating the columns, and then check if there should be a one in the corresponding entry of $A_n$. This method is straightforward but has the drawback that it also generates all the entries in $A_n$ that are zero. In this section we show how to overcome this and generate just the entries in $A_n$ that are ones, and thereby reduce the amount of work substantially.
We introduce here a function \texttt{Increment\_PQ}, see \mbox{Figure \ref{fig:IncrementWithSideCondition}}, that increases a binary vector $q$ with the side condition $p\in T_n$. The function generates all the elements $q \in T_n$ that do not have a collision with $p$. A collision with $p$ means that if $p_i = 1$, $1\leq i\leq n$, then $q_{i+j} = 1$ for some $j = -1,0,1$ with $1\leq i+j \leq n$. We also say that words without collisions are allowed. These allowed words correspond to the ones in $A_n$, where we see $p$ as the row index and $q$ as the column index in $A_n$.
The function \texttt{Increment\_PQ} works in the same way as the function \texttt{Increment\_P}, with the extra check for a collision with $p$ when incrementing $q$. If there is a collision, we have to go deeper in the recursion and flip bits closer to the front in $q$. The function returns true if the incrementation was successful, and false if there are no further words to list. Finally, for each word $p\in T_n$, we start with $q = 0$ and call the function repeatedly until false is returned.
{\centering
\begin{figure}
{\footnotesize
\begin{verbatim}
boolean Increment_PQ(i,p,q)
{ n = length(p)
flip q[i]
if( q[i] == 0 )
{ if( i > 1 )
{ return Increment_PQ(i-1,p,q)
}else
{ return false
}
}else
{ if( i > 1 )
{ if( q[i-1] == 1 or p[i-1] == 1 or p[i] == 1 or
(i < n and p[i+1] == 1) )
{ flip q[i]
return Increment_PQ(i-1,p,q)
}else
{ return true
}
}else
{ if( p[i] == 1 or (i < n and p[i+1] == 1) )
{ flip q[i]
return false
}else
{ return true
}
}
}
}
\end{verbatim}
}
\caption{\label{fig:IncrementWithSideCondition}
The pseudocode for the function \texttt{Increment\_PQ} that increments the vector $q$ with the side condition $p$.
It returns true if the next word has been found, and false if we have generated all words.}
\end{figure}
}
Let us turn to the performance of the function \texttt{Increment\_PQ}. For this, let $f_p(n)$ denote the total number of flips made when generating all words $q$ when calling \texttt{Increment\_PQ(n,p,q)} for all $p\in T_n$. That is, the total number of flips performed on $q$ when we generate the matrix $A_n$. Similarly, let $f_p(n,i)$ be the total number of times the bits in $q$ are flipped for the $i$th word $p$ in $T_n$, where we index the words lexicographically. In other words, this is the number of flips made when generating row $i$ in $A_n$. Then clearly
\begin{equation}
\label{eq:sumfpni}
f_p(n) = \sum_{i=1}^{F_{n+2}} f_p(n,i).
\end{equation}
In Table \ref{table:FlipsIncrementPQ} the result of a computer enumeration of $f_p(n)$ for some small values of $n$ is presented.
\begin{table}[ht]
\centering
\texttt{
\begin{tabular}{|c*{8}{|r}|}
\hline
$n$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ \hline
$f_p(n)$ &
\phantom{000}4 &
\phantom{00}14 &
\phantom{00}40 &
\phantom{00}96 &
\phantom{0}222 &
\phantom{0}488 &
1052 &
2222 \\ \hline
\end{tabular}
}
\caption{\label{table:FlipsIncrementPQ} The number of flips performed by \texttt{Increment\_PQ} when stepping through the allowed words $q$ of length $n$ for all words $p\in T_n$.}
\end{table}
\begin{lemma}
The total number of flips on all $q$ performed by \texttt{Increment\_PQ(n,p,q)} when going through all $p\in T_n$ is given by the recursion
\begin{equation}
\label{eq:RecFlipsPerRow}
f_p(n) = f_p(n-1) + 2f_p(n-2) + 8 F_{n} + 2F_{n-1},
\end{equation}
for $n>2$ with $f_p(1) = 4$ and $f_p(2) = 14$.
\end{lemma}
\begin{proof}
The basis conditions are obtained by stepping through the function \texttt{Increment\_PQ}. For $n = 1$ we have $f_p(1) = f_p(1,1) + f_p(1,2) = 2+2 = 4$ and similarly
\begin{align*}
f_p(2)
&= \sum_{i=1}^{F_4} f_p(2,i) = 6+4+4 = 14%\\
\end{align*}
for $n = 2$.
For the recursion \eqref{eq:RecFlipsPerRow} recall the recursive structure of the matrix $A_{n}$, see Figure \ref{fig:GraphMatrix}. Let $p$ be the $i$th word in $T_n$. First let us consider the case when $0 < i \leq F_{n}$. To generate the allowed words $q$ in the interval from $\texttt{00} \cdots {\tt 0}$
to $\texttt{10} \cdots {\tt 0}$
requires $f_p(n-1, i)+1$ flips,
where the plus one comes from flipping the first bit.
To generate the words in the interval $\texttt{10} \cdots {\tt 0}$
to $\texttt{110} \cdots {\tt 0}$ requires $f_p(n-2, i)+1$ flips, and then an additional 2 flips are made for the two first bits. We therefore have
\[ f_p(n, i) = f_p(n-1, i) + f_p(n-2, i) + 4,
\quad\textnormal{for}\quad 0< i \leq F_{n}.
\]
Secondly, for $F_{n}< i \leq F_{n+1}$, again notice that to generate the allowed words $q$ in the interval from $\texttt{00} \cdots {\tt 0}$
to $\texttt{10} \cdots {\tt 0}$ requires $f_p(n-1, i)+1$ flips. Furthermore, in this case $p$ starts with \texttt{01}. This means that after having generated the last allowed word $q$ smaller than $\mathtt{10} \cdots {\tt 0}$ the only extra flip made is on the first bit to reset it. Therefore we have
\[ f_p(n, i) = f_p(n-1, i) + 2,
\quad\textnormal{for}\quad F_{n}< i \leq F_{n+1}.
\]
Third and finally, for $F_{n+1}< i \leq F_{n+2}$ we make $f_q(n-2, i-F_{n+1})+1$ flips to generate the allowed words from $\texttt{00} \cdots {\tt 0}$
to $\texttt{01} \cdots {\tt 0}$.
As above we notice here that $p$ starts with \texttt{10}.
This means that after having generated the last allowed word
$ q < \mathtt{01} \cdots {\tt 0}$,
the only extra flips made are on the first bits. So,
\[ f_p(n, i) = f_p(n-2, i-F_{n+1}) + 4,
\quad\textnormal{for}\quad F_{n+1}< i \leq F_{n+2}.
\]
Summing up the three cases, recalling \eqref{eq:sumfpni}, gives
\begin{align*}
f_p(n)
&= \sum_{i=1}^{F_{n}} \big(f_p(n-1, i) + f_p(n-2, i) + 4\big) \\
&\qquad+ \sum_{i=F_{n}+1}^{F_{n+1}} \big(f_p(n-1, i) + 2\big) \\
&\qquad+ \sum_{i=F_{n+1}+1}^{F_{n+2}} \big(f_p(n-2, i-F_{n+1}) + 4\big) \\
&=f_p(n-1) + 2 f_p(n-2) + 8 F_{n} + 2F_{n-1},
\end{align*}
completing the proof.
\end{proof}
It is straightforward to give an explicit solution to the recursion \eqref{eq:RecFlipsPerRow} with its initial conditions. We find
\[ f_p(n) = \frac{32}{3} 2^n -\frac{2}{3}(-1)^n - 8 F_{n+2} -2 F_{n+1}.
\]
\begin{corollary}
Generating the ones in the adjacency matrix $A_n$ can be made in linear time in the number of ones in $A_n$.
\end{corollary}
\begin{proof}
If we let $f(A_n)$ denote the total number of flips needed to generate $A_n$, then
\begin{align*}
\frac{f(A_n)}{\Ones(A_n)}
&= \frac{f_p(n)+ f(n)}{\Ones(A_n)} \\
&=\frac{\frac{32}{3} 2^n -\frac{2}{3}(-1)^n - 8 F_{n+2} -2 F_{n+1} + 2F_{n+3}-4}
{\frac{4}{3}\,2^n - \frac{1}{3}\,(-1)^n}\\
&=\frac{32 \cdot 2^n -2(-1)^n - 18 F_{n+2}-12}
{4 \cdot 2^n - (-1)^n}\\
&\leq \frac{32 \cdot 2^n - 18 F_{n+2}-10}
{4 \cdot 2^n - 1}\\
&\leq 8,
\end{align*}
where the last inequality follows from
\[ 8 (4 \cdot 2^n - 1) - (32 \cdot 2^n - 18 F_{n+2}-10) = 18 F_{n+2}+ 2 \geq 0.
\qedhere
\]
\end{proof}
To conclude, the space needed to generate $A_n$ is $O(n)$, since we just have to store the vectors $p$ and $q$, and the work needed to do this is linear in the number of ones in $A_n$.
\section{Matrix multiplication}
In the previous section we have seen how to generate the adjacency matrix $A_n$. In this section we describe how to use it efficiently in the matrix multiplication. First we present how to count the number of tilings, without respect to what tiles we use - we turn to that question in the second subsection.
\subsection{Counting}
The rows and columns in $A_n$ are indexed in lexicographical order with the words of $T_n$. To simplify the access into a specific position in $A_n$ we introduce the index function $I_n:T_n\to\mathbb{N}$ by
\begin{equation}
\label{ex:DefIndex}
I_n(t) = 1+\sum_{i=1}^{n} F_{n+2-i}\, t_i,
\end{equation}
for $t\in T_n$ with $t = t_1\cdots t_n$. It is easy to show that $I_n$ indexes the words of $T_n$ in order without gaps. The function $I_n$ is based on the well-known exercise of writing a natural number in the Fibonacci base system.
In the multiplication
\[ u = A_n^k \, \mathbf{1}
\]
the entry $u_i$ is the number of all paths of length $k$ in the graph $G_n$ (representing the tilings) that end in node $N$ with $i = I_n(N)$. By the length of a path we mean the number of visited edges in the path.
Now we have all the parts for the matrix multiplication $A_n$ with a column vector $v^T=(v_1,v_2,\ldots,v_{F_{n+2}})$. The actual matrix multiplications are now performed according to \eqref{eq:IteratedMatrixMul}. The pseudocode for the matrix multiplication $A_n \,v$ is given in \mbox{Figure \ref{fig:MatrixMul}}.
The algorithm for the matrix multiplication works as follows. We initiate a binary counter $row$ and for each increment of it we initiate and step through a second binary counter $column$. We increment $row$ with \texttt{Increment\_P} and $column$ with \texttt{Increment\_PQ} where we have $row$ as the side condition. This corresponds to stepping through the matrix $A_n$ from the upper leftmost position going rightwards to the end of the row before moving to the next row, restarting from the leftmost position, and so on. As the function $\texttt{Increment\_PQ}$ does not go through all the entries on a row, we have to use the index function $I_n$ to find the correct position. At each position, we just have to add the entry $v_i$ to a temporary vector $v_{tmp}$. We do not have to make any multiplications since all non-zero entries of $A_n$ are ones. After stepping through all rows of $A_n$ we return the temporary vector $v_{tmp}$.
\begin{center}
\begin{figure}
{\footnotesize
\begin{verbatim}
vector MatrixMultiplication(n,v)
{ initiate the binary vector 'row' of length n to zero
initiate the vector 'v_tmp' of length F(n+2) with zeros
do
{ initiate the binary vector 'column' of length n to zero
r = I_n(row)
do
{ c = I_n(column)
v_tmp[r] = v_tmp[r] + v[c]
}
while(Increment_PQ(n,row,column))
}
while(Increment_P(n,row))
return v_tmp
}
\end{verbatim}
}
\caption{\label{fig:MatrixMul} The pseudocode for performing the multiplication $A_n v$. The function $I_n$ is the index function from \eqref{ex:DefIndex}. Note that no actual multiplication is performed, as all non-zero entries of $A_n$ are 1.}
\end{figure}
\end{center}
\subsection{Detailed count}
Here we present how to keep track of the number of tilings with a specific number of large tiles.
The multiplication follows the pattern given in the previous section, with only a few changes.
The vector $v$ is modified to be a vector of $(m+1)$-tuples, where $m$ is the maximum number of big tiles in any of the tilings we are going to count.
Next, the initialization of $v$ is made by
\begin{verbatim}
for(t in T_n)
{ v[I_n(t)][Ones(t)] = 1
}
\end{verbatim}
where \textnormal{Ones} gives the number of ones in a word, and all the other entries are set to zero.
Thus, in the multiplication
\[ u = A_n^k \, v,
\]
$u_{ij}$ represents the number of all paths of length $k$ in $G_n$ that end in node $N$, with $i=I_n(N)$, which contain precisely $j$ ones. That is, $j$ is the total number of ones in the nodes along such paths.
In the multiplication we have to take into account the number of ones which are in the word representing the current row in $A_n$, say $o = \textnormal{Ones}(row)$. Now the entry-wise multiplication will just be to add tuple $v_c$ to the tuple $(v_{tmp})_r$, where the latter is shifted $o$ steps to the left. This is to take care of the extra $o$ ones that we get by adding node $row$ to the paths. See the pseudocode in \mbox{Figure \ref{fig:MatrixMulDetail}}.
\begin{center}
\begin{figure}[H]
{\footnotesize
\begin{verbatim}
vector MatrixMultiplicationDetailed(n,m,v)
{ initiate the binary vector 'row' of length n to zero
initiate the array 'v_tmp' of size F(n+2) X m with zeros
do
{ initiate the binary vector 'column' of length n to zero
r = I_n(row)
o = Ones(row)
do
{ c = I_n(column)
for(i=0; o+i] (0,0)--(1,0);
\draw[->] (0,0)--(0,0.4);
\node[above] at (0,0.4) {Nbr of tilings};
\node[below] at (1,-0.05) {Nbr of $2\times2$ squares};
\node[below] at (0.5379,0) {71};
\draw[red, dashed] (0.5379,0)--(0.5379,0.3179);
\node[below] at (0.9167,0) {121};
\draw[red, dashed] (0.9167,0) -- (0.9167,0.1006);
\node[below] at (0,0) {0};
\draw[red, dashed] (0,0.3179)--(0.5379,0.3179);
\node[left] at(0,0.3179) {$3.188\cdot10^{64}$};
\end{tikzpicture}
\caption{\label{fig:EnumGraph}The distribution of the number of tilings of a $23\times23$ square with given number of $2\times2$ squares. The $y$--axis is drawn in a logarithmic scale.}
\end{center}
\end{figure}
\section{Acknowledgment}
The author wishes to thank T. Fernique and A. Ugolnikova at Universit\'e Paris 13 for our
discussions of the problem and for reading drafts of the manuscript.
This work was supported by the ANR project QuasiCool (ANR-12-JS02-011-01).
\begin{thebibliography}{99}
\bibitem{calkin}
N. J. Calkin, K. James, S. Purvis, S. Race, K. Schneider, and M. Yancey,
Counting kings: as easy as $\lambda_1$, $\lambda_2$, $\lambda_3$,\ldots.
\textit{Proceedings of the Thirty-Seventh Southeastern International Conference on Combinatorics, Graph Theory and Computing.}, Congr. Numer. {\bf 183}
(2006), 83--95.
\bibitem{race}
S. Race, K. Schneider, and M. Yancey,
The kings problem. Manuscript available at
\url{http://www4.ncsu.edu/~slrace/gsskings.pdf}.
\bibitem{cormen}
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein,
\emph{Introduction to Algorithms},
3rd ed., MIT Press, 2009.
\bibitem{oeis}
N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Published electronically at \url{http://oeis.org} .
\bibitem{wilf}
H. Wilf,
The problem of the kings,
{\it Electronic J. Combinatorics}
{\bf 2} (1995), \#R3. Available at
\url{http://www.combinatorics.org/ojs/index.php/eljc/article/view/v2i1r3}.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent {\it 2010 Mathematics Subject Classification:}
Primary 68R05; % Combinatorics
Secondary 68Q25. % Analysis of algorithms and problem complexity
\noindent \emph{Keywords:}
tiling,
analysis of algorithms,
combinatorics.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences \seqnum{A001045}, \seqnum{A063443}, \seqnum{A193580} and \seqnum{A245013}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received April 20 2016;
revised version received December 1 2016.
Published in {\it Journal of Integer Sequences}, December 27 2016.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}