\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}