Generating Functions for Domino Matchings in the $2\times k$ Game of Memory

Abstract

When all the elements of the multiset $\{1,1,2,2,3,3,\dots ,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 $2\times 1$ or $1\times 2$ 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.

v2, 16 pages, 8 figures, version published in the Journal of Integer Sequences

References in corpus (1)

• Tiling bijections between paths and Brauer diagrams

Cited by in corpus (1)

• Linear $k$-Chord Diagrams