Generating Functions for Domino Matchings in the 2 × k Game of Memory

Donovan Young St Albans, Hertfordshire AL1 4SZ United Kingdom

                   donovan.m.young@gmail.com

Abstract When all the elements of the multiset {1, 1, 2, 2, 3, 3, …, k, k} are placed in the cells of a 2 × 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 × 2 or 2 × 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×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.

1 Introduction

The game of memory consists of the placement of a set of distinct pairs of cards in a rectangular array. The present author [1] 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 × 2 or 2 × 1 dominoes. In this paper we consider the case of 2 × k arrays in more detail. In Figure 1 we show a configuration of the case k = 4 with h = 1 horizontal dominoes, and v = 1 vertical dominoes. 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^{1}, as a chord diagram (cf. Krasko

1Terada [2] and Marsh and Martin [3] have considered Brauer diagrams in the context of combinatorics.

1 1 4 4 2 2 3 3

Figure 1: A configuration for the 2 × 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.

and Omelchenko [4]), or unfolded as a linear chord diagram (cf. Cameron and Killpatrick [8]). 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 ≥ 0 indexing rows, and h ≥ 0 indexing columns, the entries below the anti-diagonal are therefore all zero. The first few values are as follows:

D_{0,v,h} = 1, D_{1,v,h} = \binom{0 0}{1} , D_{2,v,h} = (\begin{matrix}1 & 0 & 1 \\ 0 & 0 \\ 1 \end{matrix}) , D_{3,v,h} = (\begin{matrix}2 & 4 & 2 & 0 \\ 4 & 0 & 2 \\ 0 & 0 \\ 1 \end{matrix}) ,

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 × k array^{2}. The sum of all numbers in the matrix^{3} 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 × k grid graph, whose vertices represent the 2×k array of cards, and whose edges define the possible domino matchings. In Figure 2 we show this grid graph for the case k = 4. The present author [1, Section 3, Theorem 4] provided a method for computing the number of 0-domino configurations (i.e., configurations without any matched pairs) on any analogous graph G. Let ρ_{j} be the number of j-edge matchings^{4} on G. Then the number of 0-domino configurations is given by

∑_{j=0}^{n}(−1)^{j}(2n − 2j − 1)!! ρ_{j},

2Graham, Knuth, and Patashnik [6, p. 320] give an account.

3We recall that the double factorial is given by n!! := ∏_{k=0}^{⌈ \frac{n}{2} ⌉−1}(n − 2k), and we define 0!! = (−1)!! = 1.

4A j-edge matching is defined as a set of j pairwise non-adjacent edges, none of which are loops.

\begin{matrix}h_{1} \\ h_{3} \\ h_{5} \\ h_{2} \\ h_{4} \\ h_{6} \\ v_{1} \\ v_{2} \\ v_{3} \\ v_{4} \\ v_{1} \\ v_{2} \\ v_{3} \\ v_{4} \\ h_{1} \\ h_{4} \\ h_{5} \\ h_{6} \\ h_{3} \\ h_{2} \end{matrix}

Figure 2: The 2 × 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.

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 × k grid graph in all possible ways.

2 Preliminaries

The board associated with the grid graph is defined as follows (cf. Riordan [10, p. 163]). In Figure 2, 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) = ∑ 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 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 3. 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 3), the rook polynomial factorizes into a product of the polynomials for the regions.

Riordan ([9], [10, p. 230]) (McQuistan and Lichtman [11] give connections to dimer models in physics) provided the generating function for the rook polynomials of the 2 × k grids

T (x, y) := \frac{1 − xy}{1 − y − 2xy − xy^{2} + x^{3}y^{3}} = ∑_{k=0}^{∞} T_{k}(x)y^{k},

= + x

Figure 3: 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.

\begin{matrix}1 + 3x + x^{2} \\ 1 + 3x + x^{2} \\ 1 + 3x + x^{2} \\ 1 + 3x + x^{2} \end{matrix}

Figure 4: 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 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 T_{3,0,1}(x) = 4(1 + 3x + x^{2}).

where T_{k}(x) are the rook polynomials. Riordan also provided similar generating functions for several related grids, whose boards are shown in Figure 5,

s(x, y) := \frac{T (x, y)}{(1 − xy)^{2}} , r(x, y) := (1 − xy) s(x, y), R(x, y) := y r(x, y),

S(x, y) := (1 − 2xy − xy^{2} + x^{3}y^{3}) s(x, y).

For example, the rook polynomial corresponding to the board on the left hand side of Figure 3 is R_{3}(x) r_{3}(x) + x T_{3}(x) T_{2}(x).

3 Generating functions for matching numbers

We now turn our attention to the set 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 × k grid graph. The four graphs belonging to G_{3,0,1} are displayed in Figure 4. Each of the graphs g ∈ G_{k,v,h} will have an associated matching polynomial, which with a slight abuse of notation, we will denote

= S(x, y) = r(x, y) = R(x, y) = s(x, y) = T (x, y) =

Figure 5: The boards which arise when the calculus of the rook polynomial is applied to the boards shown in Figure 6.

g(x). The combinatorial object of interest will be the sum of these polynomials

T_{k,v,h}(x) := ∑_{g∈G_{k,v,h}} g(x).

Theorem 1. The generating function for the T_{k,v,h}(x) is given by^{5}

T (x, y, w, z) := ∑_{k,h,v≥0} T_{k,v,h}(x) y^{k−v−h}w^{v}z^{h}

= \frac{1 − xy − z}{1 − (1 + 2x)y − z − w(1 − xy − z) + (xy + z)(x^{2}y^{2} − (1 − z)z − y(1 − 2xz))}, (1)

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.

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 6, boards resulting from the deletion of two horizontal vertex pairs are shown. When the boards are developed using the black cells in Figure 6, various shapes arise; these are shown in Figure 5. For example, the configuration shown on the left in Figure 6 corresponds to

R(x, y) · S(x, y) · r(x, y) + xy T (x, y) · R(x, y) · r(x, y)
+ R(x, y) · r(x, y) · xy T (x, y) + x^{2}y^{2} T (x, y) · T (x, y) · T (x, y)
= yr^{2}S + 2xy^{2}T r^{2} + x^{2}y^{2}T^{3},  (2)

5The 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}.

Figure 6: 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 3.

where the · 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^{6} for the ordered sum over all possible positions of the removed horizontal vertex pairs^{7}. 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 6 differs from the above only in the first term, which becomes R(x, y) · s(x, y) · R(x, y) = y^{2}r^{2}s.

We now focus on generalising to the removal of an arbitrary number h̃ of non-coincident (see Footnote 7) horizontal vertex pairs from the grid graph. In keeping with previous notation, we call this set of graphs G̃_{k,0,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 h̃ = 0, we have simply T. When 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 h̃ = 2, we have 2z^{2}(yr^{2}S + y^{2}r^{2}s) = 2z^{2}yr^{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 h̃ > 0 is 2yzr^{2} (z(S + ys))^{h̃−1}. Performing a sum over h̃ ≥ 0 we obtain the expression

6The reader is referred to Flajolet and Sedgewick [5, p. 16] for an account of the basic symbolic method.

7The 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.

T + \frac{2yzr^{2}}{1 − z(S + ys)}.  (3)

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

(2xyz)^{q−1} (T + \frac{2yzr^{2}}{1 − z(S + ys)})^{q} .

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 (3), 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

X := ∑_{k,h̃≥0} y^{k−h̃}zh̃ ( ∑_{g∈G̃_{k,0,h̃}} g(x)) = \frac{T + \frac{2yzr^{2}}{1−z(S+ys)}}{1 − 2xyz (T + \frac{2yzr^{2}}{1−z(S+ys)})}.

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:

∑_{j=0}^{∞}(w + z^{2})^{j}X^{j+1} = \frac{T + \frac{2yzr^{2}}{1−z(S+ys)}}{1 − (2xyz + z^{2} + w) (T + \frac{2yzr^{2}}{1−z(S+ys)})},

where the coefficient of w^{v} corresponds to the removal of v vertical vertex pairs. Simplifying this expression, we obtain Equation (1).

4 From matching numbers to domino-counting generating functions

We now use the result of Theorem 1 to compute the number of configurations with exactly h horizontal, and v vertical dominoes. Let the ρ_{j}(k, v, h) be defined^{8} as follows:

ρ_{j}(k, v, h) := [x^{j}]T_{k,v,h}(x).

We remind the reader the combinatorial significance of this quantity. The set G_{k,v,h} of graphs is obtained from removing v vertical, and h horizontal vertex pairs from the 2 × k grid graph in all possible ways. Each graph g ∈ G_{k,v,h} has a number g_{j} of j-edge matchings. We then have that

ρ_{j}(k, v, h) = ∑_{g∈G_{k,v,h}} g_{j}.  (4)

As mentioned in the Introduction, the number D_{k,h,v} of configurations with exactly h horizontal, and v vertical dominoes is given by

D_{k,v,h} = ∑_{j=0}^{n}(−1)^{j}(2n − 2j − 1)!! ρ_{j}(k, v, h),  (5)

where n = k − h − v. We define the corresponding generating function in the usual way,

D(y, w, z) := ∑_{k,h,v≥0} D_{k,v,h} y^{k}w^{v}z^{h}.

We now translate Equation (5) into an operation on T (x, y, w, z).

Theorem 2. The generating function D(y, w, z) may be obtained using the following integral representation:

D(y, w, z) = ∫_{0}^{∞} dt e^{−t} \frac{1}{2πi} ∮_{C_{ϵ}} \frac{dx}{x\sqrt{1 + 2x}} T (\frac{x}{t}, \frac{−yt}{x}, yw, yz) ,

where the contour integral with respect to x is taken around a small circle containing the origin.

Proof. We consider the coefficient of y^{n} in the Taylor expansion of T (x, y, w, z), and define Ω_{j,n}(w, z) := [x^{j}y^{n}] T (x, y, w, z). We have

[y^{n}] T (x, y, w, z) = ∑_{j=0}^{n} Ω_{j,n}(w, z) x^{j} = ∑_{j=0}^{n} ( ∑_{h,v≥0} ρ_{j}(n + h + v, v, h) w^{v}z^{h}) x^{j}.

8We use the notation [y^{n}] f(y) to represent the coefficient of y^{n} in the Taylor expansion of f(y).

Under the integration in t, the replacements x → xt^{−1} and y → yt dress this result by a factor of ∫_{0}^{∞} dt t^{n−j}e^{−t} = (n − j)!

[y^{n}] ∫_{0}^{∞} dt e^{−t} T (xt^{−1}, yt, w, z) = ∑_{j=0}^{n}(n − j)! Ω_{j,n}(w, z) x^{j}.  (6)

We now consider the coefficient of x^{n} in the expression obtained by multiplying Equation (6) with (1 + 2x)^{−1/2}

[x^{n}] (∑_{q=0}^{∞}(−1)^{q} \frac{(2q − 1)!!}{q!} x^{q}) (∑_{j=0}^{n}(n − j)! Ω_{j,n}(w, z) x^{j})

= (−1)^{n} ∑_{j=0}^{n}(−1)^{j}(2n − 2j − 1)!! Ω_{j,n}(w, z).

We may, therefore, compute this quantity by further scaling y → 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 → −y. The variables w and z are also scaled by y, so that the unnatural parameterization discussed in Footnote 5 is rectified.

Corollary 3. The generating function D(y, w, z) is given by

D(y,w, z) =

∫_{0}^{∞} dt\frac{e^{−t}}{(1 + (1 − w)y − (1 − z)^{2}y^{2})\sqrt{1 − \frac{2ty(1−(1−z)y)}{(1+(1−z)y)(1+(1−w)y−(1−z)^{2}y^{2})}}}

= ∑_{j=0}^{∞}(2j − 1)!!\frac{y^{j}(1 − (1 − z)y)^{j}}{(1 + (1 − z)y)^{j}(1 + (1 − w)y − (1 − z)^{2}y^{2})^{j+1}} .

Proof. We note from Equation (1) that T (\frac{x}{t}, \frac{−yt}{x}, yw, yz) = Ax/(Bx + Ct), where A, B, and C are functions of y, w, and z. The contour integration replaces x → −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.

This is not a convergent series^{9}, 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

E(y, w, z) := L^{−1} {y^{−1}D(y^{−1}, w, z)} .

9It may be interpreted as the real part (taking y, w, and z ∈ ℝ) 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)^{2}y^{2})}}F (\sqrt{\frac{(1+(1−z)y)(1+(1−w)y−(1−z)^{2}y^{2})}{2y(1−(1−z)y)}}), where F is Dawson’s integral; Nijimbere [7] gives a modern account of the asymptotic expansion of this function and its relatives.

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 \underline{A055140},

D(y, w, 1) = ∑_{j=0}^{∞} \frac{(2j − 1)!! y^{j}}{(1 + (1 − w)y)^{j+1}} → E(y, w, 1) = \frac{e^{y(w−1)}}{\sqrt{1 − 2y}} ,  (7)

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

D(y, 1, z) = \frac{1}{(1 − (1 − z)y)} ∑_{j=0}^{∞} \frac{(2j − 1)!! y^{j}}{(1 + (1 − z)y)^{2j+1}} ,

but in the next section we derive the exponential generating function by appealing to known results for the 1 × 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 [1, Section 4] considered this sequence previously. We can now provide a generating function for these numbers \underline{A325753}

D(y, z, z) = ∑_{j=0}^{∞} \frac{(2j − 1)!! y^{j} (1 − (1 − z)y)^{j}}{(1 + (1 − z)y)^{j} (1 + (1 − z)y − (1 − z)^{2}y^{2})^{j+1}} .

The present author [1, Section 4.2] also made several conjectures^{10} for generating functions for the so-called (k − ℓ)-domino configurations, when the number of dominoes is ℓ less than the maximum value k. These can now be readily calculated as follows:

F_{ℓ}(y) := ∑_{k≥0}( ∑_{\begin{matrix}h,v≥0 \\ h+v=k−ℓ \end{matrix}} D_{k,v,h}) y^{k} = [z^{−ℓ}] lim_{z→∞} D (\frac{y}{z} , z, z) .

The first few such generating functions are

F_{0} = \frac{1}{1 − y − y^{2}} ,  F_{1} = \frac{2y^{3}}{(1 − y)(1 − y − y^{2})^{2}} ,  F_{2} = \frac{y^{2}(1 + 3y + 6y^{2} + y^{3} + 3y^{4})}{(1 − y)^{2}(1 − y − y^{2})^{3}}.

The function F_{0} is the generating function for the Fibonacci numbers, giving the number of domino tilings. The function F_{1} is that for the path length of the Fibonacci tree of order k, \underline{A178523}. The sequences corresponding to the cases ℓ = 2, …, 5 appear as \underline{A318267} to \underline{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 ℓ were achieved.

10A. Howroyd [12] has proven several of these.

Figure 7: The 2 × k grid graph is unfolded to produce the 1 × 2k grid graph. The vertices marked in red comprise a vertical domino, which becomes horizontal upon unfolding.

5 Connections to linear chord diagrams

Kreweras and Poupard [13] solved the problem of counting the h-domino configurations on the 1 × 2k grid graph (i.e., a path of length 2k). Cameron and Killpatrick [8] 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 × 2k grid graph. We seek to establish a correspondence with the number D_{k,h} of h horizontal domino configurations on the 2 × k grid graph, where we allow any number of vertical dominoes.

Theorem 4. The numbers L_{k,h} and D_{k,h} are related by the following recursion relation:

D_{k,h} = D_{k−1,h} + L_{k,h} − D_{k−1,h−1}.

Proof. We begin by unfolding the the vertices of the 2 × k grid graph, as shown in Figure 7, to give the vertices of the 1 × 2k grid graph. We then note that the central pair of vertices does not correspond to a horizontal domino in the 2 × 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 × (k − 1) grid graph with h − 1 horizontal dominoes. In Figure 8, 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}.

Jovovic [14], and Cameron and Killpatrick [8], provide the exponential generating function

L(y, z) := ∑_{k,h≥0} L_{k,h} \frac{y^{k}}{k!} z^{h} = \frac{e^{(\sqrt{1−2y} − 1)(1−z)}}{\sqrt{1 − 2y}} .

Translating the recursion relation from Theorem 4 into a differential equation for the exponential generating function, we obtain

\frac{∂E(y, 1, z)}{∂y} − (1 − z)E(y, 1, z) = \frac{∂L(y, z)}{∂y}.  (8)

L^{k,1} = + D^{k,1} = + D^{k−1,1} D^{k−1,0}

Figure 8: The relationship between the numbers, L_{k,h} and D_{k,h}, of h-horizontal-domino configurations on the 1 × 2k, and 2 × k grid graphs, respectively, is shown for the case h = 1.

This elementary, non-homogeneous, first-order ODE may be solved using an integrating factor.

Corollary 5. The exponential generating function for D_{k,h} is as follows:

E(y, 1, z) = \frac{e^{(\sqrt{1−2y} − 1)(1−z)}}{\sqrt{1 − 2y}}  (9)

− e^{(y−2)(1−z)}\sqrt{\frac{π}{2}} \sqrt{1 − z} (Erfi (\frac{(\sqrt{1 − 2y} + 1)\sqrt{1 − z}}{\sqrt{2}} ) − Erfi(\sqrt{2}\sqrt{1 − z})) ,

where we have expressed the result in terms of the imaginary error function Erfi.

Proof. The method of an integrating factor may be used to solve Equation (8).

6 Asymptotic growth and distributions

The asymptotics of the exponential generating functions E(y, w, 1) and E(y, 1, z), given in Equations (7) and (9), respectively, can be analyzed using the usual machinery of analytic combinatorics. Let V_{k} be the random variable defined as the number of vertical dominoes in a random configuration on the 2×k grid. Similarly, let H_{k} be the analogous random variable counting horizontal dominoes. The probability distribution functions V_{k,v} := P (V_{k} = v) and H_{k,h} := P (H_{k} = h) are computed as follows:

V_{k,v} = \frac{1}{(2k − 1)!!} ∑_{h≥0} D_{k,v,h}, H_{k,h} = \frac{1}{(2k − 1)!!} ∑_{v≥0} D_{k,v,h}.

Taking derivatives of E(y, w, 1) by w, we can compute the factorial moments of V_{k,v}. We note that

[y^{k}] \frac{∂^{m}E(y, w, 1)}{∂w^{m}} |_{w=1} = [y^{k}] \frac{y^{m}}{\sqrt{1 − 2y}} ∼ (\frac{1}{2})^{m} \frac{(2k − 1)!!}{k!},

where ∼ indicates asymptotic growth in k, and so the m^{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 [13] (see also Cameron and Killpatrick [8]) proved that the asymptotic factorial moments for the distribution of dominoes on the 1 × 2k grid graph are all equal to one; the case of horizontal dominoes on the 2×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 7.

We expect, in the k → ∞ limit, the occurrences of vertical and horizontal dominoes to be independent, and so the distribution P_{k,p} := P (H_{k} + 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:

P_{k,p} = \frac{1}{(2k − 1)!!} ∑_{\begin{matrix}v,h≥0 \\ v+h=p \end{matrix}} D_{k,v,h}.

The present author [1, Section 2, Theorem 1] proved that the mean of this distribution, exact in k, is given by

∑_{p≥0} p P_{k,p} = \frac{3k − 2}{2k − 1},

which gives the expected result of 3/2 in the k → ∞ 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^{11} may be used, however, to prove that, indeed,

Theorem 6.

lim_{k→∞} P_{k,p} ≃ \frac{e^{−3/2}}{p!} (\frac{3}{2})^{p} .

Proof. We begin by noting that P_{k,p} is (up to the denominator (2k − 1)!!) the coefficient of y^{k}z^{p} in D(y, z, z), i.e.

P_{k,p} =[y^{k}z^{p}] ∑_{j=0}^{∞} \frac{(2j − 1)!!}{(2k − 1)!!} \frac{y^{j} (1 − (1 − z)y)^{j}}{(1 + (1 − z)y)^{j} (1 + (1 − z)y − (1 − z)^{2}y^{2})^{j+1}}

= ∑_{j=0}^{k} \frac{(2j − 1)!!}{(2k − 1)!!}[y^{k−j}z^{p}]\frac{(1 − (1 − z)y)^{j}}{(1 + (1 − z)y)^{j} (1 + (1 − z)y − (1 − z)^{2}y^{2})^{j+1}} .

We now define the coefficients a_{j,n} as follows:

a_{j,n} := [x^{n}]\frac{(1 − x)^{j}}{(1 + x)^{j}(1 + x − x^{2})^{j+1}} .

We then have that

P_{k,p} = ∑_{j=0}^{k} \frac{(2j − 1)!!}{(2k − 1)!!}[y^{k−j}z^{p}] ∑_{n≥0} a_{j,n}(1 − z)^{n}y^{n} = ∑_{j=0}^{k} \frac{(2j − 1)!!}{(2k − 1)!!}[z^{p}]a_{j,k−j}(1 − z)^{k−j}.

11The author thanks Stephan Wagner for providing this proof.

Let P_{k}(z) be defined as follows:

P_{k}(z) := ∑_{p≥0} P_{k,p}z^{p} = ∑_{j=0}^{k} \frac{(2j − 1)!!}{(2k − 1)!!}a_{j,k−j}(1 − z)^{k−j} = ∑_{ℓ=0}^{k} \frac{(2k − 2ℓ − 1)!!}{(2k − 1)!!}a_{k−ℓ,ℓ}(1 − z)^{ℓ}.

We now proceed to prove

lim_{k→∞} P_{k}(z) = e^{3(z−1)/2},

which is equivalent to the statement of the theorem. We accomplish this by placing bounds on the a_{k−ℓ,ℓ}. Note that

a_{k−ℓ,ℓ} = [x^{ℓ}]\frac{1}{1 + x − x^{2}} (\frac{1 − x}{(1 + x)(1 + x − x^{2})})^{k−ℓ}

= (−1)^{ℓ}[x^{ℓ}]\frac{1}{1 − x − x^{2}} (\frac{1 + x}{(1 − x)(1 − x − x^{2})})^{k−ℓ} .

The following inequalities hold coefficient-by-coefficient:

1 ≤ \frac{1}{1 − x − x^{2}} ≤ \frac{1}{1 − 3x}, and 1 + 3x ≤ \frac{1 + x}{(1 − x)(1 − x − x^{2})} ≤ \frac{1}{1 − 3x}.

It then follows that

[x^{ℓ}](1 + 3x)^{k−ℓ} ≤ (−1)^{ℓ}a_{k−ℓ,ℓ} ≤ [x^{ℓ}](1 − 3x)^{−(k−ℓ+1)},

or, equivalently

3^{ℓ}\binom{k − ℓ}{ℓ} ≤ (−1)^{ℓ}a_{k−ℓ,ℓ} ≤ 3^{ℓ}\binom{k}{ℓ}.

In the k → ∞ limit these bounds become equal. In order to establish the form of P_{k}(z) in this limit, we consider

\frac{(2k − 2ℓ − 1)!!}{(2k − 1)!!}3^{ℓ}\binom{k − ℓ}{ℓ} ≤ \frac{(2k − 2ℓ − 1)!!}{(2k − 1)!!}(−1)^{ℓ}a_{k−ℓ,ℓ} ≤ \frac{(2k − 2ℓ − 1)!!}{(2k − 1)!!}3^{ℓ}\binom{k}{ℓ},

and note that the bounds in this inequality are equal to (3/2)^{ℓ}/ℓ! in the limit, thus

lim_{k→∞} \frac{(2k − 2ℓ − 1)!!}{(2k − 1)!!}(−1)^{ℓ}a_{k−ℓ,ℓ} = \frac{3^{ℓ}}{2^{ℓ}ℓ!}.

It remains to show that (the limit of) the sum in the definition of P_{k}(z) is convergent. For this we note that

|\frac{(2k − 2ℓ − 1)!!}{(2k − 1)!!}(−1)^{ℓ}a_{k−ℓ,ℓ}(z − 1)^{ℓ}| ≤ \frac{(2k − 2ℓ − 1)!!}{(2k − 1)!!}3^{ℓ}\binom{k}{ℓ} |z − 1|^{ℓ}

= \frac{3^{ℓ}|z − 1|^{ℓ}}{ℓ!} ∏_{j=0}^{ℓ−1} \frac{k − j}{2k − 2j − 1} ≤ \frac{3^{ℓ}|z − 1|^{ℓ}}{ℓ!} ,

and, further,

∑_{ℓ≥0} \frac{3^{ℓ}|z − 1|^{ℓ}}{ℓ!} = e^{3|z−1|}

is a convergent series; by dominated convergence it follows that

lim_{k→∞} P_{k}(z) = ∑_{ℓ≥0} lim_{k→∞} \frac{(2k − 2ℓ − 1)!!}{(2k − 1)!!}(−1)^{ℓ}a_{k−ℓ,ℓ}(1 − z)^{ℓ} = ∑_{ℓ≥0} \frac{3^{ℓ}}{2^{ℓ}ℓ!}(z − 1)^{ℓ} = e^{3(z−1)/2}.

7 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 6.

References

[1] D. Young, The number of domino matchings in the game of memory, J. Integer Sequences 21 (2018), Article 18.8.1.

[2] I. Terada, Brauer diagrams, updown tableaux and nilpotent matrices, J. Algebraic Combin. 14 (2001), 229–267.

[3] R. J. Marsh and P. Martin, Tiling bijections between paths and Brauer diagrams, J. Algebraic Combin. 33 (2011), 427–453.

[4] E. Krasko and A. Omelchenko, Enumeration of chord diagrams without loops and parallel chords, Electron. J. Combin. 24 (2017), Article P3.43.

[5] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009.

[6] R. Graham, D. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1994.

[7] V. Nijimbere, Analytical evaluation and asymptotic evaluation of Dawson’s integral and related functions in mathematical physics, preprint, 2017, http://arxiv.org/abs/

   1703.06757.

[8] N. Cameron and K. Killpatrick, Statistics on linear chord diagrams, preprint, 2019,

   http://arxiv.org/abs/1902.09021.

[9] J. Riordan, The enumeration of permutations with three-ply staircase restrictions, un-

    published memorandum, 1963, http://oeis.org/A001883/a001883_21.pdf.

[10] J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958.

[11] R. B. McQuistan and S. J. Lichtman, Exact recursion relation for 2 × N arrays of dumb-bells, J. Math Phys. 11 (1970), 3095–3099.

[12] A. Howroyd, http://oeis.org/A318268.

[13] G. Kreweras and Y. Poupard, Sur les partitions en paires d’un ensemble fini totalement ordonné, Publications de l’Institut de Statistique de l’Université de Paris 23 (1978), 57–74.

[14] V. Jovovic, http://oeis.org/A079267.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05C70, 60C05. Keywords: Fibonacci number, Fibonacci tree, domino tiling, perfect matching, chord diagram, Brauer diagram.

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

Received June 8 2019; revised versions received July 31 2019; December 18 2019. Published in Journal of Integer Sequences, December 27 2019.

Return to Journal of Integer Sequences home page.