\documentclass[12pt,reqno]{article}

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

\usepackage[usenames,dvipsnames]{pstricks}
\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{mathtools}

\DeclareMathOperator{\Ones}{Ones}
\DeclareMathOperator{\Rows}{Rows}
\DeclareMathOperator{\erfi}{Erfi}

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

\begin{document}

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

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
Generating Functions for Domino Matchings in the $2\times k$ 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,k,k\}$ are
placed in the cells of a $2\times k$ rectangular array, in how many
configurations are exactly $v$ of the pairs directly over top one
another, and exactly $h$ directly beside one another --- thus forming
$1\times 2$ or $2\times 1$ dominoes? We consider the sum of matching numbers over the
graphs obtained by deleting $h$ horizontal and $v$ vertical vertex
pairs from the $2\times k$ grid graph in all possible ways, providing
a generating function for these aggregate matching polynomials. We use
this result to derive a formal generating function enumerating the
domino matchings, making connections with linear chord diagrams.
\end{abstract}

\section{Introduction}

The game of memory consists of the placement of a set of distinct
pairs of cards in a rectangular array. The present author \cite{DY}
considered the enumeration of the configurations in which exactly $p$
of the pairs are placed directly beside, or over top of one another,
thus forming $1\times 2$ or $2\times 1$ dominoes. In this paper we
consider the case of $2\times k$ arrays in more detail. In Figure
\ref{fourways} we show a configuration of the case $k=4$ with $h=1$
horizontal dominoes, and $v=1$ vertical dominoes.
\begin{figure}[h]
\begin{center}
\psscalebox{0.75 0.75} 
{
\begin{pspicture}(0,-1.6)(18.088701,1.6)
\definecolor{colour0}{rgb}{0.6039216,0.6039216,0.6039216}
\psframe[linecolor=black, linewidth=0.04, dimen=outer](0.8,0.8)(0.0,0.0)
\psframe[linecolor=black, linewidth=0.04, dimen=outer](0.8,0.0)(0.0,-0.8)
\psframe[linecolor=black, linewidth=0.04, dimen=outer](1.6,0.8)(0.8,0.0)
\psframe[linecolor=black, linewidth=0.04, dimen=outer](1.6,0.0)(0.8,-0.8)
\psframe[linecolor=black, linewidth=0.04, dimen=outer](2.4,0.8)(1.6,0.0)
\psframe[linecolor=black, linewidth=0.04, dimen=outer](2.4,0.0)(1.6,-0.8)
\psframe[linecolor=black, linewidth=0.04, dimen=outer](3.2,0.8)(2.4,0.0)
\psframe[linecolor=black, linewidth=0.04, dimen=outer](3.2,0.0)(2.4,-0.8)
\rput[bl](0.3034483,0.31724137){1}
\rput[bl](0.3034483,-0.49655172){1}
\rput[bl](1.862069,0.3034483){4}
\rput[bl](2.6482759,0.3034483){4}
\rput[bl](1.09,0.30992928){2}
\rput[bl](1.8758621,-0.49655172){2}
\rput[bl](1.1034483,-0.4827586){3}
\rput[bl](2.662069,-0.5103448){3}
\psdots[linecolor=black, dotsize=0.18](4.4,0.4)
\psdots[linecolor=black, dotsize=0.18](4.4,-0.4)
\psdots[linecolor=black, dotsize=0.18](5.2,0.4)
\psdots[linecolor=black, dotsize=0.18](5.2,-0.4)
\psdots[linecolor=black, dotsize=0.18](6.0,0.4)
\psdots[linecolor=black, dotsize=0.18](6.0,-0.4)
\psdots[linecolor=black, dotsize=0.18](6.8,0.4)
\psdots[linecolor=black, dotsize=0.18](6.8,-0.4)
\psline[linecolor=black, linewidth=0.04](4.4,0.4)(4.4,-0.4)
\psline[linecolor=black, linewidth=0.04](6.0,0.4)(6.8,0.4)
\psline[linecolor=black, linewidth=0.04](5.2,0.4)(6.0,-0.4)
\psbezier[linecolor=black, linewidth=0.04](5.2,-0.4)(5.2,-1.2)(6.8,-1.2)(6.8,-0.4)
\pscircle[linecolor=colour0, linewidth=0.04, dimen=outer](9.6,0.0){1.6}
\psdots[linecolor=black, dotsize=0.18](9.02,1.44)
\psdots[linecolor=black, dotsize=0.18](8.16,0.58)
\psdots[linecolor=black, dotsize=0.18](8.12,-0.54)
\psdots[linecolor=black, dotsize=0.18](9.02,-1.42)
\psdots[linecolor=black, dotsize=0.18](10.24,-1.38)
\psdots[linecolor=black, dotsize=0.18](11.12,-0.54)
\psdots[linecolor=black, dotsize=0.18](11.1,0.58)
\psdots[linecolor=black, dotsize=0.18](10.24,1.44)
\psdots[linecolor=black, dotsize=0.18](12.4,-0.4)
\psdots[linecolor=black, dotsize=0.18](13.2,-0.4)
\psdots[linecolor=black, dotsize=0.18](14.0,-0.4)
\psdots[linecolor=black, dotsize=0.18](14.8,-0.4)
\psdots[linecolor=black, dotsize=0.18](15.6,-0.4)
\psdots[linecolor=black, dotsize=0.18](16.4,-0.4)
\psdots[linecolor=black, dotsize=0.18](17.2,-0.4)
\psdots[linecolor=black, dotsize=0.18](18.0,-0.4)
\psbezier[linecolor=black, linewidth=0.04](17.96,-0.4)(18.0,1.2)(12.4,1.2)(12.4,-0.4)
\psline[linecolor=black, linewidth=0.04](16.4,-0.4)(15.6,-0.4)
\psbezier[linecolor=black, linewidth=0.04](14.8,-0.4)(14.8,0.4)(13.2,0.4)(13.2,-0.4)
\psbezier[linecolor=black, linewidth=0.04](14.0,-0.4)(14.0,0.4)(17.2,0.4)(17.2,-0.4)
\psline[linecolor=black, linewidth=0.04](9.04,1.44)(10.24,-1.36)
\psline[linecolor=black, linewidth=0.04](10.24,1.44)(10.24,1.44)
\psline[linecolor=black, linewidth=0.04](10.24,1.44)(11.12,0.56)
\psline[linecolor=black, linewidth=0.04](9.02,-1.42)(11.12,-0.56)
\psline[linecolor=black, linewidth=0.04](8.16,0.56)(8.12,-0.56)
\end{pspicture}
}
\caption{A configuration for the $2\times 4$ array with one horizontal
  and one vertical domino is shown in four different
  representations. From left to right: a placement of paired cards in
  a game of memory, a Brauer diagram whose links correspond to the
  pairs, a chord diagram, and finally as a linear chord diagram
  resulting from breaking the circle in the chord diagram at its
  Westernmost point.}
\label{fourways}
\end{center}
\end{figure}
The enumeration of these configurations always carries a factor of
$k!$, which counts the orderings of the $k$ distinguishable pairs. It
is therefore easier to drop this factor, and thus treat the pairs as
indistinguishable. We can then think of the domino enumeration problem
in different ways: as a Brauer diagram\footnote{Terada \cite{IT} and
  Marsh and Martin \cite{MM} have considered Brauer diagrams in the
  context of combinatorics.}, as a chord diagram (cf.\ Krasko and
Omelchenko \cite{KO}), or unfolded as a linear chord diagram
(cf.\ Cameron and Killpatrick \cite{CK}). In the present paper we
provide a generating function for the numbers $D_{k,v,h}$ which count,
considering the pairs to be indistinguishable, the number of
configurations with $h$ horizontal, and $v$ vertical dominoes. It is
clear that $D_{k,v,h}=0$ for $h+v>k$; considering the $D_{k,v,h}$ as
matrices with $v\geq 0$ indexing rows, and $h\geq 0$ indexing columns,
the entries below the anti-diagonal are therefore all zero. The first few values
are as follows:
\begin{equation}\nonumber
  D_{0,v,h} = 1,\quad
  D_{1,v,h} = \begin{pmatrix}
    0& 0\\
    1& 
  \end{pmatrix},\quad
  D_{2,v,h} = \begin{pmatrix}
    1& 0& 1\\
    0& 0\\
    1&
  \end{pmatrix},\quad
   D_{3,v,h} = \begin{pmatrix}
    2& 4& 2& 0\\
    4& 0& 2&\\
    0& 0\\
    1&
  \end{pmatrix},
\end{equation}
where we have omitted the aforementioned zero entries. The sum of the
numbers on the anti-diagonal are the Fibonacci numbers, which count
the domino tilings of the $2\times k$ array\footnote{Graham, Knuth,
  and Patashnik \cite[p. 320]{GKP} give an account.}. The sum of all
numbers in the matrix\footnote{We recall that the double factorial is
  given by $n!! \coloneqq \prod_{k=0}^{\lceil{n\over2}\rceil-1} (n-2k)$, and
  we define $0!!=(-1)!!=1$.} is $(2k-1)!!$, which is the number of
ways of placing the cards, modulo re-labelling of the pairs.

The strategy we will employ is to consider the matching numbers of the
$2\times k$ grid graph, whose vertices represent the $2\times k$ array
of cards, and whose edges define the possible domino matchings. In
Figure~\ref{explaingrid} we show this grid graph for the case
$k=4$. The present author \cite[Section 3, Theorem 4]{DY} provided a
method for computing the number of $0$-domino configurations (i.e.,
configurations without any matched pairs) on any analogous graph
$G$. Let $\rho_j$ be the number of $j$-edge matchings\footnote{A
  $j$-edge matching is defined as a set of $j$ pairwise non-adjacent
  edges, none of which are loops.} on $G$. Then the number of
$0$-domino configurations is given by
\begin{equation}\nonumber
\sum_{j=0}^n (-1)^j(2n-2j-1)!! \,\rho_j,
\end{equation}
where $n$ is the number of pairs. We may therefore compute the
$D_{k,v,h}$ by computing the matching numbers for the graphs which
arise from removing $v$ vertical, and $h$ horizontal vertex pairs (and
their incident edges), from the $2\times k$ grid graph in all possible
ways.

\section{Preliminaries}

The {\it board} associated with the grid graph is defined as follows
(cf.\ Riordan \cite[p.\ 163]{JR1}). In Figure~\ref{explaingrid}, we
show the board for the case $k=4$. We color the vertices of the grid
graph black and white, in a checkerboard pattern. The columns (rows)
of the board represent the black (white) vertices. The cells of the
board represent the edges of the graph. The vertical edges correspond
to the cells on the central diagonal, while the horizontal edges
correspond to the upper and lower diagonals. The rook or matching
polynomial $g(x) = \sum g_j x^j$ encodes the number $g_j$ of $j$-edge
matchings on the graph and enjoys two important properties. The first
comes from partioning the set of all matchings into two sets: those
which contain a specific edge, and those which do not. One can then
{\it develop} the associated board using the property that the rook
polynomial of a board $B$ is equal to that of $B$ with a given cell
removed (corresponding to the absence of the specific edge in the
matching), plus $x$ times the rook polynomial of $B$ with the entire
row and column containing that cell removed (corresponding to the
presence of the specific edge in the matching). An example is shown in
Figure~\ref{develop}. The second property stems from graphs consisting
of disconnected components; the disconnectedness implies that the
number of matchings of each component are independent of one
another. We then have that if a board can be separated into regions
whose cells share no common row or column with another region (as in
the right hand side of Figure~\ref{develop}), the rook polynomial
factorizes into a product of the polynomials for the regions.

\begin{figure}[t]
\begin{center}
\psscalebox{1.0 1.0} 
{
\begin{pspicture}(0,-1.62)(8.923704,1.62)
\definecolor{colour0}{rgb}{0.61960787,0.61960787,0.61960787}
\definecolor{colour1}{rgb}{0.003921569,0.003921569,0.003921569}
\definecolor{colour2}{rgb}{0.99607843,0.99607843,0.99607843}
\definecolor{colour3}{rgb}{0.827451,0.827451,0.827451}
\psdots[linecolor=black, dotsize=0.34](0.4237037,0.68)
\psdots[linecolor=black, dotsize=0.34](1.6237037,-0.92)
\psdots[linecolor=black, dotsize=0.34](2.8237038,0.68)
\psdots[linecolor=black, dotsize=0.34](4.0237036,-0.92)
\psline[linecolor=black,
  linewidth=0.04](0.4237037,0.68)(0.4237037,-0.92)
\psline[linecolor=black,
  linewidth=0.04](0.4237037,0.68)(4.0237036,0.68)
\psline[linecolor=black,
  linewidth=0.04](0.4237037,-0.92)(4.0237036,-0.92)(4.0237036,0.68)(2.8237038,0.68)(2.8237038,-0.92)(1.6237037,-0.92)(1.6237037,0.68)
\rput[bl](0.9037037,0.81){$h_1$} \rput[bl](2.1037037,0.81){$h_3$}
\rput[bl](3.1737038,0.81){$h_5$} \rput[bl](0.92370373,-1.42){$h_2$}
\rput[bl](2.0637038,-1.42){$h_4$} \rput[bl](3.2837038,-1.42){$h_6$}
\rput[bl](-0.08,-0.26703703){$v_1$} \rput[bl](1.1,-0.26703703){$v_2$}
\rput[bl](2.3,-0.26703703){$v_3$} \rput[bl](3.5,-0.26703703){$v_4$}
\psline[linecolor=black,
  linewidth=0.04,fillstyle=solid,fillcolor=colour3](5.703704,1.6)(5.703704,0.0)(6.5037036,0.0)(6.5037036,-0.8)(7.303704,-0.8)(7.303704,-1.6)(7.303704,-1.6)(8.903704,-1.6)(8.903704,0.0)(8.1037035,0.0)(8.1037035,0.8)(7.303704,0.8)(7.303704,1.6)(5.703704,1.6)
\psline[linecolor=colour0,
  linewidth=0.04](6.5037036,1.6)(6.5037036,0.0)
\psline[linecolor=colour0,
  linewidth=0.04](7.303704,0.8)(7.303704,-0.8)
\psline[linecolor=colour0,
  linewidth=0.04](8.1037035,0.0)(8.1037035,-1.6)
\psline[linecolor=colour0, linewidth=0.04](7.303704,0.8)(5.703704,0.8)
\psline[linecolor=colour0,
  linewidth=0.04](8.1037035,0.0)(6.5037036,0.0)
\psline[linecolor=colour0,
  linewidth=0.04](8.903704,-0.8)(7.303704,-0.8)
\rput[bl](6.0185184,1.1122222){$v_1$}
\rput[bl](6.8185186,0.31074074){$v_2$}
\rput[bl](7.5237035,-0.57){$v_3$} \rput[bl](8.36296,-1.277777){$v_4$}
\rput[bl](6.6977777,1.0088889){$h_1$}
\rput[bl](7.505185,0.27666667){$h_4$}
\rput[bl](8.382963,-0.5603704){$h_5$}
\rput[bl](7.505185,-1.3233334){$h_6$}
\rput[bl](6.742222,-0.5011111){$h_3$}
\rput[bl](5.903703,0.2914815){$h_2$} \pscircle[linecolor=colour1,
  linewidth=0.04, dimen=outer, doubleline=true, doublesep=0.12,
  doublecolor=colour2](0.4148148,-0.8740741){0.16296296}
\pscircle[linecolor=colour1, linewidth=0.04, dimen=outer,
  doubleline=true, doublesep=0.12,
  doublecolor=colour2](1.6222222,0.7037037){0.16296296}
\pscircle[linecolor=colour1, linewidth=0.04, dimen=outer,
  doubleline=true, doublesep=0.12,
  doublecolor=colour2](2.8296297,-0.9037037){0.16296296}
\pscircle[linecolor=colour1, linewidth=0.04, dimen=outer,
  doubleline=true, doublesep=0.12,
  doublecolor=colour2](3.9925926,0.65925926){0.16296296}
\end{pspicture}
}
\caption{The $2\times 4$ grid graph is shown on the left, while the
  corresponding board is shown on the right. The mapping of the edges
  of the graph to the cells of the board is also displayed.}
\label{explaingrid}
\end{center}
\end{figure}

\begin{figure}[t]
\begin{center}
\psscalebox{1.0 1.0} 
{
\begin{pspicture}(0,-1.22)(10.04,1.22)
  \definecolor{colour0}{rgb}{0.827451,0.827451,0.827451}
  \definecolor{colour1}{rgb}{0,0,0}
\definecolor{colour2}{rgb}{0.50980395,0.50980395,0.50980395}
\psline[linecolor=black, linewidth=0.04, fillstyle=solid,fillcolor=colour0](0.02,1.2)(0.02,0.4)(0.42,0.4)(0.42,0.0)(0.82,0.0)(1.22,0.0)(1.22,-0.4)(1.62,-0.4)(1.62,-1.2)(2.42,-1.2)(2.42,-0.4)(2.02,-0.4)(2.02,0.0)(1.62,0.0)(1.62,0.4)(1.22,0.4)(1.22,0.8)(0.82,0.8)(0.82,1.2)(0.02,1.2)
\pscircle[linecolor=black, linewidth=0.04, dimen=outer](1.39,-0.21){0.11}
\rput[bl](2.56,0.16){$=$}
\psline[linecolor=black, linewidth=0.04, fillstyle=solid,fillcolor=colour0](4.02,1.2)(4.02,0.4)(4.42,0.4)(4.42,0.0)(5.62,0.0)(5.62,0.4)(5.22,0.4)(5.22,0.8)(4.82,0.8)(4.82,1.2)(4.02,1.2)
\psline[linecolor=black, linewidth=0.04, fillstyle=solid,fillcolor=colour0](5.62,0.0)(5.62,-1.2)(6.42,-1.2)(6.42,-0.4)(6.02,-0.4)(6.02,0.0)(5.62,0.0)
\rput[bl](6.72,0.12){$+\,x$}
\psline[linecolor=black, linewidth=0.04, fillstyle=solid,fillcolor=colour0](8.02,1.2)(8.02,0.4)(8.42,0.4)(8.42,0.0)(9.22,0.0)(9.22,0.8)(8.82,0.8)(8.82,1.2)(8.02,1.2)
\psline[linecolor=black, linewidth=0.04, fillstyle=solid,fillcolor=colour0](9.22,0.0)(9.22,-0.8)(10.02,-0.8)(10.02,0.0)(9.22,0.0)
\psframe[linecolor=black, linewidth=0.002, fillstyle=solid,fillcolor=colour1, dimen=outer](1.63,-0.0033333334)(1.2433333,-0.39)
\psframe[linecolor=black, linewidth=0.002, fillstyle=solid,fillcolor=colour2, dimen=outer](1.61,0.39)(1.2233334,0.0033333334)
\psframe[linecolor=black, linewidth=0.002, fillstyle=solid,fillcolor=colour2, dimen=outer](2.02,-0.01)(1.6333333,-0.39666668)
\psframe[linecolor=black, linewidth=0.002, fillstyle=solid,fillcolor=colour2, dimen=outer](5.61,0.39)(5.2233334,0.0033333334)
\psframe[linecolor=black, linewidth=0.002, fillstyle=solid,fillcolor=colour2, dimen=outer](6.02,-0.01)(5.633333,-0.39666668)
\end{pspicture}
}
\caption{The board on the left is developed using the black cell. The
  cells in the row and column containing the black cell are shown in
  dark grey. The boards on the right hand side both factorize into the
  product of two rook polynomials.}
\label{develop}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\psscalebox{1.0 1.0} 
{
\begin{pspicture}(0,-1.934351)(10.46,1.934351)
\psdots[linecolor=black, dotsize=0.18](0.44,-0.49435097)
\psdots[linecolor=black, dotsize=0.18](0.44,-1.294351)
\psdots[linecolor=black, dotsize=0.18](1.24,-0.49435097)
\psdots[linecolor=black, dotsize=0.18](1.24,-1.294351)
\psdots[linecolor=black, dotsize=0.18](2.04,-0.49435097)
\psdots[linecolor=black, dotsize=0.18](2.04,-1.294351)
\psline[linecolor=black, linewidth=0.04](1.24,-0.49435097)(2.04,-0.49435097)
\psline[linecolor=black, linewidth=0.04](0.44,-0.49435097)(1.24,-1.294351)
\psbezier[linecolor=black, linewidth=0.04](0.44,-1.294351)(0.44,-2.094351)(2.04,-2.094351)(2.04,-1.2943509615384619)
\psdots[linecolor=black, dotsize=0.18](4.78,-0.51435095)
\psdots[linecolor=black, dotsize=0.18](4.78,-1.314351)
\psdots[linecolor=black, dotsize=0.18](3.98,-0.51435095)
\psdots[linecolor=black, dotsize=0.18](3.98,-1.314351)
\psdots[linecolor=black, dotsize=0.18](3.18,-0.51435095)
\psdots[linecolor=black, dotsize=0.18](3.18,-1.314351)
\psline[linecolor=black, linewidth=0.04](3.98,-0.51435095)(3.18,-0.51435095)
\psline[linecolor=black, linewidth=0.04](4.78,-0.51435095)(3.98,-1.314351)
\psbezier[linecolor=black, linewidth=0.04](4.78,-1.314351)(4.78,-2.114351)(3.18,-2.114351)(3.18,-1.3143509615384619)
\psdots[linecolor=black, dotsize=0.18](10.16,-1.414351)
\psdots[linecolor=black, dotsize=0.18](10.16,-0.614351)
\psdots[linecolor=black, dotsize=0.18](9.36,-1.414351)
\psdots[linecolor=black, dotsize=0.18](9.36,-0.614351)
\psdots[linecolor=black, dotsize=0.18](8.56,-1.414351)
\psdots[linecolor=black, dotsize=0.18](8.56,-0.614351)
\psline[linecolor=black, linewidth=0.04](9.36,-1.414351)(8.56,-1.414351)
\psline[linecolor=black, linewidth=0.04](10.16,-1.414351)(9.36,-0.614351)
\psbezier[linecolor=black, linewidth=0.04](10.16,-0.614351)(10.16,0.18564904)(8.56,0.18564904)(8.56,-0.6143509615384619)
\psdots[linecolor=black, dotsize=0.18](5.88,-1.334351)
\psdots[linecolor=black, dotsize=0.18](5.88,-0.534351)
\psdots[linecolor=black, dotsize=0.18](6.68,-1.334351)
\psdots[linecolor=black, dotsize=0.18](6.68,-0.534351)
\psdots[linecolor=black, dotsize=0.18](7.48,-1.334351)
\psdots[linecolor=black, dotsize=0.18](7.48,-0.534351)
\psline[linecolor=black, linewidth=0.04](6.68,-1.334351)(7.48,-1.334351)
\psline[linecolor=black, linewidth=0.04](5.88,-1.334351)(6.68,-0.534351)
\psbezier[linecolor=black, linewidth=0.04](5.88,-0.534351)(5.88,0.26564905)(7.48,0.26564905)(7.48,-0.5343509615384618)
\psdots[linecolor=black, dotsize=0.18](0.46,1.845649)
\psdots[linecolor=black, dotsize=0.18](0.46,1.045649)
\psdots[linecolor=black, dotsize=0.18](1.26,1.045649)
\psdots[linecolor=black, dotsize=0.18](2.06,1.045649)
\psline[linecolor=black, linewidth=0.04](0.44,1.7856491)(0.44,0.98564905)(0.44,0.98564905)
\psline[linecolor=black, linewidth=0.04](1.32,1.0356491)(0.52,1.0356491)
\psline[linecolor=black, linewidth=0.04](2.1,1.0356491)(1.3,1.0356491)
\rput[bl](0.0,0.24564904){$1+3x+x^2$}
\psdots[linecolor=black, dotsize=0.18](4.78,1.825649)
\psdots[linecolor=black, dotsize=0.18](4.78,1.0256491)
\psdots[linecolor=black, dotsize=0.18](3.98,1.0256491)
\psdots[linecolor=black, dotsize=0.18](3.18,1.0256491)
\psline[linecolor=black, linewidth=0.04](4.8,1.7656491)(4.8,0.965649)(4.8,0.965649)
\psline[linecolor=black, linewidth=0.04](3.92,1.0156491)(4.72,1.0156491)
\psline[linecolor=black, linewidth=0.04](3.14,1.0156491)(3.94,1.0156491)
\psdots[linecolor=black, dotsize=0.18](5.84,1.045649)
\psdots[linecolor=black, dotsize=0.18](5.84,1.845649)
\psdots[linecolor=black, dotsize=0.18](6.64,1.845649)
\psdots[linecolor=black, dotsize=0.18](7.44,1.845649)
\psline[linecolor=black, linewidth=0.04](5.82,1.105649)(5.82,1.9056491)(5.82,1.9056491)
\psline[linecolor=black, linewidth=0.04](6.7,1.855649)(5.9,1.855649)
\psline[linecolor=black, linewidth=0.04](7.48,1.855649)(6.68,1.855649)
\psdots[linecolor=black, dotsize=0.18](9.98,1.0256491)
\psdots[linecolor=black, dotsize=0.18](9.98,1.825649)
\psdots[linecolor=black, dotsize=0.18](9.18,1.825649)
\psdots[linecolor=black, dotsize=0.18](8.38,1.825649)
\psline[linecolor=black, linewidth=0.04](10.0,1.085649)(10.0,1.8856491)(10.0,1.8856491)
\psline[linecolor=black, linewidth=0.04](9.12,1.835649)(9.92,1.835649)
\psline[linecolor=black, linewidth=0.04](8.34,1.835649)(9.14,1.835649)
\rput[bl](2.68,0.28564903){$1+3x+x^2$}
\rput[bl](5.46,0.34564903){$1+3x+x^2$}
\rput[bl](8.02,0.32564905){$1+3x+x^2$}
\end{pspicture}
}
\caption{On the bottom row, the four configurations counted by
  $D_{3,0,1}$ are shown as Brauer diagrams. On the top row, the set of
  graphs ${\cal G}_{3,0,1}$ corresponding to the removal of the vertex
  pair corresponding to the domino, along with their matching
  polynomials, are shown. The sum of these polynomials yields ${\cal
    T}_{3,0,1}(x) = 4(1+3x+x^2)$.}
\label{exampleTD}
\end{center}
\end{figure}

Riordan (\cite{JR}, \cite[p.\ 230]{JR1}) (McQuistan and Lichtman \cite{ML} give
connections to dimer models in physics) provided the generating
function for the rook polynomials of the $2\times k$ grids
\begin{equation}\label{riordan}\nonumber
T(x,y) \coloneqq \frac{1-xy}{1-y-2xy-xy^2+x^3y^3} = \sum_{k=0}^\infty T_k(x) y^k ,
\end{equation}
where $T_k(x)$ are the rook polynomials. Riordan also provided similar
generating functions for several related grids, whose boards are shown
in Figure~\ref{shapes},
\begin{align}\nonumber
  &s(x,y) \coloneqq \frac{T(x,y)}{(1-xy)^2},\quad r(x,y) \coloneqq (1-xy)\, s(x,y),
  \quad R(x,y) \coloneqq y\,r(x,y),\\\nonumber
  &S(x,y) \coloneqq \left(1-2xy-xy^2+x^3y^3\right)s(x,y).
\end{align}
For example, the rook polynomial corresponding to the board on the
left hand side of Figure~\ref{develop} is $R_3(x)\, r_3(x) +
x\,T_3(x)\, T_2(x)$.

   
\section{Generating functions for matching numbers}

We now turn our attention to the set ${\cal G}_{k,v,h}$ of graphs
which arise when $h$ horizontal, and $v$ vertical vertex pairs are
removed, in all possible ways, from the $2\times k$ grid graph. The
four graphs belonging to ${\cal G}_{3,0,1}$ are displayed in
Figure~\ref{exampleTD}. Each of the graphs $g \in {\cal G}_{k,v,h}$
will have an associated matching polynomial, which with a slight abuse
of notation, we will denote $g(x)$. The combinatorial object of
interest will be the sum of these polynomials
\begin{equation}\nonumber
  {\cal T}_{k,v,h}(x) \coloneqq \sum_{g\in {\cal G}_{k,v,h}} g(x).
\end{equation}
\begin{figure}[t]
\begin{center}
\psscalebox{0.8 0.8} 
{\begin{pspicture}(0,-3.02)(16.5,3.02)
\definecolor{colour0}{rgb}{0.827451,0.827451,0.827451}
\psline[linecolor=black, linewidth=0.04,fillstyle=solid,fillcolor=colour0](9.22,2.2)(9.22,1.8)(9.62,1.8)(9.62,1.4)(10.02,1.4)(10.02,1.0)(10.42,1.0)(10.42,0.6)(10.82,0.6)(10.82,0.2)(12.02,0.2)(12.02,0.6)(11.62,0.6)(11.62,1.0)(11.22,1.0)(11.22,1.4)(10.82,1.4)(10.82,1.8)(10.42,1.8)(10.42,2.2)(10.02,2.2)(10.02,2.6)(9.62,2.6)(9.62,3.0)(9.22,3.0)(9.22,2.2)
\rput[bl](15.22,1.4){$= S(x,y)$}
\psline[linecolor=black, linewidth=0.04,fillstyle=solid,fillcolor=colour0](1.62,-1.0)(1.62,-1.8)(2.02,-1.8)(2.02,-2.2)(2.42,-2.2)(2.42,-2.6)(2.82,-2.6)(2.82,-3.0)(3.22,-3.0)(3.22,-1.8)(2.82,-1.8)(2.82,-1.4)(2.42,-1.4)(2.42,-1.0)(1.62,-1.0)
\rput[bl](3.62,-2.2){$=$ }
\psline[linecolor=black, linewidth=0.04,fillstyle=solid,fillcolor=colour0](6.0127144,-2.957189)(6.0127144,-2.1571891)(5.6127143,-2.1571891)(5.6127143,-1.757189)(5.212714,-1.757189)(5.212714,-1.357189)(4.812714,-1.357189)(4.812714,-0.9571891)(4.412714,-0.9571891)(4.412714,-2.1571891)(4.812714,-2.1571891)(4.812714,-2.557189)(5.212714,-2.557189)(5.212714,-2.957189)(6.0127144,-2.957189)
\rput[bl](6.42,-2.2){$= r(x,y)$}
\psline[linecolor=black, linewidth=0.04,fillstyle=solid,fillcolor=colour0](10.62,-2.8)(9.82,-2.8)(9.82,-2.4)(9.42,-2.4)(9.42,-2.0)(9.02,-2.0)(9.02,-1.6)(8.62,-1.6)(8.62,-1.2)(9.82,-1.2)(9.82,-1.6)(10.22,-1.6)(10.22,-2.0)(10.62,-2.0)(10.62,-2.8)
\rput[bl](10.82,-2.2){$=$}
\psline[linecolor=black, linewidth=0.04,fillstyle=solid,fillcolor=colour0](11.412714,-1.157189)(12.212714,-1.157189)(12.212714,-1.5571891)(12.612714,-1.5571891)(12.612714,-1.9571891)(13.012714,-1.9571891)(13.012714,-2.3571892)(13.412714,-2.3571892)(13.412714,-2.757189)(12.212714,-2.757189)(12.212714,-2.3571892)(11.812715,-2.3571892)(11.812715,-1.9571891)(11.412714,-1.9571891)(11.412714,-1.157189)
\rput[bl](13.62,-2.2){$= R(x,y)$}
\psline[linecolor=black, linewidth=0.04,fillstyle=solid,fillcolor=colour0](4.82,3.0)(4.82,2.6)(4.82,1.8)(5.22,1.8)(5.22,1.4)(5.62,1.4)(5.62,1.0)(6.02,1.0)(6.02,0.6)(6.42,0.6)(6.42,0.2)(6.82,0.2)(6.82,1.4)(6.42,1.4)(6.42,1.8)(6.02,1.8)(6.02,2.2)(5.62,2.2)(5.62,2.6)(5.22,2.6)(5.22,3.0)(4.82,3.0)
\rput[bl](6.72,1.8){$= s(x,y)$}
\psline[linecolor=black, linewidth=0.04,fillstyle=solid,fillcolor=colour0](0.02,3.0)(0.02,2.6)(0.02,2.6)(0.02,2.2)(0.42,2.2)(0.42,1.8)(0.82,1.8)(0.82,1.4)(1.22,1.4)(1.22,1.0)(1.62,1.0)(1.62,0.6)(2.02,0.6)(2.02,0.2)(2.82,0.2)(2.82,1.0)(2.42,1.0)(2.42,1.4)(2.02,1.4)(2.02,1.8)(1.62,1.8)(1.62,2.2)(1.22,2.2)(1.22,2.6)(0.82,2.6)(0.82,3.0)(0.42,3.0)(0.42,3.0)(0.02,3.0)(0.02,3.0)
\rput[bl](2.42,1.8){$= T(x,y)$}
\psline[linecolor=black, linewidth=0.04,fillstyle=solid,fillcolor=colour0](14.823736,2.9948063)(14.423737,2.9948063)(14.423737,2.5948064)(14.023736,2.5948064)(14.023736,2.1948063)(13.623736,2.1948063)(13.623736,1.7948064)(13.223737,1.7948064)(13.223737,1.3948064)(12.823736,1.3948064)(12.823736,0.19480638)(13.223737,0.19480638)(13.223737,0.5948064)(13.623736,0.5948064)(13.623736,0.99480635)(14.023736,0.99480635)(14.023736,1.3948064)(14.423737,1.3948064)(14.423737,1.7948064)(14.823736,1.7948064)(14.823736,2.1948063)(15.223737,2.1948063)(15.223737,2.5948064)(15.623736,2.5948064)(15.623736,2.9948063)(14.823736,2.9948063)
\rput[bl](12.02,1.8){$=$ }
\end{pspicture}
}
\end{center}
\caption{The boards which arise when the calculus of the rook
  polynomial is applied to the boards shown in Figure~\ref{gridboard}.}
\label{shapes}
\end{figure}
\begin{theorem}
The generating function for the ${\cal T}_{k,v,h}(x)$ is given
by\footnote{\label{ftp}The power of $y$ is taken to be $k-v-h$; this is a useful
  parameterization for computing the generating function for the
  $D_{k,v,h}$.}
\begin{align}\nonumber\label{ThmFirst}
&{\cal T}(x,y,w,z)\coloneqq \sum_{k,h,v\geq 0} {\cal T}_{k,v,h}(x) \,y^{k-v-h} w^v z^h\\
  &=\frac{1 - xy - z}{1-(1+2 x) y-z - w (1 - xy - z)+(x y+z)
    (x^2 y^2 - (1 - z) z - y (1 - 2 x z))},
\end{align}
where the power of the variable $w$ (respectively $z$) corresponds to
the number of removed vertical (respectively horizontal) vertex pairs,
while the power of the variable $y$ corresponds to the number of
remaining vertex pairs after these removals have taken place. The
power $j$ of the variable $x$ corresponds to $j$-edge matchings in the
resulting graphs.
\end{theorem}

\begin{proof}
   The removal of a horizontal vertex pair from the grid graph
   corresponds to the deletion of a cell on the lower or upper
   diagonal of the board, together with its entire row and column. In
   Figure~\ref{gridboard}, boards resulting from the deletion of two
   horizontal vertex pairs are shown.  When the boards are developed
   using the black cells in Figure~\ref{gridboard}, various shapes
   arise; these are shown in Figure~\ref{shapes}. For example, the
   configuration shown on the left in Figure~\ref{gridboard}
   corresponds to
   \begin{align}\nonumber\label{example}
     &R(x,y)\cdot S(x,y) \cdot r(x,y) + xy\, T(x,y)\cdot R(x,y) \cdot r(x,y)\\
     &+ R(x,y) \cdot r(x,y)\cdot xy\, T(x,y)\nonumber
     + x^2y^2\, T(x,y) \cdot T(x,y) \cdot T(x,y)\\
     &= yr^2S + 2xy^2 Tr^2 + x^2y^2 T^3,
   \end{align}   
   where the $\cdot$ denotes ordinary multiplication, and has been
   included to aid in the following explanation. The first term
   corresponds to the removal of both the black cells, the second
   (third) term to the additional removal of the row and column
   containing the first (second) black cell, and the last term to the
   removal of the rows and columns containing both black cells. The
   multiplication also accounts\footnote{The reader is referred to
     Flajolet and Sedgewick \cite[p.\ 16]{FS} for an account of the
     basic symbolic method.}  for the ordered sum over all possible
   positions of the removed horizontal vertex
   pairs\footnote{\label{fn}The exception is when the two removed
     horizontal vertex pairs are directly over top of one another in
     the grid graph; these coincident configurations will be accounted
     for below.}. When the row and column containing a black cell is
   removed, the overall board is shortened, and hence earns a factor
   of $y$; this is why the expression $xy$ appears for each such
   removal. It is straightforward to see that the corresponding
   expression for the board shown on the right in
   Figure~\ref{gridboard} differs from the above only in the first
   term, which becomes $R(x,y) \cdot s(x,y) \cdot R(x,y) = y^2r^2s$.
\begin{figure}[t]
\begin{center}
\psscalebox{0.5 0.5} 
{\begin{pspicture}(0,-3.42)(6.84,3.42)
\definecolor{colour2}{rgb}{0.827451,0.827451,0.827451}
\definecolor{colour4}{rgb}{0.50980395,0.50980395,0.50980395}
  \definecolor{colour3}{rgb}{0,0,0}
\psline[linecolor=black, linewidth=0.04, fillstyle=solid,fillcolor=colour2](0.02,3.4)(0.02,2.6)(0.42,2.6)(0.42,2.2)(0.82,2.2)(0.82,1.8)(1.62,1.8)(1.62,1.4)(2.02,1.4)(2.02,0.6)(2.42,0.6)(2.42,0.2)(2.82,0.2)(2.82,-0.2)(3.22,-0.2)(3.22,-0.6)(3.62,-0.6)(3.62,-1.0)(4.42,-1.0)(4.42,-1.4)(4.82,-1.4)(4.82,-2.2)(5.22,-2.2)(5.22,-2.6)(5.62,-2.6)(5.62,-3.0)(6.02,-3.0)(6.02,-3.4)(6.82,-3.4)(6.82,-2.6)(6.42,-2.6)(6.42,-2.2)(6.02,-2.2)(6.02,-1.8)(5.62,-1.8)(5.62,-1.4)(5.22,-1.4)(5.22,-1.0)(4.82,-1.0)(4.82,-0.6)(4.42,-0.6)(4.42,-0.2)(4.02,-0.2)(4.02,0.2)(3.62,0.2)(3.62,0.6)(3.22,0.6)(3.22,1.0)(2.82,1.0)(2.82,1.4)(2.42,1.4)(2.42,1.8)(2.02,1.8)(2.02,2.2)(1.62,2.2)(1.62,2.6)(1.22,2.6)(1.22,3.0)(0.82,3.0)(0.82,3.4)(0.02,3.4)
\pscircle[linecolor=black, linewidth=0.04, dimen=outer](1.8136508,1.5973545){0.074074075}
\pscircle[linecolor=black, linewidth=0.04, dimen=outer](4.613651,-1.1910053){0.074074075}
\psframe[linecolor=black, linewidth=0.002, fillstyle=solid,fillcolor=colour4, dimen=outer](2.01,2.19)(1.6233333,1.8033333)
\psframe[linecolor=black, linewidth=0.002, fillstyle=solid,fillcolor=colour3, dimen=outer](2.03,1.7966666)(1.6433333,1.41)
\psframe[linecolor=black, linewidth=0.002, fillstyle=solid,fillcolor=colour4, dimen=outer](2.42,1.79)(2.0333333,1.4033333)
\psframe[linecolor=black, linewidth=0.002, fillstyle=solid,fillcolor=colour4, dimen=outer](4.8166666,-0.61)(4.43,-0.99666667)
\psframe[linecolor=black, linewidth=0.002, fillstyle=solid,fillcolor=colour3, dimen=outer](4.8366666,-1.0033333)(4.45,-1.39)
\psframe[linecolor=black, linewidth=0.002, fillstyle=solid,fillcolor=colour4, dimen=outer](5.2266665,-1.01)(4.84,-1.3966666)
\end{pspicture}            
\qquad\qquad\begin{pspicture}(0,-3.42)(6.84,3.42)
\definecolor{colour2}{rgb}{0.827451,0.827451,0.827451}
  \definecolor{colour3}{rgb}{0,0,0}
\definecolor{colour4}{rgb}{0.50980395,0.50980395,0.50980395}
\psline[linecolor=black, linewidth=0.04, fillstyle=solid,fillcolor=colour2](0.02,3.4)(0.02,2.6)(0.42,2.6)(0.42,2.2)(0.82,2.2)(0.82,1.8)(1.62,1.8)(1.62,1.4)(2.02,1.4)(2.02,0.6)(2.42,0.6)(2.42,0.2)(2.82,0.2)(2.82,-0.2)(3.22,-0.2)(3.22,-0.6)(3.62,-0.6)(3.62,-1.0)(4.02,-1.0)(4.02,-1.4)(4.42,-1.4)(4.42,-1.8)(4.82,-1.8)(4.82,-2.2)(5.22,-2.2)(5.22,-2.6)(5.62,-2.6)(5.62,-3.0)(6.02,-3.0)(6.02,-3.4)(6.82,-3.4)(6.82,-2.6)(6.42,-2.6)(6.42,-2.2)(6.02,-2.2)(6.02,-1.8)(5.62,-1.8)(5.62,-1.4)(5.22,-1.4)(5.22,-1.0)(4.42,-1.0)(4.42,-0.6)(4.02,-0.6)(4.02,0.2)(3.62,0.2)(3.62,0.6)(3.22,0.6)(3.22,1.0)(2.82,1.0)(2.82,1.4)(2.42,1.4)(2.42,1.8)(2.02,1.8)(2.02,2.2)(1.62,2.2)(1.62,2.6)(1.22,2.6)(1.22,3.0)(0.82,3.0)(0.82,3.4)(0.02,3.4)
\pscircle[linecolor=black, linewidth=0.04, dimen=outer](1.8371428,1.6028571){0.071428575}
\pscircle[linecolor=black, linewidth=0.04, dimen=outer](4.237143,-0.8057143){0.068571426}
\psframe[linecolor=black, linewidth=0.002, fillstyle=solid,fillcolor=colour4, dimen=outer](2.0033333,2.1966667)(1.6166667,1.81)
\psframe[linecolor=black, linewidth=0.002, fillstyle=solid,fillcolor=colour3, dimen=outer](2.0233333,1.8033333)(1.6366667,1.4166666)
\psframe[linecolor=black, linewidth=0.002, fillstyle=solid,fillcolor=colour4, dimen=outer](2.4133334,1.7966666)(2.0266666,1.41)
\rput{-180.0}(8.466666,-2.4333334){\psframe[linecolor=black, linewidth=0.002, fillstyle=solid,fillcolor=colour4, dimen=outer](4.4266667,-1.0233333)(4.04,-1.41)}
\rput{-180.0}(8.426666,-1.6466666){\psframe[linecolor=black, linewidth=0.002, fillstyle=solid,fillcolor=colour3, dimen=outer](4.4066668,-0.63)(4.02,-1.0166667)}
\rput{-180.0}(7.6466665,-1.6333333){\psframe[linecolor=black, linewidth=0.002, fillstyle=solid,fillcolor=colour4, dimen=outer](4.016667,-0.62333333)(3.63,-1.01)}
\end{pspicture}
}
\end{center}
\caption{Boards corresponding to removing two horizontal vertex pairs
  from the grid graph. On the left both removed pairs correspond to
  cells on the upper diagonal. On the right, one upper, and one lower
  diagonal pair have been removed. The black cells are used in further
  developing the boards using the calculus of the rook polynomial, in
  the same way as shown in the example in Figure~\ref{develop}.}
\label{gridboard}
\end{figure}

We now focus on generalising to the removal of an arbitrary number
$\tilde h$ of non-coincident (see Footnote~\ref{fn}) horizontal vertex
pairs from the grid graph. In keeping with previous notation, we call
this set of graphs $\widetilde{\cal G}_{k,0,\tilde h}$. We begin by accounting
for the terms which arise from the first step in the development of
the associated boards, i.e. when the black cells are removed from the
boards. For the time being, we exclude the terms which arise when any
rows and columns containing those black cells are also removed. We
introduce the variable $z$, the power of which corresponds to the
number of horizontal vertex pairs removed from the grid graph. When
$\tilde h=0$, we have simply $T$. When $\tilde h=1$, we have $2zyr^2$,
where the factor of 2 arises as the removed horizontal vertex pair can
correspond to a cell on the upper, or the lower diagonal of the
board. As we have seen in the previous paragraph, for $\tilde h=2$, we
have $2z^2(yr^2S+y^2r^2s)=2z^2yr^2(S+ys)$, where again the factor of 2
accounts for swapping the diagonals which the two cells (corresponding
to the removed vertex pairs) are taken from. It follows that the
general term for $\tilde h >0$ is $2yzr^2 \left(z(S+ys)\right)^{\tilde
  h-1}$. Performing a sum over $\tilde h \geq 0$ we obtain the
expression
   \begin{equation}\label{jjghs}
     T + \frac{2yzr^2}{1-z(S+ys)} .
   \end{equation}

We now account for those terms which arise in the development of the
boards whenever the row and column containing a black cell are further
removed. As was explained above, the calculus of the rook polynomial
implies that we gain a factor of $xy$ for each such a removal. In
fact, we gain a factor of $2xyz$; the 2 since the black cell could be
on the upper, or lower diagonal, and the $z$ to account for the
corresponding removal of the vertex pair from the grid graph. Once one
row and column have been removed, the board is split into two
independent boards. If we remove the columns and rows of $q-1$
different black cells, we will have $q$ independent boards; the
corresponding terms are then given by
   \begin{equation}\nonumber
     (2xyz)^{q-1}\left(T + \frac{2yzr^2}{1-z(S+ys)} \right)^q.
   \end{equation}
We can also interpret this expression from the point of view of the
grid graph itself. The factor $(2xyz)^{q-1}$ corresponds to the removal
of $q-1$ horizontal vertex pairs, where the coincident edge below or
above is chosen in the matching. The factor 2 comes from choosing
either the upper or the lower vertex pair to remove. This leaves us to
deal with $q$ separate and independent grids. Each of these $q$ grids
is enumerated by a factor of Equation~(\ref{jjghs}), where $T$
corresponds to the case where no further horizontal vertex pairs are
removed. The fraction, on the other hand, corresponds to the case
where at least one further horizontal vertex pair is removed (but the
coincident edge is not chosen in a matching).
   
   Taking the sum over $q>0$, we obtain
   \begin{equation}\nonumber
     {\cal X} \coloneqq\sum_{k,\tilde h\geq 0}\,y^{k-\tilde h} z^{\tilde h}\
     \left(\sum_{g\in\widetilde {\cal G}_{k,0,\tilde h}} g(x)\right)
     =\frac{T + \frac{2yzr^2}{1-z(S+ys)}}{1-2xyz\left(T +
  \frac{2yzr^2}{1-z(S+ys)}\right)}.
   \end{equation}
   
   It remains to account for the removal of vertical vertex pairs, and
   coincident horizontal vertex pairs, from the grid graph. The removal
   of a single pair of coincident horizontal vertex pairs is
   equivalent to the removal of two neighboring vertical vertex
   pairs. The effect of either of these removals on the board is again to
   break it into two independent boards. Thus we find that the removal of
   coincident horizontal and vertical vertex pairs is accounted for as
   follows:
   \begin{equation}\nonumber
     \sum_{j=0}^\infty (w + z^2)^j {\cal X}^{j+1}
     =  \frac{T + \frac{2yzr^2}{1-z(S+ys)}}{1-(2xyz+z^2+w)
       \left(T + \frac{2yzr^2}{1-z(S+ys)}\right)},
   \end{equation}
   where the coefficient of $w^v$ corresponds to the removal of $v$
   vertical vertex pairs. Simplifying this expression, we obtain
   Equation~(\ref{ThmFirst}).   
\end{proof}

\section{From matching numbers to domino-counting generating functions}

We now use the result of Theorem~\ref{ThmFirst} to compute the number
of configurations with exactly $h$ horizontal, and $v$ vertical
dominoes. Let the $\rho_j(k,v,h)$ be defined\footnote{We use the notation $[y^n]\,f(y)$
  to represent the coefficient of $y^n$ in the Taylor expansion of
  $f(y)$.} as follows:
\begin{equation}\nonumber
\rho_j(k, v, h) \coloneqq [x^j] \mathcal{T}_{k, v, h}(x).
\end{equation}
We remind the reader the combinatorial significance of this
quantity. The set ${\cal G}_{k,v,h}$ of graphs is obtained from
removing $v$ vertical, and $h$ horizontal vertex pairs from the
$2\times k$ grid graph in all possible ways. Each graph $g\in {\cal
  G}_{k,v,h}$ has a number $g_j$ of $j$-edge matchings. We then have
that
\begin{equation}
  \rho_j(k, v, h) = \sum_{g\in{\cal G}_{k,v,h} }g_j.
\end{equation}
As mentioned
in the Introduction, the number $D_{k,h,v}$ of configurations with
exactly $h$ horizontal, and $v$ vertical dominoes is given by
\begin{equation}\label{MyOldThm}
D_{k,v,h}=\sum_{j=0}^n (-1)^j(2n-2j-1)!! \,\rho_j(k,v,h),
\end{equation}
where $n=k-h-v$. We define the corresponding generating function in
the usual way,
\begin{equation}\nonumber
D(y,w,z) \coloneqq \sum_{k,h,v\geq 0} D_{k,v,h}\,y^kw^vz^h.
\end{equation}
We now translate Equation~(\ref{MyOldThm}) into an operation on ${\cal T}(x,y,w,z)$.
\begin{theorem}
  The generating function $D(y,w,z)$ may be obtained using the
  following integral representation:
\begin{equation}\nonumber
 D(y,w,z) = \int_0^\infty dt\,e^{-t}
\frac{1}{2\pi i} \oint_{C_\epsilon} \frac{dx}{x\sqrt{1+2x}}\,
      {\cal T}\left(\frac{x}{t},\frac{-yt}{x},yw,yz\right),
\end{equation}
where the contour integral with respect to $x$ is taken around a small
circle containing the origin.
\end{theorem}
\begin{proof}
We consider the coefficient of $y^n$ in the Taylor expansion of ${\cal T}(x,y,w,z)$,
and define $\Omega_{j,n}(w,z)\coloneqq [x^jy^n]\, {\cal T}(x,y,w,z)$. We have
\begin{equation}\nonumber
[y^n]\, {\cal T}(x,y,w,z)=\sum_{j=0}^n \Omega_{j,n}(w,z)\, x^j =
\sum_{j=0}^n \left(\sum_{h,v\geq 0} \rho_j(n+h+v, v, h) \, w^v z^h \right)x^j
  .
\end{equation}
Under the integration in $t$, the replacements $x\to x t^{-1}$ and $y\to
yt$ dress this result by a factor of $\int_0^\infty dt\, t^{n-j} e^{-t}=(n-j)!$
\begin{equation}\label{thiseq}
  [y^n]\int_0^\infty dt \,e^{-t}\, {\cal T}(xt^{-1},yt,w,z) 
  =\sum_{j=0}^n
  (n-j)!\,\Omega_{j,n}(w,z)\, x^j.
\end{equation}
We now consider the coefficient of $x^n$ in the expression obtained by
multiplying Equation~(\ref{thiseq}) with $(1+2x)^{-1/2}$
\begin{align}\nonumber
  &[x^n] \left( \sum_{q=0}^\infty (-1)^q \frac{(2q-1)!!}{q!} \,x^q \right)
  \left( \sum_{j=0}^n (n-j)!\,\Omega_{j,n}(w,z)\, x^j \right) \\\nonumber
  &= (-1)^n \sum_{j=0}^n (-1)^j (2n-2j-1)!! \, \Omega_{j,n}(w,z).
\end{align}
We may, therefore, compute this quantity by further scaling $y \to
y/x$ and taking the residue at the origin after an overall
multiplication by $x^{-1}$. The factor of $(-1)^n$ is absorbed by a
final replacement $y \to -y$. The variables $w$ and $z$ are also
scaled by $y$, so that the unnatural parameterization discussed in
Footnote~\ref{ftp} is rectified.
\end{proof}

\begin{corollary}
The generating function $D(y,w,z)$  is given by
\begin{align}\nonumber
D(y,&w,z)= \\ \nonumber
 &\int_0^\infty dt\frac{e^{-t}}{(1+(1-w)y -(1-z)^2y^2)
    \sqrt{1-\frac{2 t y (1-(1-z)y)}{(1+(1- z)y) (1+(1-w)y -(1-z)^2y^2)}}}\\
\nonumber
  &=\sum_{j=0}^\infty (2j-1)!!
  \frac{ y^j (1-(1-z)y)^j}{(1+(1-z)y)^j(1+(1-w)y -(1-z)^2y^2)^{j+1}}.
\end{align}
\end{corollary}
\begin{proof}
  We note from Equation~(\ref{ThmFirst}) that ${\cal
    T}\left(\frac{x}{t},\frac{-yt}{x},yw,yz\right)= Ax/(Bx+Ct)$, where
  $A,B$, and $C$ are functions of $y,w$, and $z$. The contour
  integration replaces $x \to -Ct/B$ in the factor
  $(1+2x)^{-1/2}$. The integration over $t$ is interpreted as acting
  on the Taylor expansion of the resulting expression.
\end{proof}
This is not a convergent series\footnote{It may be interpreted as the
  real part (taking $y,w$, and $z\in \mathbb{R}$) of the expansion of
  the following expression, asymptotic in $y^{-1}$:
  $\sqrt{\frac{2(1+(1- z)y)}{y(1-(1- z)y)(1+(1-w) y-(1-z)^2y^2)}}
  F\left( \sqrt{\frac{(1+(1- z)y)(1+(1-w)
      y-(1-z)^2y^2)}{2y(1-(1-z)y)}}\right)$, where $F$ is Dawson's
  integral; Nijimbere \cite{VN} gives a modern account of the
  asymptotic expansion of this function and its relatives.}, and hence
we cannot benefit from an analytic generating function, with which
questions about asymptotic behavior could easily be answered. In order
to convert this formal generating function into a convergent series,
we could take an inverse Laplace transform in $y$ to form an
exponential generating function
\begin{equation}\nonumber
E(y,w,z) \coloneqq {\cal L}^{-1}\left\{ y^{-1} D(y^{-1},w,z) \right\}.
\end{equation}
Performing this transform is not straightforward, however in the
simple case of counting only vertical dominoes, it is feasible, and
yields a well-known result \seqnum{A055140},
\begin{equation}\label{byvonly}
D(y,w,1) = \sum_{j=0}^\infty \frac{(2j-1)!!\,y^j}{(1+(1-w)y)^{j+1}}
\to E(y,w,1)=
\frac{e^{y(w-1)}}{\sqrt{1-2y}},
\end{equation}
which counts the number of matchings of $2k$ people with partners (of
either sex) such that exactly $v$ couples are left
together. Unfortunately, we have been unable to perform the transform
for the case of counting only horizontal dominoes \seqnum{A325754}
\begin{equation}\nonumber
 D(y,1,z) =  \frac{1}{\left(1-(1-z)y\right)}
\sum_{j=0}^\infty   \frac{(2j-1)!! \,y^j}{\left(1+(1-z)y\right)^{2j+1}},
\end{equation}
but in the next section we derive the exponential generating function
by appealing to known results for the $1\times 2k$ problem.

It is also interesting to consider the case where vertical and
horizontal dominoes are not distinguished, i.e., $D(y,z,z)$. The
present author \cite[Section 4]{DY} considered this sequence previously. We can
now provide a generating function for these numbers \seqnum{A325753}
\begin{equation}\nonumber
  D(y,z,z) = 
  \sum_{j=0}^\infty
  \frac{(2j-1)!!\,y^j\,(1-(1-z)y)^j}
       {(1+(1-z)y)^j\left(1+(1-z)y-(1-z)^2y^2\right)^{j+1}}.
\end{equation}
The present author \cite[Section 4.2]{DY} also made several
conjectures\footnote{A. Howroyd \cite{AH} has proven several of
  these.} for generating functions for the so-called $(k-\ell)$-domino
configurations, when the number of dominoes is $\ell$ less than the
maximum value $k$. These can now be readily calculated as follows:
\begin{equation}\nonumber
  {\cal F}_{\ell}(y) \coloneqq \sum_{k\geq 0} \Biggl(\sum_{\substack{h,v\geq 0\\h+v=k-\ell}}
  D_{k,v,h}\Biggr)\, y^k
  =[z^{-\ell}] \lim_{z\to\infty} D\left(\frac{y}{z},z,z\right).
\end{equation}
The first few such generating functions are
\begin{align}\nonumber
  {\cal F}_0 = \frac{1}{1-y-y^2},\qquad {\cal F}_1 =
  \frac{2y^3}{(1-y)(1-y-y^2)^2},\qquad {\cal F}_2 =
  \frac{y^2(1+3y+6y^2+y^3+3y^4)}{(1-y)^2(1-y-y^2)^3}.
\end{align}
The function ${\cal F}_0$ is the generating function for the Fibonacci
numbers, giving the number of domino tilings. The function ${\cal
  F}_1$ is that for the path length of the Fibonacci tree of order
$k$, \seqnum{A178523}. The sequences corresponding to the cases
$\ell=2,\dots,5$ appear as \seqnum{A318267} to \seqnum{A318270},
respectively; before the results presented here were available these
were obtained by using data produced by a computer program to fix the
coefficients in the numerators of the generating functions, based on a
guess for the pattern of the denominators. Hence only a small range of
values of $\ell$ were achieved.

\section{Connections to linear chord diagrams}

Kreweras and Poupard \cite{KP} solved the problem of counting the
$h$-domino configurations on the $1\times 2k$ grid graph (i.e., a path
of length $2k$). Cameron and Killpatrick \cite{CK} recently revisited
this case in the context of linear chord diagrams, and provided a
derivation of the corresponding exponential generating function. Let
$L_{k,h}$ be the number of $h$-domino configurations on the $1\times
2k$ grid graph. We seek to establish a correspondence with the number
$D_{k,h}$ of $h$ horizontal domino configurations on the $2\times k$
grid graph, where we allow any number of vertical dominoes.
\begin{theorem}\label{LtoD}
The numbers $L_{k,h}$ and $D_{k,h}$ are related by the following recursion relation:
  \begin{equation}\nonumber
D_{k,h} = D_{k-1,h} + L_{k,h} - D_{k-1,h-1}.
    \end{equation}
\end{theorem}
\begin{proof}
We begin by unfolding the the vertices of the $2\times k$ grid graph,
as shown in Figure~\ref{unfold}, to give the vertices of the $1\times
2k$ grid graph. We then note that the central pair of vertices does
not correspond to a horizontal domino in the $2\times k$ graph, but
rather to a vertical one. The configurations counted by $L_{k,h}$
may be divided into two sets: those with a domino on the central pair
and those without. Those configurations with a domino on the central
pair are counted by $D_{k-1,h-1}$, as the central pair is effectively
deleted, leaving the $2\times (k-1)$ grid graph with $h-1$ horizontal
dominoes. In Figure~\ref{DfromL}, we provide a pictorial interpretation
of this relation. The configurations counted by $D_{k,h}$ can be
similarly divided, but since the central pair this time represents a
vertical domino, those configurations with this vertical domino are
equal in number to $D_{k-1,h}$.
\end{proof}
\begin{figure}[t]
\begin{center}
    \psscalebox{0.75 0.75} 
{
\begin{pspicture}(0,-1.2122674)(12.177403,1.2122674)
\psdots[linecolor=black, dotsize=0.18](0.6781469,1.1235654)
\psdots[linecolor=black, dotsize=0.18](0.088701926,-1.1235654)
\psdots[linecolor=black, dotsize=0.18](1.3518503,0.6921448)
\psdots[linecolor=black, dotsize=0.18](0.8887019,-1.1235654)
\psdots[linecolor=black, dotsize=0.18](2.0255537,0.2607242)
\psdots[linecolor=black, dotsize=0.18](1.6887019,-1.1235654)
\psdots[linecolor=red, dotsize=0.18](2.699257,-0.17069645)
\psdots[linecolor=red, dotsize=0.18](2.4887018,-1.1235654)
\rput{-59.39724}(1.5743339,1.5531247){\psarc[linecolor=black, linewidth=0.04, dimen=outer, arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.0]{<-}(2.148702,-0.6035655){0.4}{163.85567}{270.0}}
\psline[linecolor=black, linewidth=0.12, arrowsize=0.05291667cm 2.66,arrowlength=2.4,arrowinset=0.0]{<-}(6.0887017,-0.32356548)(3.6887019,-0.32356548)
\psdots[linecolor=black, dotsize=0.18](6.488702,-1.1235654)
\psdots[linecolor=black, dotsize=0.18](7.288702,-1.1235654)
\psdots[linecolor=black, dotsize=0.18](8.088702,-1.1235654)
\psdots[linecolor=red, dotsize=0.18](8.888702,-1.1235654)
\psdots[linecolor=red, dotsize=0.18](9.688702,-1.1235654)
\psdots[linecolor=black, dotsize=0.18](10.488702,-1.1235654)
\psdots[linecolor=black, dotsize=0.18](11.288702,-1.1235654)
\psdots[linecolor=black, dotsize=0.18](12.088702,-1.1235654)
\rput{-127.53087}(15.839679,5.7988305){\psarc[linecolor=black, linewidth=0.04, dimen=outer, arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.0]{<-}(9.3487015,-1.0035654){0.4}{163.85567}{270.0}}
\end{pspicture}
}
\caption{The $2\times k$ grid graph is unfolded to produce the
  $1\times 2k$ grid graph. The vertices marked in red comprise a
  vertical domino, which becomes horizontal upon unfolding.}
\label{unfold}
\end{center}
\end{figure}

\begin{figure}[h]
\begin{center}
\psscalebox{0.8 0.8} 
{
\begin{pspicture}(0,-1.5023571)(15.328702,1.5023571)
\definecolor{colour0}{rgb}{0.61960787,0.61960787,0.61960787}
\psline[linecolor=colour0, linewidth=0.04](9.64,1.0025451)(15.24,1.0025451)
\psdots[linecolor=black, dotsize=0.18](9.64,1.0025451)
\psdots[linecolor=black, dotsize=0.18](10.44,1.0025451)
\psdots[linecolor=black, dotsize=0.18](11.24,1.0025451)
\psdots[linecolor=red, dotsize=0.18](12.04,1.0025451)
\psdots[linecolor=red, dotsize=0.18](12.84,1.0025451)
\psdots[linecolor=black, dotsize=0.18](13.64,1.0025451)
\psdots[linecolor=black, dotsize=0.18](14.44,1.0025451)
\psdots[linecolor=black, dotsize=0.18](15.24,1.0025451)
\rput{-88.58558}(11.090218,13.492521){\psarc[linecolor=black, linewidth=0.04, dimen=outer](12.46,1.0625452){0.4}{88.15239}{270.0}}
\psline[linecolor=colour0, linewidth=0.04](2.44,1.0025451)(8.04,1.0025451)
\psdots[linecolor=black, dotsize=0.18](2.44,1.0025451)
\psdots[linecolor=black, dotsize=0.18](3.24,1.0025451)
\psdots[linecolor=black, dotsize=0.18](4.04,1.0025451)
\psdots[linecolor=red, dotsize=0.18](4.84,1.0025451)
\psdots[linecolor=red, dotsize=0.18](5.64,1.0025451)
\psdots[linecolor=black, dotsize=0.18](6.44,1.0025451)
\psdots[linecolor=black, dotsize=0.18](7.24,1.0025451)
\psdots[linecolor=black, dotsize=0.18](8.04,1.0025451)
\rput{-88.58558}(5.6284475,7.8942275){\psarc[linecolor=black, linewidth=0.04, dimen=outer](6.86,1.0625452){0.4}{88.15239}{270.0}}
\rput[bl](0.04,1.0025451){$L_{k,1}=$}
\rput[bl](8.7,0.8825452){+}
\psline[linecolor=colour0, linewidth=0.04](9.6,-0.73745483)(15.2,-0.73745483)
\psdots[linecolor=black, dotsize=0.18](9.6,-0.73745483)
\psdots[linecolor=black, dotsize=0.18](10.4,-0.73745483)
\psdots[linecolor=black, dotsize=0.18](11.2,-0.73745483)
\psdots[linecolor=red, dotsize=0.18](12.0,-0.73745483)
\psdots[linecolor=red, dotsize=0.18](12.8,-0.73745483)
\psdots[linecolor=black, dotsize=0.18](13.6,-0.73745483)
\psdots[linecolor=black, dotsize=0.18](14.4,-0.73745483)
\psdots[linecolor=black, dotsize=0.18](15.2,-0.73745483)
\rput{-88.58558}(12.790675,11.755483){\psarc[linecolor=black, linewidth=0.04, dimen=outer](12.42,-0.6774548){0.4}{88.15239}{270.0}}
\psline[linecolor=colour0, linewidth=0.04](2.4,-0.73745483)(8.0,-0.73745483)
\psdots[linecolor=black, dotsize=0.18](2.4,-0.73745483)
\psdots[linecolor=black, dotsize=0.18](3.2,-0.73745483)
\psdots[linecolor=black, dotsize=0.18](4.0,-0.73745483)
\psdots[linecolor=red, dotsize=0.18](4.8,-0.73745483)
\psdots[linecolor=red, dotsize=0.18](5.6,-0.73745483)
\psdots[linecolor=black, dotsize=0.18](6.4,-0.73745483)
\psdots[linecolor=black, dotsize=0.18](7.2,-0.73745483)
\psdots[linecolor=black, dotsize=0.18](8.0,-0.73745483)
\rput{-88.58558}(7.3289046,6.1571894){\psarc[linecolor=black, linewidth=0.04, dimen=outer](6.82,-0.6774548){0.4}{88.15239}{270.0}}
\rput[bl](0.0,-0.73745483){$D_{k,1}=$}
\rput[bl](8.66,-0.85745484){+}
\rput{-88.58558}(14.371662,13.295989){\psarc[linecolor=black, linewidth=0.04, dimen=outer](14.0,-0.71745485){0.4}{88.15239}{270.0}}
\rput[bl](11.62,-1.4174548){$D_{k-1,1}$}
\rput[bl](11.52,0.28254515){$D_{k-1,0}$}
\end{pspicture}
}
\caption{The relationship between the numbers, $L_{k,h}$ and $D_{k,h}$,
  of $h$-horizontal-domino configurations on the $1\times 2k$, and
  $2\times k$ grid graphs, respectively, is shown for the case $h=1$.
}
\label{DfromL}
\end{center}
\end{figure}

Jovovic \cite{JV}, and Cameron and Killpatrick \cite{CK}, provide the
exponential generating function
\begin{equation}\nonumber
  L(y,z) \coloneqq
  \sum_{k,h\geq 0} L_{k,h} \frac{y^k}{k!}\, z^h
  = \frac{e^{(\sqrt{1-2 y}\,-\,1) (1-z)}}{\sqrt{1-2 y}}.
\end{equation}
Translating the recursion relation from Theorem~\ref{LtoD} into a
differential equation for the exponential generating function, we obtain
\begin{equation}\label{ODE}
  \frac{\partial E(y,1,z)}{\partial y} - (1-z) E(y,1,z) =
  \frac{\partial L(y,z)}{\partial y}.
\end{equation}
This elementary, non-homogeneous, first-order ODE may be solved using an
integrating factor. 
\begin{corollary}
  The exponential generating function for $D_{k,h}$ is as follows:
\begin{align}\label{byhonly}
E(y,1,z)& =  \frac{e^{(\sqrt{1-2 y}\,-\,1) (1-z)}}{\sqrt{1-2 y}}\\\nonumber
  &-e^{(y-2) (1-z)} \sqrt{\frac{\pi}{2}} \sqrt{1-z}
  \left(
\erfi
\left( \frac{(\sqrt{1-2 y}+1) \sqrt{1-z}}{\sqrt{2}} \right)
-\erfi (\sqrt{2} \sqrt{1-z})
  \right),
\end{align}
where we have expressed the result in terms of the imaginary error
function $\erfi$.
\end{corollary}
\begin{proof}
The method of an integrating factor may be used to solve Equation~(\ref{ODE}).  
\end{proof}

\section{Asymptotic growth and distributions}

The asymptotics of the exponential generating functions $E(y,w,1)$ and
$E(y,1,z)$, given in Equations~(\ref{byvonly}) and (\ref{byhonly}),
respectively, can be analyzed using the usual machinery of analytic
combinatorics. Let ${\cal V}_k$ be the random variable defined as the
number of vertical dominoes in a random configuration on the $2\times
k$ grid. Similarly, let ${\cal H}_k$ be the analogous random variable
counting horizontal dominoes. The probability distribution functions
$V_{k,v}\coloneqq P({\cal V}_k=v)$ and $H_{k,h}\coloneqq P({\cal
  H}_k=h)$ are computed as follows:
\begin{equation}\nonumber
  V_{k,v} = \frac{1}{(2k-1)!!}\sum_{h\geq 0} D_{k,v,h},\qquad
  H_{k,h} = \frac{1}{(2k-1)!!}\sum_{v\geq 0} D_{k,v,h}.
\end{equation}
Taking derivatives of $E(y,w,1)$ by $w$, we can compute
the factorial moments of $V_{k,v}$. We note that
\begin{equation}\nonumber
  \left[y^k\right] \frac{\partial^m E(y,w,1)}{\partial w^m}\biggr|_{w=1} =
  \left[y^k\right]\frac{y^m}{\sqrt{1-2y}}
  \sim \left(\frac{1}{2}\right)^m \frac{(2k-1)!!}{k!},
\end{equation}
where $\sim$ indicates asymptotic growth in $k$, and so the
$m^{\text{th}}$ factorial moment of $V_{k,v}$ is asymptotically
$(1/2)^m$, consistent with a Poisson distribution of mean $1/2$. A
similar argument can be made for $H_{k,h}$, where the corresponding
mean is found to be $1$. Indeed, Kreweras and Poupard \cite{KP} (see
also Cameron and Killpatrick \cite{CK}) proved that the asymptotic
factorial moments for the distribution of dominoes on the $1\times 2k$
grid graph are all equal to one; the case of horizontal dominoes on
the $2\times k$ grid graph must have the same asymptotic behavior,
since the matchings differ only at a single site: the vertices shown
in red in Figure~\ref{unfold}.

We expect, in the $k\to\infty$ limit, the occurrences of vertical and
horizontal dominoes to be independent, and so the distribution
$P_{k,p}\coloneqq P({\cal H}_k+{\cal V}_k=p)$ of dominoes (vertical or
horizontal) should also be Poisson with mean $1/2 + 1 = 3/2$. We
calculate $P_{k,p}$ as follows:
\begin{equation}\nonumber
P_{k,p} = \frac{1}{(2k-1)!!}\sum_{\substack{v,h\geq 0\\v+h=p}} D_{k,v,h}.
\end{equation}
The present author \cite[Section 2, Theorem 1]{DY} proved that the mean of this
distribution, exact in $k$, is given by
\begin{equation}\nonumber
  \sum_{p\geq 0} p\, P_{k,p} = \frac{3k-2}{2k-1},
\end{equation}
which gives the expected result of $3/2$ in the $k\to \infty$
limit. We do not have an expression for the exponential generating
function for the $D_{k,v,h}$, and so cannot follow the same line of
reasoning used above to establish the equality of the remaining
factorial moments. A different strategy\footnote{The author thanks
  Stephan Wagner for providing this proof.} may be used,
however, to prove that, indeed,
\begin{theorem}\label{threehalves}
\begin{equation}\nonumber
  \lim_{k\to\infty}
  P_{k,p}
  \simeq \frac{e^{-3/2}}{p!}
  \left(\frac{3}{2}\right)^p.
\end{equation}
\end{theorem}
\begin{proof}
  We begin by noting that $P_{k,p}$ is (up to the denominator $(2k-1)!!$) the
  coefficient of $y^kz^p$ in $D(y,z,z)$, i.e.
  \begin{align}\nonumber
    P_{k,p} = &[y^kz^p] 
    \sum_{j=0}^\infty
    \frac{(2j-1)!!}{(2k-1)!!}
  \frac{y^j\,(1-(1-z)y)^j}
       {(1+(1-z)y)^j\left(1+(1-z)y-(1-z)^2y^2\right)^{j+1}}\\\nonumber
       =&\sum_{j=0}^k
    \frac{(2j-1)!!}{(2k-1)!!}[y^{k-j}z^p]
  \frac{(1-(1-z)y)^j}
       {(1+(1-z)y)^j\left(1+(1-z)y-(1-z)^2y^2\right)^{j+1}}.
    \end{align}
  We now define the coefficients $a_{j,n}$ as follows:
  \begin{equation}\nonumber
    a_{j,n}  \coloneqq [x^n]\frac{(1-x)^j}{(1+x)^j(1+x-x^2)^{j+1}}.
    \end{equation}
  We then have that
  \begin{equation}\nonumber
    P_{k,p} = \sum_{j=0}^k  \frac{(2j-1)!!}{(2k-1)!!}[y^{k-j}z^p]
    \sum_{n\geq 0} a_{j,n} (1-z)^n y^n
    = \sum_{j=0}^k  \frac{(2j-1)!!}{(2k-1)!!}[z^p]
     a_{j,k-j} (1-z)^{k-j} .
  \end{equation}
  Let $P_k(z)$ be defined as follows:
  \begin{equation}\nonumber
    P_k(z) \coloneqq \sum_{p\geq 0} P_{k,p} z^p = \sum_{j=0}^k
    \frac{(2j-1)!!}{(2k-1)!!}a_{j,k-j} (1-z)^{k-j} =
   \sum_{\ell=0}^k
    \frac{(2k-2\ell-1)!!}{(2k-1)!!}a_{k-\ell,\ell} (1-z)^{\ell}.
  \end{equation}
  
  We now proceed to prove
  \begin{equation}\nonumber
    \lim_{k\to \infty} P_k(z) = e^{3(z-1)/2},
  \end{equation}
  which is equivalent to the statement of the theorem. We accomplish
  this by placing bounds on the $a_{k-\ell,\ell}$. Note that
  \begin{align}\nonumber
    a_{k-\ell,\ell} &= [x^\ell] \frac{1}{1+x-x^2}\left(
    \frac{1-x}{(1+x)(1+x-x^2)}\right)^{k-\ell}\\\nonumber
&    =(-1)^\ell [x^\ell]
    \frac{1}{1-x-x^2}\left( \frac{1+x}{(1-x)(1-x-x^2)}\right)^{k-\ell}.
  \end{align}
  The following inequalities hold coefficient-by-coefficient:
  \begin{equation}\nonumber
    1 \leq \frac{1}{1-x-x^2} \leq \frac{1}{1-3x},
\quad\text{and}\quad
    1+3x \leq \frac{1+x}{(1-x)(1-x-x^2)} \leq \frac{1}{1-3x}.
  \end{equation}
  It then follows that
  \begin{equation}\nonumber
    [x^\ell](1+3x)^{k-\ell} \leq (-1)^\ell a_{k-\ell,\ell} \leq [x^\ell] (1-3x)^{-(k-\ell+1)},
  \end{equation}
  or, equivalently
  \begin{equation}\nonumber
    3^\ell {k-\ell \choose \ell}  \leq (-1)^\ell a_{k-\ell,\ell} \leq 3^\ell {k \choose \ell}  .
  \end{equation}
 In the $k\to\infty$ limit these bounds become equal. In order to
 establish the form of $P_k(z)$ in this limit, we consider
 \begin{equation}\nonumber
     \frac{(2k-2\ell-1)!!}{(2k-1)!!} 3^\ell {k-\ell \choose \ell} \leq
     \frac{(2k-2\ell-1)!!}{(2k-1)!!} (-1)^\ell a_{k-\ell,\ell} \leq
     \frac{(2k-2\ell-1)!!}{(2k-1)!!} 3^\ell {k \choose \ell} ,
  \end{equation}
 and note that the bounds in this inequality are equal to $(3/2)^\ell/\ell!$
 in the limit, thus
 \begin{equation}\nonumber
   \lim_{k\to\infty} \frac{(2k-2\ell-1)!!}{(2k-1)!!} (-1)^\ell a_{k-\ell,\ell} =
   \frac{3^\ell}{2^\ell \ell!}.
 \end{equation}
It remains to show that (the limit of) the sum in the definition of
$P_k(z)$ is convergent. For this we note that 
\begin{align}\nonumber
  \left| \frac{(2k-2\ell-1)!!}{(2k-1)!!} (-1)^\ell a_{k-\ell,\ell} (z-1)^\ell \right|
  &\leq \frac{(2k-2\ell-1)!!}{(2k-1)!!} 3^\ell {k \choose \ell}
  \left|z-1\right|^\ell\\\nonumber
  &=\frac{3^\ell|z-1|^\ell}{\ell!}\prod_{j=0}^{\ell-1}
  \frac{k-j}{2k-2j-1}\leq\frac{3^\ell|z-1|^\ell}{\ell!},
\end{align}
and, further,
\begin{equation}\nonumber
 \sum_{\ell\geq 0}  \frac{3^\ell|z-1|^\ell}{\ell!} = e^{3|z-1|}
\end{equation}
is a convergent series; by dominated convergence it follows that 
\begin{align}\nonumber
\lim_{k\to\infty} P_k(z) = \sum_{\ell\geq 0} \lim_{k\to\infty}
\frac{(2k-2\ell-1)!!}{(2k-1)!!} (-1)^\ell a_{k-\ell,\ell} (1-z)^\ell = \sum_{\ell\geq 0}
\frac{3^\ell}{2^\ell \ell!} (z-1)^\ell = e^{3(z-1)/2}.
  \end{align}

\end{proof}

\section{Acknowledgments}
The author would like to thank the anonymous referee for a very
careful reading of the manuscript and for suggesting several
improvements. He also thanks Stephan Wagner for providing the proof to
Theorem~\ref{threehalves}.

\begin{thebibliography}{99}

\bibitem{DY} D. Young, The number of domino matchings in the game of
  memory, {\it J. Integer Sequences} {\bf 21} (2018), 
  \href{https://cs.uwaterloo.ca/journals/JIS/VOL21/Young/young2.html}{Article 18.8.1}.
 
\bibitem{IT} I. Terada, Brauer diagrams, updown tableaux and nilpotent matrices,
  {\it J. Algebraic Combin.} {\bf 14} (2001), 229--267.

\bibitem{MM} R. J. Marsh and P. Martin, Tiling bijections between
  paths and Brauer diagrams, {\it J. Algebraic Combin.} {\bf 33}
  (2011), 427--453.

\bibitem{KO} E. Krasko and A. Omelchenko, Enumeration of chord
  diagrams without loops and parallel chords, {\it
    Electron. J. Combin.} {\bf 24} (2017), 
    \href{https://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p43}{Article P3.43}.

\bibitem{FS} P. Flajolet and R. Sedgewick, {\it Analytic
  Combinatorics}, Cambridge University Press, 2009.

\bibitem{GKP} R. Graham, D. Knuth, and O. Patashnik, {\it Concrete
  Mathematics}, Addison-Wesley, 1994.

\bibitem{VN} V. Nijimbere, Analytical evaluation and asymptotic
  evaluation of Dawson's integral and related functions in
  mathematical physics, preprint, 2017,
  \url{http://arxiv.org/abs/1703.06757}.
  
\bibitem{CK} N. Cameron and K. Killpatrick, Statistics on linear chord
  diagrams, preprint, 2019, \url{http://arxiv.org/abs/1902.09021}.
  
\bibitem{JR} J. Riordan, The enumeration of permutations with
  three-ply staircase restrictions, unpublished memorandum, 1963,
  \url{http://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{AH} A. Howroyd, \url{http://oeis.org/A318268}.
  
\bibitem{KP} G. Kreweras and Y. Poupard, Sur les partitions en paires
  d'un ensemble fini totalement ordonn{\'e}, {\it Publications de
    l'Institut de Statistique de l'Universit\'{e} de Paris} {\bf 23}
  (1978), 57--74.

\bibitem{JV} V. Jovovic, \url{http://oeis.org/A079267}.
  
\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, chord diagram, Brauer diagram.
\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  June 8 2019; 
revised versions received July 31 2019; December 18 2019. 
Published in {\it Journal of Integer Sequences},
December 27 2019.

\bigskip
\hrule
\bigskip

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


\end{document}