##
**
The Number of Domino Matchings in the Game of Memory
**

###
Donovan Young

St Albans, Hertfordshire

AL1 4SZ

United Kingdom

**Abstract:**

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

**
Full version: pdf,
dvi,
ps,
latex
**

(Concerned with sequences
A000045
A001883
A046741
A079267
A178523
A265167
A318243
A318244
A318267
A318268
A318269
A318270.)

Received August 2 2018; revised version received August 24 2018.
Published in *Journal of Integer Sequences*, September 30 2018.

Return to
**Journal of Integer Sequences home page**