Regular structures of an intractable enumeration problem: a diagonal recurrence relation of monomer-polymer coverings on two-dimensional rectangular lattices

In the monomer-polymer model, a linear rigid polymer covers $k$ adjacent lattice sites, with no lattice site occupied by more than one polymer. The polymers are called $k$-mers, and those unoccupied lattice sites are called monomers. The well-known monomer-dimer model is a special case of the monomer-polymer model with $k=2$. The enumeration of polymer coverings on two-dimensional rectangular lattices is considered as “intractable”. We prove that the number of coverings of $s$ polymer satisfies a simple recurrence relation ${\sum }_{i=0}^{2s}(-1{)}^i\left(\genfrac{}{}{0px}{}{2s}{i}\right)a_{n-i,m-i}=2^s(2s)!\mathrm{/}s!$ on a $n\times m$ rectangular lattice with open boundary conditions in both directions.