Tiling a checkered strip with a width of 4
https://doi.org/10.32517/2221-1993-2022-21-1-81-84
Abstract
The problem of calculating the number of all possible coverings of a checkered rectangle n×m (n rows, m columns) by tiles 1×2 without gaps and overlaps is considered. Since there are no coverings for odd n and m, it is assumed that at least one of these two parameters has an even value. A solution to the problem of calculating the number of various coverings with tiles of sizes 1×2 strips of checkered paper with a width of 4 and a given height is proposed. A brief overview of known approaches to solving the problem of determining the number of all possible coverings an for m = 2 and m = 3 is given. In this article, a recursive formula is obtained for calculating an in the case m = 4. For this, a method of the initial cell for laying tiles is proposed, on the basis of which a system of three recurrent formulas for calculating an for n >= 3 and m = 4 is built. Then one recurrent formula for an is deduced from the system.
About the Authors
A. M. MagomedovRussian Federation
Makhachkala, The Republic of Dagestan
N. Sh. Radzhabova
Russian Federation
Makhachkala, The Republic of Dagestan
References
1. Волченков С. Г. Задача «Паркет» // Информатика и образование. 1994. № 3. С. 52–54.
2. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М.: Мир, 1998. 703 с.
3. Канель-Белов А. Я., Ковальджи А. К. Как решают нестандартные задачи / под ред. В. О. Бугаенко. 4-е изд., стереотип. М.: МЦНМО, 2008. 96 с.
4. Караваев А. М. Метод динамического программирования для подсчета замощений домино на прямоугольной решетке и цилиндре // Актуальные проблемы гуманитарных и естественных наук. 2013. № 6 (53). С. 13–18.
5. Кирюхин В. М. VI Всероссийская олимпиада школьников по информатике // Информатика и образование. 1994. № 3. С. 47–50.
6. Магомедов А. М., Магомедов Т. А., Лавренченко С. А. Взаимно-рекуррентные формулы для перечисления разбиений прямоугольника // Прикладная дискретная математика. 2019. № 46. С. 108–121.
7. Нурлигареев Х. Д. Полоски из домино // Наука и общество. Новости науки и техники. https://ru.sciencenetnews.com/poloski-iz-domino
8. Graham R. L., Knuth D. E., Patashnik O. Concrete Mathematics. Massachusetts: Addison-Wesley, 1994. 657 p.
9. Grünbaum B., Shephard G. C. Tilings and Patterns. New York: W. H. Freeman & Co., 1987.
10. Klarner D. , Pollack J. Domino tilings of rectangles with fixed width // Discrete Mathematics, 1980. Vol. 32. P. 45–52.
11. Rao M. Exhaustive search of convex pentagons which tile the plane. https://perso.ens-lyon.fr/michael.rao/publi/penta.pdf
Review
For citations:
Magomedov A.M., Radzhabova N.Sh. Tiling a checkered strip with a width of 4. Informatics in school. 2022;(1):81-84. (In Russ.) https://doi.org/10.32517/2221-1993-2022-21-1-81-84