\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

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

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

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

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section] 
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

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

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

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

\usepackage{amssymb}
\usepackage{pstcol,pst-node,graphics}
\newpsobject{showgrid}{psgrid}{subgriddiv=1,griddots=10,gridlabels=6pt}
\usepackage
[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\usepackage{amsthm,amssymb,color,epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\newtheorem{Definition}{Definition}[section]
\newtheorem{Lemma}[Definition]{Lemma}
\newtheorem{Theorem}[Definition]{Theorem}
\newtheorem{Notation}[Definition]{Notation}
\newtheorem{Prop}[Definition]{Proposition}
\newtheorem{Cor}[Definition]{Corollary}


\renewcommand{\baselinestretch}{1.2} 
\renewcommand{\arraystretch}{.7} 

\makeatletter
\def\section{\@startsection {section}{1}{\z@}{-3.5ex plus -1ex minus
 -.2ex}{2.3ex plus .2ex}{\normalsize\bf}}
\makeatother

\def\dominoh{\pspolygon[fillstyle=solid,fillcolor=lightgray](0,0)(1,0)(1,0.5)(0,0.5)}
\def\dominov{\pspolygon[fillstyle=solid,fillcolor=lightgray](0,0)(0,1)(0.5,1)(0.5,0)}
\def\elle{
\psline[linecolor=lightgray](0,0.5)(2,0.5)
\psline[linecolor=lightgray](0.5,0)(0.5,2.5)
\psline[linecolor=lightgray](1,0)(1,1)
\psline[linecolor=lightgray](1.5,0)(1.5,1)
\psline[linecolor=lightgray](0,1)(1,1)
\psline[linecolor=lightgray](0,1.5)(1,1.5)
\psline[linecolor=lightgray](0,2)(1,2)
\pspolygon(0,0)(2,0)(2,1)(1,1)(1,2.5)(0,2.5)}
\def\acca{
\psline[linecolor=lightgray](0,0.5)(3,0.5)
\psline[linecolor=lightgray](0,2.5)(3,2.5)
\psline[linecolor=lightgray](0.5,0)(0.5,3)
\psline[linecolor=lightgray](2.5,0)(2.5,3)
\psline[linecolor=lightgray](1,0)(1,1)\psline[linecolor=lightgray](1,2)(1,3)
\psline[linecolor=lightgray](1.5,0)(1.5,1)\psline[linecolor=lightgray](1.5,2)(1.5,3)
\psline[linecolor=lightgray](2,0)(2,1)\psline[linecolor=lightgray](2,2)(2,3)
\psline[linecolor=lightgray](0,1)(1,1)\psline[linecolor=lightgray](2,1)(3,1)
\psline[linecolor=lightgray](0,1.5)(1,1.5)\psline[linecolor=lightgray](2,1.5)(3,1.5)
\psline[linecolor=lightgray](0,2)(1,2)\psline[linecolor=lightgray](2,2)(3,2)
\pspolygon(0,0)(3,0)(3,3)(0,3)\pspolygon(1,1)(2,1)(2,2)(1,2)}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm
{\LARGE\bf A New Domino Tiling Sequence}
\vskip 1cm
\large Roberto Tauraso \\ 
Dipartimento di Matematica \\
Universit\`a di Roma ``Tor Vergata'' \\
via della Ricerca Scientifica\\
00133 Roma, Italy\\
{ \href{mailto:tauraso@mat.uniroma2.it}{\tt tauraso@mat.uniroma2.it} }
\vskip 1cm
\bf {Abstract}
\end{center}
{\em In this short note, we prove that the sequence \seqnum{A061646} 
from Neil Sloane's Online Encyclopedia of Integer Sequences is connected 
with the number of domino tilings of a holey square.}


\begin{section}{Introduction}
J. Bao discusses in \cite{Bao} the following conjecture due to Edward
Early (see also \cite{Pachter}): the number of tilings of a {\sl holey
square}, that is a $2n\times 2n$ square with a hole of size $2m\times
2m$ removed from the center, is $2^{n-m}\cdot k^2$ where $k$ is an odd
number which depends on $n$ and $m$. The conjecture has been proven for
$m=1,2,\dots, 6$ and numerical experiments indicate that it holds for
several other values of $m$. Here we are going to show that the
conjecture is verified also for $m=n-2$ and, perhaps what is more
surprising, that the corresponding odd numbers $k_n$ give a sequence
already contained in Sloane's Encyclopedia \cite{Sloane}, namely
\seqnum{A061646}.

Before proving this result we supply some definitions and notations.
The Fibonacci numbers \seqnum{A000045} are defined as the sequence of integers 
$$f_0 = 0, f_1 = 1, \mathrm{\ and\ } 
f_{n} = f_{n-1} +f_{n-2} \mathrm{\ for\ all\ } n\geq 2.$$
We will need Cassini's formula, one of the most famous Fibonacci identities: 
\begin{equation}
\label{cassini}
f_{n+1} f_{n-1}-f_{n}^2=(-1)^n\mathrm{\ for\ all\ } n\geq 1.
\end{equation}
The terms of
the sequence \seqnum{A061646} satisfy the recurrence relation given by 
$$a_0 = 1, a_1 = 1, a_2 = 3,\mathrm{\ and\ } 
a_{n} = 2 a_{n-1}+2 a_{n-2} - a_{n-3}  
\mathrm{\ for\ all\ } n\geq 3,$$
and the corresponding generating function is 
$$A(x)=\frac{1-x-x^2}{(1+x)(1-3x+x^2)}.$$
The number $a_n$ can be expressed in terms of the Fibonacci numbers, as
follows:
$$a_{n}=f_{n+1} f_{n-1}+f_{n}^2=2 f_{n}^2 + (-1)^n \mathrm{\ for\ all\ } n\geq 1.$$
The second formula is obtained from the first by using (\ref{cassini})  
and it says that $a_{n}$ is always an odd number.
The first $20$ values of the sequence $a_{n}$ compared
with the Fibonacci numbers are as follows:
\begin{center}
\begin{tabular}{ | r | r | r |}
\hline
$n$ & $f_n$ & $a_n$\\
\hline
0  & 0 & 1 \\
1  & 1 & 1 \\
2  & 1 & 3 \\
3  & 2 & 7 \\
4  & 3 & 19 \\
5  & 5 & 49 \\
6  & 8 & 129 \\
7  & 13 & 337 \\
8  & 21 & 883 \\
9  & 34 & 2311 \\
10 & 55 & 6051 \\
11 & 89 & 15841 \\
12 & 144 & 41473 \\
13 & 233 & 108577 \\
14 & 377 & 284259 \\
15 & 610 & 744199 \\
16 & 987 & 1948339 \\
17 & 1597 & 5100817 \\
18 & 2584 & 13354113 \\
19 & 4181 & 34961521 \\
\hline
\end{tabular}
\end{center}
\end{section}

\begin{section}{The Result}

\begin{Lemma}
For all $n,m\geq 1$ the number of domino tilings of the $L$-grid
\begin{center}
\begin{pspicture}(0,0)(2,3)%\showgrid
\elle
\psline{<->}(0.5,0.5)(2,0.5)
\uput[d](1.25,0.5){$m$}
\psline{<->}(0.5,0.5)(0.5,2.5)
\uput[l](0.55,1.5){$n$}
\end{pspicture}
\end{center}
is 
\begin{equation}
\label{Lformula}
L_{n,m}=f_{n+1} f_{m}+f_{n} f_{m+1}.
\end{equation} 
Moreover, $L_{n,n-1}=a_n$ for all $n\geq 2$ and
\begin{equation}
\label{Lcassini}
L_{n,n-1}^2=L_{n,n}  L_{n-1,n-1} +1.
\end{equation}
\end{Lemma} 

\begin{proof} In order to prove (\ref{Lformula}), we start by covering the lower left corner. We can put there either a horizontal domino or a vertical one and then we can either cut along its smaller side or not.
Then we get the following four different configurations: 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}
\begin{pspicture}(0,-0.5)(13,3)
%\showgrid
\rput(1,1.25){$L_{n,m}=$}
\put(2,0){\elle\dominoh\psline(1,0)(1,1)
\uput[d](1,0){$f_{n+1} f_{m}$}}
\rput(4.5,1.25){$+$}
\put(5,0){\elle\dominoh\put(0.5,0.5){\dominoh}
\uput[d](1,0){$0$}}
\rput(7.5,1.25){$+$}
\put(8,0){\elle\dominov\psline(0,1)(1,1)
\uput[d](1,0){$f_{n} f_{m+1}$}}
\rput(10.5,1.25){$+$}
\put(11,0){\elle\dominov\put(0.5,0.5){\dominov}
\uput[d](1,0){$0$}}
\end{pspicture}
\end{center}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
where the number of domino tilings of each configuration has been calculated
by recalling that the number of ways to tile a $2\times n$ rectangle is equal to $f_{n+1}$.

By (\ref{Lformula}), the identity (\ref{Lcassini}) is equivalent to
$$(f_{n+1} f_{n-1}+f_{n}^2)^2=(2 f_{n+1} f_{n})(2 f_{n-1} f_{n})+1=
4 f_{n+1} f_{n-1} f_{n}^2+1,$$
that is
$$(f_{n+1} f_{n-1}-f_{n}^2)^2=1$$
which holds by Cassini's formula (\ref{cassini}).
\end{proof}

Finally we show that, as expected by the previous conjecture, the number of domino tilings of the considered holey square is the product of $2^2$ by the square of an odd number. This odd number belongs to the sequence \seqnum{A061646}.


\begin{Theorem}
For all $n\geq 3$ the number of domino tilings of the holey square
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}
\begin{pspicture}(0,0)(3,3)%\showgrid
\acca
\psline{<->}(0.5,0.5)(2.5,0.5)
\psline{<->}(0.5,0.5)(0.5,2.5)
\uput[d](1.5,0.5){$n$}
\uput[l](0.55,1.5){$n$}
\end{pspicture}
\end{center}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
is
\begin{equation}
\label{Hformula} 
H_n=4 L_{n,n-1}^2=4 a_n^2.
\end{equation}
\end{Theorem} 

\begin{proof} By symmetry, the tilings which have a horizontal domino 
in the lower left corner are one half of the total number $H_n$:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}
\begin{pspicture}(0,0)(9,3)
%\showgrid
\rput(1.1,1.5){$\frac{1}{2} H_{n}= $}
\put(2,0){\acca\dominoh\psline(1,0)(1,1)}
\rput(5.5,1.5){$+$}
\put(6,0){\acca\dominoh\put(0.5,0.5){\dominoh}}
\end{pspicture}
\end{center}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent The first tiling can be continued by covering the upper right corner in 
these four ways:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}
\begin{pspicture}(1,-0.5)(16,3)
%\showgrid
\put(1,0){\acca\dominoh\psline(1,0)(1,1)\put(2,2.5){\dominoh}\psline(2,2)(2,3)
\uput[d](1.5,0){$L_{n,n-1}^2$}}
\rput(4.5,1.5){$+$}
\put(5,0){\acca\dominoh\psline(1,0)(1,1)\put(2,2.5){\dominoh}\put(1.5,2){\dominoh}
\uput[d](1.5,0){$0$}}
\rput(8.5,1.5){$+$}
\put(9,0){\acca\dominoh\psline(1,0)(1,1)\put(2.5,2){\dominov}\psline(2,2)(3,2)
\uput[d](1.7,0){$L_{n,n} L_{n-1,n-1}$}}
\rput(12.5,1.5){$+$}
\put(13,0){\acca\dominoh\psline(1,0)(1,1)\put(2.5,2){\dominov}\put(2,1.5){\dominov}
\uput[d](1.5,0){$0$}}
\end{pspicture}
\end{center}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent On the other hand the second tiling can be completed in only one way:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\begin{center}
\begin{pspicture}(0,0)(3,3)
%\showgrid
\acca
\dominoh\put(1,0){\dominoh}\put(2,0){\dominoh}
\put(0.5,0.5){\dominoh}\put(1.5,0.5){\dominoh}
\put(1.5,2){\dominoh}\put(0.5,2){\dominoh}
\put(2,2.5){\dominoh}\put(1,2.5){\dominoh}\put(0,2.5){\dominoh}
\put(2,1){\dominov}\put(2.5,0.5){\dominov}\put(2.5,1.5){\dominov}
\put(0,0.5){\dominov}\put(0,1.5){\dominov}
\put(0.5,1){\dominov}
\end{pspicture}
\end{center}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent Therefore
$$\frac{1}{2} H_{n}=L_{n,n-1}^2+L_{n,n} L_{n-1,n-1}+1$$
and by (\ref{Lcassini}) we obtain
$$\frac{1}{2} H_{n}=2 L_{n,n-1}^2=2 a_n^2$$
which gives us (\ref{Hformula}).
\end{proof}
\end{section}


\begin{thebibliography}{99}

\bibitem{Bao}
J. Bao, 
On the number of domino tilings of the rectangular grid, the holey square, and related problems, Final Report, Research Summer Institute at MIT, (1997).

\bibitem{Pachter}
L. Pachter, 
Combinatorial approaches and conjectures for 2-divisibility problems concerning domino tilings of polyominoes, \emph{Electron. J. Comb.}, 
\textbf{4} (1997), 401--410.

\bibitem{Sloane} N. J. A. Sloane,
The On-Line Encyclopedia of Integer Sequences.
Published electronically at \htmladdnormallink{http://www.research.att.com/$\sim
$njas/sequences/}{http://www.research.att.com/~njas/sequences/}.
    
\end{thebibliography}



\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: \ \ Primary 05B45;
Secondary 11B37, 11B39.

\noindent \emph{Keywords:} domino tilings, Fibonacci numbers.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences 
\seqnum{A000045} and \seqnum{A061646}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received March 26 2004;
revised version received  April 19 2004.
Published in {\it Journal of Integer Sequences}, April 27 2004.

\bigskip
\hrule
\bigskip

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


\end{document}