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/

[1] Stanley R. P., Enumerative Combinatorics, v. 2, Cambridge University Press, Cambridge, 1999, 228 pp. | MR

[2] Montroll E. W., “Lattice statistics”, Applied Combinatorial Mathematics, ed. E. F. Beckenbach, John Wiley and Sons, N.Y., 1964, 96–143 | MR

[3] Karavaev A. M., Perepechko S. N., “The problem of dimers on a cylinder: recurrence relations and generating functions”, Matematicheskoe Modelirovanie, 26:11 (2014), 18–22 (in Russian) | MR | Zbl

[4] Kateleyn P. W., “The statistic of dimers on a lattice I: The number of dimer arrangements on quadratic lattice”, Physica, 27 (1961), 1209–1225 | DOI | MR

[5] Temperley H. N. V., Fisher M. E., “Dimer problem in statistical mechanics — an exact result”, Phil. Mag., 6 (1961), 1061–1063 | DOI | MR | Zbl

[6] Matoušek J., Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra, Amer. Math. Soc., 2010, 182 pp. | MR | Zbl

[7] Klarner D., Pollack J., “Domino tilings of rectangles with fixed width”, Discr. Math., 32 (1980), 45–52 | DOI | MR | Zbl

[8] Read R. C., “A note on tiling rectangles with dominoes”, Fib. Q, 18:1 (1980), 24–27 | MR | Zbl

[9] Graham R. L., Knuth D. E., Patashnik O., Concrete Mathematics, Addison-Wesley, Massachusetts, 1994, 657 pp. | MR | Zbl

[10] Graham R., Knut D., Patashnik O., Concrete Mathematics, Mir Publ., M., 1998, 703 pp. (in Russian) | MR

[11] Olympiads in Informatics, 1994

[12] Kirjuhin V. M., “[VI all-Russian Olympiad in Informatics”, Informatika i Obrazovanie, 1994, no. 3, 47–50 (in Russian)

[13] Volchenkov S. G., “Task «Tiling»”, Informatika i Obrazovanie, 1994, no. 3, 52–54 (in Russian)

[14] Magomedov A. M., Magomedov T. A., “Computer construction of recurrence formulas for partitions of the rectangle”, Proc. X Belarusian Math. Conf., November 3–7, 2008, v. 4, Institut of Mathematics NAS of Belarus, Minsk, 2008, 44 (in Russian)

[15] Albahari J., Albahari B., C# 5.0 in a Nutshell. The Definitive Reference, 5th ed., O'Reilly Media, 2012, 1064 pp.

[16] Swamy M. N., Thulasiraman K., Graphs, Networks and Algorithms, Wiley-Interscience, N.Y., 1981, 590 pp. | MR | Zbl

[17] Магомедов А. М., “Chain structures in scheduling tasks”, Prikladnaja Diskretnaja Matematika, 2016, no. 3(33), 67–77 (in Russian)

[18] Garey M. R., Jonson D. S., Computers and Intractability, Freeman and Company, San Francisco, 1979, 347 pp. | MR | Zbl

[19] Lawler E. L., Combinatorial Optimization: Networks and Matroids, Holt, Rinehart, and Winston, N.Y., 1976, 384 pp. | MR | Zbl

[20] Emelichev V. A., Mel'nikov O. I., Sarvanov V. I., Tyshkevich R. I., Lectures on Graph Theory, Librokom Publ., M., 2009, 392 pp. (in Russian) | MR