Geodesic
Mutually-recursive formulas for enumerating partitions of the rectangle
Prikladnaâ diskretnaâ matematika, no. 4 (2019), pp. 108-121

Voir la notice de l'article provenant de la source Math-Net.Ru

The paper deals with the problem of enumerating the (complete) partitions of a given $h\times w$ rectangle into $1\times 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 $\varphi (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: ${\varphi (x) = \varphi (y) + \varphi (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.
Keywords: enumeration of rectangle partitions, recurrent formulas. 
@article{PDM_2019_4_a8,
     author = {A. M. Magomedov and T. A. Magomedov and S. A. Lawrencenko},
     title = {Mutually-recursive formulas for enumerating partitions of the rectangle},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {108--121},
     publisher = {mathdoc},
     number = {4},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2019_4_a8/}
}
TY  - JOUR
AU  - A. M. Magomedov
AU  - T. A. Magomedov
AU  - S. A. Lawrencenko
TI  - Mutually-recursive formulas for enumerating partitions of the rectangle
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2019
SP  - 108
EP  - 121
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2019_4_a8/
LA  - ru
ID  - PDM_2019_4_a8
ER  - 
%0 Journal Article
%A A. M. Magomedov
%A T. A. Magomedov
%A S. A. Lawrencenko
%T Mutually-recursive formulas for enumerating partitions of the rectangle
%J Prikladnaâ diskretnaâ matematika
%D 2019
%P 108-121
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2019_4_a8/
%G ru
%F PDM_2019_4_a8
A. M. Magomedov; T. A. Magomedov; S. A. Lawrencenko. Mutually-recursive formulas for enumerating partitions of the rectangle. Prikladnaâ diskretnaâ matematika, no. 4 (2019), pp. 108-121. http://geodesic.mathdoc.fr/item/PDM_2019_4_a8/