Journal of Integer Sequences, Vol. 21 (2018), Article 18.8.1

The Number of Domino Matchings in the Game of Memory

Donovan Young
St Albans, Hertfordshire
United Kingdom


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 = 2n), what is the probability Pm,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