Some Properties of Direct Recurrence Relations for Sequences of Dimer Numbers
Various aspects of the problem of enumeration of all possible coverings by 1×2-tiles of a giv- en rectangle of integer dimensions, first studied by Kastelyn P.V. in 1961, remain relevant at the present time, which is explained by the demand for the problem in the applied fields of mathematics, chemistry and physics. In particular, it is equivalent to the problem of enumerative combinatorics about calculating the number of perfect matchings in grid graphs. In the proposed method of the first light cell, the enumeration of coverages is considered as the construction of a trivial binary tree, the leaves of which correspond to complete coverages, and the remaining vertices correspond to partial coverages of the original rectangle; each vertex of the tree is associated with a numerical descriptor that characterizes the boundary between the covered and the rest of the partial coverage areas corresponding to this vertex. If further generation of descendants of vertices does not lead to an update of the set of descriptors, the construction of the tree is immediately interrupted; the constructed part of a trivial tree is called a generating tree. On the basis of the generating tree, a system of mutually recurrent formulas is generated that allows transformation by the method of successive elimination to one recursive relation (direct recursion) to calculate the desired number of coverages. The article proves a number of statements about the method of the first light cell, the structure of descriptors, the system of mutually recurrent formulas; the characteristic features of direct recursion for the sequence of numbers of all possible coverings of the original rectangle are considered; specific examples show the variability of the set of its coefficients and its invariance within the system of mutually recurrent formulas; some unsolved problems are formulated.