Counting Tilings by Taking Walks

Given a graph \( G \), we show how to compute the number of (perfect) matchings in the graphs \( G \Box P_n \) and \( G \Box C_n \), by looking at appropriate entries in a power of a particular matrix. We give some generalizations and extensions of this result, including showing how to compute tilings of \( k \times n \) boards using monomers, dimers, and \( 2 \times 2 \) tiles.