Mutually-recursive formulas for enumerating partitions of the rectangle | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2019. № 46. DOI: 10.17223/20710410/46/9

The paper deals with the problem of enumerating the (complete) partitions of a given h × w rectangle into 1 × 2 rectangles (dominos). An algorithm is given to find a system of mutually recursive formulas enumerating all such partitions of a given rectangle of an arbitrary size. The idea is as follows. In fact, the process of finding all partitions is equivalent to the process of growing a binary tree T with vertices representing partial partitions of the given rectangle. In the former process, a descriptor means the border between the part already partitioned and the remaining part of the rectangle. Let φ(v) be the number of extensions of a partial partition v to a complete partition of the rectangle. The tree-growing process terminates as soon as the descriptor of each pendant vertex of T coincides (up to symmetry) with the descriptor of some non-pendant vertex of T . The algorithm for generating recurrence relations for calculating the number of complete partitions is based on the following: the sibling vertex y, or z, of a vertex x in the growing tree corresponds to the partial partition obtained by horizontal or vertical placement of a domino at the left upper corner of the not-yet-partitioned part of the partial partition corresponding to x. The desired recurrence relations are written upon the completion of the tree-growing process, on the base of the equation: φ(x) = φ(y) + φ(z). The main result of this paper is an algorithm for computer generation of recurrence relations, using only the operation of integer addition. Almost all previously known formulas for solutions for the problem contain floating-point operations, which require a long computation time and significant computer resources.