\documentclass[12pt,reqno]{article}

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

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

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

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

\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\usepackage{graphicx}
\usepackage[usenames,dvipsnames]{pstricks}

\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}{\underline{#1}}}

\DeclareMathOperator{\Ones}{Ones}
\DeclareMathOperator{\Rows}{Rows}

\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 
The Number of Domino Matchings in the Game of Memory\\
}
\vskip 1cm
\large
Donovan Young\\
St Albans, Hertfordshire \\
AL1 4SZ \\
United Kingdom\\
\href{mailto:donovan.m.young@gmail.com}{\tt donovan.m.young@gmail.com} \\
\end{center}

\vskip .2 in


\begin{abstract}
When all the elements of the multiset $\{1,1,2,2,3,3,\ldots,n,n\}$ are
placed randomly in the cells of an $m\times k$ rectangular array
(where $mk=2n$), what is the probability $P_{m,k}(p)$ that exactly
$p\in[0,n]$ of the pairs are found with their matching partner
directly beside them in a row or column --- thus forming a $1\times 2$
domino? For the case $p=n$, this reduces to the domino tiling
enumeration problem solved by Kastelyn and which produces the
Fibonacci sequence for the well-known case $m=2$. In this paper we
obtain a formula for the first moment of the probability distribution
for a completely general array, and also give an inclusion-exclusion
formula for the number of 0-domino configurations. In the case of a
$2\times k$ rectangular array, we give a bijection between the
$(k-1)$-domino configurations and the nodes of the Fibonacci tree of
order $k$, thus finding that the number of such configurations is
equal to the path length of the tree; secondly we give generating
functions for the number of $(k-l)$-domino configurations for $l \leq
2$ and conjecture results for $l\leq 5$. These generating functions
are related to convolutions of Fibonacci numbers.
\end{abstract}

\section{Introduction and statement of the problem in terms of
  bipartite perfect matchings}

The game of memory consists of the placement of $n$ distinct pairs of
cards in a rectangular array. For example, we might have two red cards,
two green cards, and two blue cards. The array could then be $2\times
3$ in size; see Figure \ref{fig23color}. \footnote{Though it is not
  important to the work of this paper, the reader unfamiliar with the
  game may be interested in how it is played. The cards are
  placed face down in random order and a turn consists of a player
  turning over two cards of her choice --- should they match they are
  removed from play and she scores a point, otherwise they are turned
  face down again, and the next player takes her turn.} This paper is
concerned with the probability, and hence enumeration, of a pair being
found side-by-side, i.e., adjacent in a column or row of the
rectangular array. We call such nearest-neighbor pairs ``dominoes'',
since we may think of them as fused into a $1\times 2$ tile. We would
like to know the distribution of dominoes, i.e., the probability that
in an $m\times k$ game of memory, $p \in [0,n=mk/2]$ dominoes are
present. We shall denote this quantity $P_{m,k}(p)$.
\begin{figure}[ht]
\begin{center}
\includegraphics[bb=60 25 305 200, height=2in]{23color}
\end{center}
\caption{A $2\times 3$ game of memory showing a 1-domino
  configuration.}
\label{fig23color}
\end{figure}
We begin by noting that the number of possible configurations of the
$n$-pairs is given\footnote{We recall that the double factorial is
  given by $n!! \equiv \prod_{k=0}^{\lceil{n\over2}\rceil-1} (n-2k)$, and we
  define $0!!=(-1)!!=1$.} by $(2n)!/2^n = n!\,(2n-1)!!$, but we will
drop the factor of $n!$ so that we do not count relabelling of the
pairs as distinct configurations. We thus define the number of
distinct configurations $N_{m,k}(p)$ as follows:
\begin{equation}\nonumber\label{defN}
P_{m,k}(p) = \frac{N_{m,k}(p)}{(2n-1)!!}.
\end{equation}
We thus see that $N_{m,k}(n)$ is the number of domino tilings of the
  $m\times k$ rectangular array. Kastelyn \cite{Kast} provided the
celebrated formula
\begin{equation}\nonumber\label{kast}
N_{m,k}(n) = \prod_{i=1}^m \prod_{j=1}^k \left(4\cos^2 \frac{\pi
  i}{m+1}+4\cos^2 \frac{\pi j}{k+1}\right)^{1/4},
\end{equation}
which gives the special case $N_{2,k}(k) = F_{k+1}$, where $F_k$ is the
Fibonacci number $F_0=0$, $F_1=1$, $F_q = F_{q-1}+F_{q-2}$.

The problem of computing $N_{m,k}(p)$ can be stated in terms of the
problem of the rooks, otherwise known as perfect matchings. A
$d$-dimensional hypercubical array (of which a rectangular array is a
special case) may be colored using a checkerboard pattern and hence
the cells form two sets: $B$ consisting of the black cells and $W$
consisting of the white cells. The cells may be considered as vertices
in a bipartite grid-graph $G$ which contains an edge between any two
vertices which connect adjacent cells and no other edges. We also
consider the complement of this graph, which we denote $\bar G$, which
is the complete graph minus the edges of $G$. 
\begin{figure}[ht]
\begin{center}
\includegraphics[bb=85 95 415 327, height=1in]{grid}
\includegraphics[bb=85 95 415 327, height=1in]{notgrid}
\includegraphics[bb=85 95 415 327, height=1in]{notgridd1}
\end{center}
\caption{The graphs $G$, $\bar G$ and $\bar G_B$ for the $2\times 3$
  rectangular array.}
\label{grid}
\end{figure}
Let ${\cal A} = B \cup
W$ be the set of all cells in the array; then the algorithm for
computing $N_{m,k}(p)$ proceeds as follows:\\

\begin{minipage}[c]{0.85\textwidth}
For every distinct subset $B_{n-p}$ containing $n-p$ elements from
$B$

\hspace{0.35cm} For every distinct subset $W_{n-p}$ containing $n-p$
elements from $W$

\hspace{1cm}\parbox[c]{\textwidth}{ Cumulatively sum: the number of
  perfect matchings of $G({\cal A}\setminus(B_{n-p}\cup W_{n-p}))$ multiplied
  by the number of perfect matchings of $\bar G(B_{n-p}\cup
  W_{n-p})$,\\}
\end{minipage}

\noindent where the number of perfect matchings of $G(\emptyset)\equiv
1$, and similarly for $\bar G(\emptyset)$. 

The graph $\bar G$ is not bipartite as it contains the complete graphs
$K(B)$ and $K(W)$, but it will be useful to define its bipartite
subgraph $\bar G_B = \bar G - K(B) - K(W)$, which joins every member
of $B$ with every member of $W$ which is not adjacent to it; see
Figure \ref{grid}. Counting the number of perfect matchings of $\bar
G$ can then be made more efficient by counting the number of
selections of an even (respectively odd) number $k$ of edges from
$\bar G_B$, where the sizes of $B$ and $W$ are even (respectively
odd). This number of selections $r_k$ (which is equivalent to the
number of $k$-edge matchings of $\bar G_B$, or equivalently its rook
number) is then just multiplied by the number of perfect matchings of
$K(B\setminus E_B)$ times the number of perfect matchings of
$K(W\setminus E_W)$, where $E_B$ and $E_W$ are the vertices at the end
points of the selected edges in $\bar G_B$. We thus have that the
number of perfect matchings $n_{PM}(\bar G)$ on $\bar G$ is given
by
\begin{equation}\nonumber\label{gbarpm}
n_{PM}(\bar G) =\begin{cases}
 \sum_{j=0}^{m/2} r_{2j} \left((m-2j-1)!!\right)^2,\quad&\text{$m$ even;}\\
 \sum_{j=0}^{(m-1)/2} r_{2j+1}
 \left((m-2j-2)!!\right)^2,\quad&\text{otherwise,}
\end{cases}
\end{equation}
where $m$ is the size of the set $B$ or $W$.

Computing the rook numbers of a bipartite graph is usually achieved by
considering the associated {\it board}. The board is defined by the
elements of $B$ making-up the columns and those of $W$ the rows. A
black square indicates the existence of an edge joining the associated
black and white vertices. In this light, we give in Figure
\ref{figboards} the boards for the $1\times k$, $2\times k$, etc.\ grid
graphs $G$ (which are the complements of the boards for $\bar G_B$).

\begin{figure}[ht]
\begin{center}
\includegraphics[bb= 0 0 360 360, height=1in]{1k}
\includegraphics[bb= 0 0 360 360, height=1in]{2k}
\includegraphics[bb= 0 0 360 360, height=1in]{3k}
\includegraphics[bb= 0 0 360 360, height=1in]{4k}
\includegraphics[bb= 0 0 360 360, height=1in]{5k}\\
\includegraphics[bb= 0 0 360 360, height=1in]{6k}
\includegraphics[bb= 0 0 360 360, height=1in]{7k}
\includegraphics[bb= 0 0 360 360, height=1in]{8k}
\includegraphics[bb= 0 0 360 360, height=1in]{9k}
\includegraphics[bb= 0 0 360 360, height=1in]{10k}
\end{center}
\caption{The boards for the grid graphs $G$ associated with a $m\times
  k$ array for $m=1,\ldots,10$. Note that $k$ is chosen differently in
  each case. Upon close inspection, the pattern of repetition becomes
  obvious.}
\label{figboards}
\end{figure}

We note that since we have recast the problem of counting the number
of perfect matchings of $\bar G$ in terms of those of $\bar G_B$, we
need only have a match-counting algorithm for dealing with bipartite
graphs (since $G$ is also bipartite), for which the permanent of the
matrix with $0,1$ entries associated with the board corresponding to $G$
or $\bar G_B$ may be used. In Appendix \ref{secapp} we give some
results for rectangular arrays computed in this way.

\section{First moment of the distribution}

In order to compute the first moment of the distribution, we can relax
the constraint that the array ${\cal A}$ be hypercubical\footnote{We
  thank the anonymous referee for suggesting this generalization and
  the method of proof which follows.}. The graph
$G$ can be taken as a general graph whose edges join the cells of
${\cal A}$ which are adjacent. It is clear that $G$ has $2n$ vertices;
let it also have $q$ edges.

\begin{theorem}\label{moment} The mean number of dominoes $\bar p$ for a game of
  memory played on the array ${\cal A}$ is given by
  $$ \bar p = \frac{q}{2n-1}.$$ 
\end{theorem}  

\begin{proof}
The proof proceeds through the linearity of expectation. Let the
random variable $X_j$ take the value $1$ when the $j^{\text{th}}$ edge
in $G$ is occupied by a domino and $0$ otherwise. Once a domino is
placed on edge $j$, there are $(2n-3)!!$ ways of placing the remaining
cards on the $2n-2$ remaining vertices of $G$. Thus $E(X_j) =
(2n-3)!!/(2n-1)!! = 1/(2n-1)$. We therefore have that $E(\sum_{j=1}^q
X_j) = \sum_{j=1}^q E(X_j) = q/(2n-1)$.
\end{proof}
\begin{corollary}
The mean number of dominoes $\bar p$ for a game of memory played on an
array ${\cal A}$ consisting of a $2n$-cell subset of a $d$-dimensional
hypercubical lattice is given by
  $$ \bar p = \frac{2dn - \partial {\cal A}/2}{2n-1},$$ where
$\partial{\cal A}$ indicates the number of $(d-1)$-dimensional outer
faces defining the perimeter of the array ${\cal A}$. For arrays with
multiple disconnected parts, these perimeters are added.
\end{corollary}
\begin{proof}
This corollary is easily verified by noting that the graph $G$ in this
instance has $q=2dn - \partial {\cal A}/2$ edges.
\end{proof}
\begin{figure}[ht]
\begin{center}
\includegraphics[bb=0 0 360 295,height=2in,clip=true]{3d}
\end{center}
\caption{An example of a three-dimensional array with 6 cubes and 28
  faces. A game of memory played on this array has $\bar p = 4/5$.}
\label{fig3d}
\end{figure}
It is interesting to note that for an infinite hypercubical array, the
mean is equal to the dimension. We expect that in the limit of large
arrays, there should be approximate independence among the
dominoes. We then expect
\begin{conjecture}
The probability distribution $P_{\cal A}(p)$, giving the probability
of a $p$-domino configuration in a game of memory played on an array
${\cal A}$, should approach a Poisson distribution with mean given by
Theorem \ref{moment}, when the size of ${\cal A}$ is taken to infinity. 
\end{conjecture}   

\section{Inclusion-exclusion formula for the 0-domino configurations}

If we are only interested in enumerating the 0-domino configurations,
we can restrict our attention to the matching numbers corresponding to
the graph $G$ defining the adjacent cells in the generalized
array\footnote{Hosoya and Motoyama \cite{Hosoya} provide a method for
  generating the rook polynomials for general rectangular arrays.}
${\cal A}$, as defined in Theorem \ref{moment}. Let these numbers be
given by $\rho_j$, i.e., $\rho_j$ counts the number of $j$-edge
matchings of $G$. Then

\begin{theorem}\label{zero}
The number of 0-domino configurations for a game of
  memory played on the array ${\cal A}$ is given by
$$N_{\cal A}(0)=
\sum_{j=0}^{n} (-1)^j(2n-2j-1)!! \,\rho_j.$$
\end{theorem}

\begin{proof}
We note that for each of the $\rho_j$ choices of $j$ edges on which to
place $j$ dominoes, there remains $(2n-2j-1)!!$ configurations of the
remaining $n-j$ pairs. There will be some number of $q$-domino
configurations among these $(2n-2j-1)!!$. Then $(2n-2j-1)!!\,\rho_j$
counts the $(q+j)$-domino configurations ${q+j\choose j}$ times. We
thus have
$$\sum_{j=0}^{n} (-1)^j(2n-2j-1)!! \,\rho_j
=\sum_{j=0}^{n} (-1)^j
\sum_{q=0}^{n-j} {q+j\choose j} N_{\cal A}(q+j)$$
$$=N_{\cal A}(0) + \sum_{q+j=1}^n N_{\cal A}(q+j) \sum_{j=0}^{q+j} (-1)^j 
{q+j\choose j},$$
and so all but the 0-domino configurations cancel.
\end{proof}
 
One could indeed extend this technique to computing the number of
$p$-domino configurations, by replacing $\rho_j$ with the sum of the
matching numbers of the graphs obtained by removing $p$ edges from $G$ in
all possible ways. We will use this technique in the next section to
compute $N_{2,k}(1)$.

\section{$2\times k$ arrays: specific results}

Kreweras and Poupard \cite{KP} explicitly solved the $1\times k$ problem;
see \seqnum{A079267}. The expression for $N_{1,k}(p)$ is ($k$ must of
course be even)
\begin{equation}\nonumber
N_{1,k}(p) = \frac{1}{p!} \sum_{j=p}^{k/2} (-1)^{j-p} 
\frac{(k-j)!}{2^{k/2-j}(k/2-j)!(j-p)!}.
\end{equation}
The case of $2\times k$ is considerably more involved. 
\begin{figure}[t]
\begin{center}
\includegraphics[bb= 0 0 360 360, height=2in]{2k}
\end{center}
\caption{The board for the grid graph $G$ associated with a $2\times 10$ array.}
\label{fig2k}
\end{figure}
Riordan \cite[p.\ 230]{JR,JR1} (McQuistan and Lichtman
\cite{ML} give connections to dimer models in Physics) provided the
rook polynomial for the grid graph $G$ associated with the $2\times k$
board; see Figure \ref{fig2k}. The generating function
\begin{equation}\label{riordan}
T(x,y) = \frac{1-xy}{1-y-2xy-xy^2+x^3y^3} = \sum_{k=0}^\infty T_k(x) y^k 
\end{equation}
gives the rook polynomials $T_k(x)$
\begin{equation}\nonumber
T_k(x) = \sum_{j=0}^k \rho_j(k) \,x^j,
\end{equation}
where $\rho_j(k)$ are the rook numbers which count the number of
$j$-edge matchings of $G$; see \seqnum{A046741}. We may compute the
rook numbers $r_j(k)$ for $\bar G_B$ (i.e., for the complement board)
using
\begin{equation}\nonumber\label{comprook}
r_j(k) = \sum_{i=0}^j (-1)^i (j-i)! 
{k-i\choose j-i}^2
\rho_i(k).
\end{equation}

Application of Theorem \ref{zero} to Eqn.~(\ref{riordan}) gives the
sequence of the number of 0-domino configurations for the $2\times k$
arrays readily. We find sequence \seqnum{A265167}:
$$N_{2,k}(0) =
0,1,2,21,186,2113,27856,422481,7241480,138478561,\ldots, $$ for $k$
starting from 1. 

We remarked beneath Theorem \ref{zero} that the $1$-domino
configurations can be calculated using this theorem with the $\rho_j$
replaced by the sum of the rook numbers of the graphs produced by
removing an edge (i.e., deleting the corresponding row and column)
from the board in Figure \ref{fig2k} in all possible ways. The rules
of rook polynomials may be used to calculate the generating function
for this sum of rook numbers. When the removed edge is on the main
diagonal, the resulting rook polynomial factorizes producing
\begin{equation}\label{di}
\text{contribution from diagonal}=
\sum_{m=0}^{k-1}T_m(x)\, T_{k-m-1}(x).
\end{equation}
A board's rook polynomial is equal to that of itself with a given cell
removed (i.e., flipped from black to white) plus $x$ multiplied by the
rook polynomial corresponding to the board with the row and column
containing that cell removed. This rule can be used to compute the
contribution from removing edges on the next-to-diagonals. We find
\begin{align}\nonumber
&\text{contribution from next-to-diagonals}=\\\nonumber
&\qquad 2 \sum_{m=0}^{k-2}\Biggl(
x\, T_m(x)\,T_{k-m-2}(x) \\\label{ndi}
&\qquad\quad+\Bigl(s_m(x)-x\,s_{m-1}(x)\Bigr)
\Bigl(s_{k-m-2}(x) - x\, s_{k-m-3}(x)\Bigr)\Biggr),
\end{align}
where $s_n(x)$ corresponds to the rook polynomial of the board
pictured in Figure \ref{figs}, with $s_{-1}(x)\equiv 0$.
\begin{figure}[t]
\begin{center}
\psscalebox{1.2 1.2} 
{
\begin{pspicture}(0,-1.42)(3.18,1.42)
\psline[linecolor=black, linewidth=0.04](0.02,1.4)(0.02,0.2)
\psline[linecolor=black,
  linewidth=0.04](0.02,0.2)(0.42,0.2)(0.42,-0.2)(0.82,-0.2)(0.82,-0.6)(1.22,-0.6)(1.22,-1.0)(1.62,-1.0)(1.62,-1.4)(2.02,-1.4)(2.02,-0.2)(1.62,-0.2)(1.62,0.2)(1.22,0.2)(1.22,0.6)(0.82,0.6)(0.82,1.0)(0.42,1.0)(0.42,1.4)(0.02,1.4)
\psline[linecolor=black, linewidth=0.04](2.62,1.4)(2.42,1.4)
\psline[linecolor=black, linewidth=0.04](2.42,-1.4)(2.62,-1.4)
\psline[linecolor=black, linewidth=0.04](2.62,1.4)(2.82,1.4)
\psline[linecolor=black, linewidth=0.04](2.62,-1.4)(2.82,-1.4)
\psline[linecolor=black, linewidth=0.04](2.62,1.4)(2.42,1.1333333)
\psline[linecolor=black, linewidth=0.04](2.62,1.4)(2.82,1.1333333)
\psline[linecolor=black, linewidth=0.04](2.62,-1.4)(2.42,-1.2)
\psline[linecolor=black, linewidth=0.04](2.62,-1.4)(2.82,-1.2)
\psline[linecolor=black, linewidth=0.04](2.62,1.4)(2.62,0.2)
\psline[linecolor=black, linewidth=0.04](2.62,-1.4)(2.62,-0.6)
\rput[bl](2.32,-0.32){$n+2$}
\end{pspicture}
}
\end{center}
\caption{The board corresponding to the rook polynomial $s_n(x)$. For
  convenience we have indicated the black cells in outline.}
\label{figs}
\end{figure}
It is given by \cite[p.\ 230]{JR,JR1}
\begin{equation}\nonumber\label{sxy}
s(x,y) = \sum_{j=0}^\infty s_j(x)\,y^j = \frac{T(x,y)}{(1 - xy)^2}.
\end{equation}
We can easily convert Eqns.~(\ref{di}) and (\ref{ndi}) into
generating functions similar to Eqn.~(\ref{riordan}); summing the
contributions we find $$\tilde T(x,y) =
\left(1+2xy+\frac{2y}{(1-xy)^2}\right)T^2(x,y).$$ Thus the
corresponding rook numbers $\tilde\rho_j(k)$ (given in
\seqnum{A318243}) produced by the expansion
$$\tilde T(x,y) =\sum_{k=0}^\infty\tilde T_k(x)\,y^k
= \sum_{k=0}^\infty y^k\sum_{j=0}^k \tilde \rho_j(k)\,x^j$$
may be used in Theorem \ref{zero} in place of the $\rho_j$ to compute
the number of $1$-domino configurations for the $(2\times k)$
array. We find \seqnum{A318244}
$$
N_{2,k}(1) = 1, 0, 8, 34, 347, 3666, 47484, 707480, 11971341, 226599568,\ldots
$$

We now turn our attention to the case of many dominoes. The result for
the maximal number $n=k$ is given by the Fibonacci number $N_{2,k}(k)
= F_{k+1}$ as is very well known. The case of $(k-1)$ dominoes will be
dealt with in the next section.

\subsection{The $(k-1)$-domino configurations and the Fibonacci tree}

The Fibonacci tree is defined as follows. The trees of order 1 and 2
consist of single nodes labeled by $F_0 = 0$ and $F_1 = 1$. To build
the tree of order $k$, we use the tree of order $k-1$ as the left
subtree and that of order $k-2$ as the right subtree. In Figure
\ref{figtree} we have reproduced the trees of order 3, 4, and 5. The
level of the nodes is defined as usual, with the root node being
assigned the level 0. The path length of the tree is then defined as
the sum of the level numbers of all nodes.

\begin{theorem}\label{kminus1}
The number of $(k-1)$-domino configurations for a game of memory
played on the $2\times k$ rectangular array is given by the path
length of the Fibonacci tree of order $k$ (see \seqnum{A178523}).
\end{theorem}

\begin{proof}
We count $N_{2,k}(k-1)$ by considering the insertion of a block
containing the two cells (i.e., $1\times1$ squares) which do not form a
domino\footnote{For odd $p$ one of these squares will be on the top
  row and one on the bottom, whereas for even $p$ they will be located
  on the same row.}; see Figure \ref{figft}. The number of domino
tilings of the blocks on either side are given by the Fibonacci
numbers $F_{k-m+1}$ and $F_{m-p+1}$. Accounting for the two possible
orientations of the central block, we have $$N_{2,k}(k-1) =
2\sum_{p=3}^k \sum_{m=p}^k F_{k-m+1}F_{m-p+1}.$$ Translating this into
a generating function one finds $$\sum_{k=1}^\infty x^k\, N_{2,k}(k-1)
= \frac{2x^3}{(1-x)(1-x-x^2)^2},$$ which is the desired result.
\end{proof}

\begin{figure}[ht]
\begin{center}
\psscalebox{0.8 0.8}
{
\begin{pspicture}(0,-1.4070716)(13.600009,1.4070716)
\psframe[linecolor=black, linewidth=0.04,
  dimen=outer](3.2,1.4070716)(0.0,-0.19292846)
\rput[bl](1.,0.4070715){\Large $k-m$} \psframe[linecolor=black,
  linewidth=0.04, dimen=outer](4.0,0.6070715)(3.2,-0.19292846)
\psframe[linecolor=black, linewidth=0.04,
  dimen=outer](4.8,1.4070716)(3.2,0.6070715) \psframe[linecolor=black,
  linewidth=0.04, dimen=outer](5.6,0.6070715)(4.0,-0.19292846)
\rput{-180.0}(24.000017,1.2140244){\psframe[linecolor=black,
    linewidth=0.04,
    dimen=outer](13.600008,1.4070122)(10.400008,-0.19298781)}
\rput{-180.0}(19.999275,2.0103118){\psframe[linecolor=black,
    linewidth=0.04,
    dimen=outer](10.399638,1.4051559)(9.599638,0.6051559)}
\rput{-180.0}(19.20076,0.40956998){\psframe[linecolor=black,
    linewidth=0.04,
    dimen=outer](10.40038,0.60478497)(8.800381,-0.19521502)}
\rput{-180.0}(17.599277,2.0080843){\psframe[linecolor=black,
    linewidth=0.04,
    dimen=outer](9.599638,1.4040421)(7.999638,0.6040422)}
\rput{0.254808}(0.0028251004,-0.051581778){\rput[bl](11.1,0.4094563){\Large
    $m-p$}} \psdots[linecolor=black, dotsize=0.3](6.0,0.6070715)
\psdots[linecolor=black, dotsize=0.3](6.8,0.6070715)
\rput{-0.16728105}(-0.0017638823,0.022191623){\psdots[linecolor=black,
    dotsize=0.3](7.600012,0.6152464)} \psline[linecolor=black,
  linewidth=0.04](3.2,-0.99292845)(5.65,-0.99292845)(6.0,-0.99292845)(6.0,-0.99292845)(6.0,-0.99292845)(6.0,-0.99292845)(6.0,-0.99292845)(6.0,-0.99292845)(6.0,-0.99292845)(6.0,-0.99292845)(6.0,-0.99292845)(6.0,-0.99292845)
\psline[linecolor=black,
  linewidth=0.04](7.6,-0.99292845)(10.4,-0.99292845)(10.4,-0.99292845)(10.4,-0.99292845)(10.4,-0.99292845)(10.4,-0.99292845)(10.4,-0.99292845)(10.4,-0.99292845)(10.4,-0.99292845)(10.4,-0.99292845)(10.4,-0.99292845)(10.4,-0.99292845)
\rput[bl](6.7,-1.299292845){\Large $p$} \psline[linecolor=black,
  linewidth=0.04](3.2,-0.59292847)(3.2,-0.99292845)
\psline[linecolor=black,
  linewidth=0.04](10.4,-0.59292847)(10.4,-0.99292845)
\psline[linecolor=black,
  linewidth=0.04](3.2,-0.99292845)(3.6,-0.59292847)
\psline[linecolor=black,
  linewidth=0.04](3.2,-0.99292845)(3.6,-1.3929285)
\psline[linecolor=black,
  linewidth=0.04](10.4,-0.99292845)(10.0,-0.59292847)
\psline[linecolor=black,
  linewidth=0.04](10.4,-0.99292845)(10.0,-1.3929285)
\psline[linecolor=black,
  linewidth=0.04](3.2,-0.99292845)(3.2,-0.99292845)
\psline[linecolor=black,
  linewidth=0.04](3.2,-1.3929285)(3.2,-0.99292845)
\psline[linecolor=black,
  linewidth=0.04](10.4,-1.3929285)(10.4,-0.99292845)
\end{pspicture}
}
\end{center}
\caption{The $2\times k$ array is broken into three blocks. The
  position of the central unbreakable block is parametrized by $m$ while its
  length is given by $p\geq 3$.}
\label{figft}
\end{figure}

A bijection between the nodes of the Fibonacci tree of order $k$ and
the $(k-1)$-domino configurations is achieved as follows. We
associate the number of places where a configuration can be
broken\footnote{We define breakability by the existence of a
  continuous vertical line consisting of edges of dominoes or
  squares. Any configuration can be broken into some number of
  unbreakable blocks.} with one less than the level of the tree. At
level 1 of the tree, we therefore have the unique two configurations
which cannot be broken, i.e., the central blocks from Figure
\ref{figft}. At each node of the tree at level $q$, we will place $q$
configurations which are the cyclic permutations of the $q$ blocks
which the configuration can be broken into. In this way the level
number serves as an overall multiplicity for the configurations on the
nodes of a given level, and we will label each node with only one
representative; see Figure \ref{figtree}. At the bottom two nodes of
any tree, the unique configurations correspond to the two shortest
blocks containing the two squares, supplemented by a number of
vertical dominoes; these are the configurations which can be broken
in the maximum number of places.

\begin{figure}[ht]
\begin{center}
\includegraphics[bb= 0 40 547 616, height=4in]{fibtree}
\end{center}
\caption{The bijection between the Fibonacci tree of order $k$ and the
  $(k-1)$-domino configurations. The configuration at each node
  represents all cyclic permutations of the blocks which that
  configuration can be broken into.}
\label{figtree}
\end{figure}

The number of nodes $T_{k,q}$ at level $q$ of the tree of order $k$
obeys the recursion relation $T_{k,q} = T_{k-1,q-1} + T_{k-2,q-1}$. To
this recursion relation, we wish to associate a rule which generates
the $(k-1)$-domino configurations (for a $2\times k$ array) at level
$q$ (i.e., breakable in $q-1$ places) from those corresponding to a
$2\times (k-1)$ and $2\times(k-2)$ array at level $q-1$. This rule
proceeds as follows, working from left to right across the
$(q-1)^\text{th}$ level of the trees of order $k-1$ and $k-2$
\begin{enumerate}
\item Add a single vertical
domino to the end of each representative configuration found at the
nodes of level $q-1$ in the tree of order $k-1$. Place these new
configurations on the nodes of level $q$ of the tree of order $k$,
working left to right.     
\item Add a square consisting of two horizontal dominoes to the end of
  each representative configuration found at the nodes of level $q-1$
  in the tree of order $k-2$. Fill the remaining nodes of level $q$
  of the tree of order $k$ with these configurations, working left to right.     
\end{enumerate}

There have been several papers relating to the tiling of $2\times k$
arrays with $1\times 2$ dominoes and $1\times 1$ squares. Examples
include Katz and Stenson \cite{KS} and more recently Kahkeshani
\cite{Kahk}. It should be noted that the enumeration problem
considered here is of a different character, due to the restricted
positions of our $1\times 1$ squares.

\subsection{Generating functions for the number of $(k-l)$-domino configurations} 
 
We conclude with some empirical observations on the generating
functions for $N_{2,k}(k-l)$. The cases of $l=0$ and $l=1$ are as
follows:
\begin{align}\nonumber
&{\cal F}_0 \equiv \sum_{k=0}^\infty x^k\, N_{2,k}(k) =
\frac{1}{1-x-x^2},\\\nonumber
&{\cal F}_{1} \equiv \sum_{k=1}^\infty x^k\, N_{2,k}(k-1) =
\frac{2x^3}{(1-x)(1-x-x^2)^2},
\end{align}
where we have quoted the generating functions for the Fibonacci
numbers and the path length of the Fibonacci tree of order $k$. We
have computed the case of $l=2$ explicitly using the calculus of the
rook polynomial. This computation is tedious and too lengthy to be
included in this paper. The result is
\begin{equation}\nonumber
{\cal F}_{2} \equiv \sum_{k=2}^\infty x^k\, N_{2,k}(k-2) =
\frac{x^2\left(1 + 3 x + 6 x^2 + x^3  + 3 x^4\right)}{(1-x)^2(1-x-x^2)^3}.
\end{equation}
These results are suggestive of a pattern and lead us to
\begin{conjecture} The generating function for the number
  $N_{2,k}(k-l)$ of $(k-l)$-domino configurations in the $2\times k$
  rectangular array is given by 
\begin{equation}\nonumber
{\cal F}_{l}(x) \equiv \sum_{k=l}^\infty x^k\, N_{2,k}(k-l)
= \frac{x^2 Q_l(x)}{(1-x)^l(1-x-x^2)^{l+1}},
\end{equation}
where
\begin{equation}\nonumber
Q_l(x) = (l+1) \,x^{3l-2} + c_{l,1} \,x^{3l-3}+c_{l,2}\,x^{3l-4}+ \ldots + c_{l,2l}\,x^{l-2},
\end{equation}
and the $c_{l,j}$ are zero for $l \leq 1$. 
\end{conjecture}
Using the data in Appendix \ref{secapp}, we have been able to fix
these coefficients for the cases $l=3,4,5$ and to verify that
several subsequent terms are correctly reproduced. We find
\begin{align}\nonumber
&Q_1(x) = 2x,\\\nonumber
&Q_2(x) = 1 + 3 x + 6 x^2 + x^3  + 3 x^4,\\\nonumber
&Q_3(x) = 2 x + 20 x^2 + 46 x^3 + 40 x^4 + 30 x^5 + 4 x^6 + 4 x^7,\\\nonumber
&Q_4(x) = 21 x^2 + 158 x^3 + 447 x^4 + 612 x^5 + 502 x^6 + 230 x^7 + 93 x^8 + 
 10 x^9 + 5 x^{10},\\\nonumber
&Q_5(x) = 186 x^3 + 1620 x^4 + 5502 x^5 + 9636 x^6 + 10020 x^7 + 6612 x^8 + 
 3012 x^9\\\nonumber
&\qquad\qquad + 888 x^{10} + 228 x^{11} + 20 x^{12} + 6 x^{13}.
\end{align}
We remark that the denominators of the generating functions contain the
term $(1-x-x^2)^{l+1}$ which corresponds to a convolution of $l+1$
Fibonacci sequences. One recognizes of course that $c_{l,2l} =
N_{2,l}(0)$. The sequences $N_{2,k}(k-l)$ for $l=2,\dots,5$ appear as
\seqnum{A318267} to \seqnum{A318270} respectively.

\section{Acknowledgments}

I would like to thank Peter Cameron from Queen Mary University London
and the other members of the combinatorics group for inviting me to
present an earlier version of this work to their seminar in March
2014. I also thank the anonymous referee for several helpful comments,
insights, and encouragement. I thank EPR for many enjoyable games of memory.

\appendix
\section{A selection of $N_{m,k}(p)$ for rectangular two-dimensional arrays}
\label{secapp}
Some results for various rectangular two-dimensional arrays, given as 
$$N_{m,k}(0),\,N_{m,k}(1),\,\ldots,\, N_{m,k}(mk/2)$$
follow below.

\begin{align}\nonumber
&N_{2,1}(p) = 0,1\\\nonumber
&N_{2,2}(p) = 1,0,2\\\nonumber
&N_{2,3}(p) = 2,8,2,3\\\nonumber
&N_{2,4}(p) = 21,34,39,6,5\\\nonumber
&N_{2,5}(p) = 186,347, 250, 138, 16, 8\\\nonumber
&N_{2,6}(p) = 2113, 3666, 2919, 1234, 414, 36, 13\\\nonumber
&N_{2,7}(p) = 27856, 47484, 36714, 17050, 4830, 1104, 76, 21\\\nonumber
&N_{2,8}(p) = 422481, 707480, 545788, 253386, 78815, 16174, 2715, 152, 34\\\nonumber
&N_{2,9}(p) = 7241480, 11971341, 9195198, 4317996, 1369260, 309075,
48444, 6282, 294, 55\\\nonumber
&N_{2,10}(p) = 138478561, 226599568, 173545854, 82061730, 26613111,
6209700, 1072617,\\\nonumber&\qquad\qquad\quad 133416, 13875, 554, 89
\end{align}
\begin{align}\nonumber 
&N_{3,4}(p) = 1829, 3585, 3066, 1391, 456, 57, 11\\\nonumber 
&N_{3,6}(p) = 6228153, 11485628, 9687119, 4919411, 1668149,
396032, 66332, 8021, 539, 41
\end{align}
\begin{align}\nonumber
&N_{4,4}(p) = 353064, 675936, 580296, 294024, 98115, 21696, 3594,
264, 36\\\nonumber
&N_{4,5}(p) = 113819277, 213825535, 184772883, 97119606, 34570179,
8761683, 1620885,\\\nonumber&\qquad\qquad\quad 215952, 21819, 1161, 95
\end{align}


\begin{thebibliography}{99}

\bibitem{Kast} P.W. Kasteleyn, The statistics of dimers on a lattice:
  I. The number of dimer arrangements on a quadratic lattice, {\it
    Physica} {\bf 27} (1961), 1209--1225.

\bibitem{KP} G. Kreweras and Y. Poupard, Sur les partitions en paires
  d'un ensemble fini totalement ordonne, {\it Publications de
    l'Institut de Statistique de l'Universit\'{e} de Paris} {\bf 23}
  (1978), 57--74.

\bibitem{JR} J. Riordan, The enumeration of permutations with
  three-ply staircase restrictions, unpublished memorandum, 1963.
  Available at \url{https://oeis.org/A001883/a001883_21.pdf}.

\bibitem{JR1} J. Riordan, {\it An Introduction to Combinatorial
  Analysis}, Wiley, 1958.

\bibitem{ML} R. B. McQuistan and S. J. Lichtman, Exact recursion
  relation for $2\times N$ arrays of dumb-bells, {\it J. Math Phys.}
  {\bf 11} (1970), 3095--3099.

\bibitem{Hosoya} H. Hosoya and A. Motoyama, An effective algorithm for
  obtaining polynomials for dimer statistics. Application of operator
  technique on the topological index to two‐ and three‐dimensional
  rectangular and torus lattices, {\it J. Math. Phys.} {\bf 26}
  (1985), 157--167.

\bibitem{KS} M. Katz and C. Stenson, Tiling of a $(2\times n)$-board
  with squares and dominoes, {\it J. Integer Sequences} {\bf 12} (2009),
  \href{https://cs.uwaterloo.ca/journals/JIS/VOL12/Stenson/stenson8.html}{ Article 09.2.2}.

\bibitem{Kahk} R. Kahkeshani, The tilings of a $(2\times n)$-board and
  some new combinatorial identities, {\it J. Integer Sequences} {\bf 20}
  (2017), \href{https://cs.uwaterloo.ca/journals/JIS/VOL20/Kahkeshani/kahk3.html}{Article 17.5.4}.

\end{thebibliography}



\bigskip
\hrule
\bigskip

\noindent {\it 2010 Mathematics Subject Classification:} 
Primary 05A15; 
Secondary 05C70, 60C05. 

\noindent \emph{Keywords:} 
Fibonacci number, Fibonacci tree, domino
  tiling, perfect matching.
\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences  
\seqnum{A000045},
\seqnum{A001883},
\seqnum{A046741},
\seqnum{A079267},
\seqnum{A178523},
\seqnum{A265167},
\seqnum{A318243},
\seqnum{A318244},
\seqnum{A318267},
\seqnum{A318268},
\seqnum{A318269}, and
\seqnum{A318270}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received August 2 2018;
revised version received  August 24 2018.
Published in {\it Journal of Integer Sequences}, September 30 2018.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                

                                                                                


.