Journal of Integer Sequences, Vol. 22 (2019), Article 19.8.7

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

Donovan Young
St Albans, Hertfordshire AL1 4SZ
United Kingdom


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.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000045 A001883 A046741 A055140 A079267 A178523 A265167 A318243 A318244 A318267 A318268 A318269 A318270 A325753 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