Замощение клетчатой полосы шириной 4
https://doi.org/10.32517/2221-1993-2022-21-1-81-84
Аннотация
Рассматривается проблема подсчета числа всевозможных покрытий клетчатого прямоугольника n×m (n строк, m столбцов) плитками размером 1×2 без пропусков и наложений. Поскольку при нечетных n и m покрытий не существует, предполагается, что хотя бы один из этих двух параметров имеет четное значение. Предлагается решение задачи о подсчете количества всевозможных покрытий плитками размером 1×2 полосы клетчатой бумаги с шириной 4 и заданной высотой. Приведен краткий обзор известных подходов к решению задачи определения числа всевозможных покрытий an при m = 2 и m = 3. В данной статье получена рекуррентная формула для вычисления an в случае m = 4. Для этого предлагается метод начальной клетки для укладки плиток, на основе которого построена система из трех рекуррентных формул для вычисления an при n >= 3 и m = 4. Затем из системы выведена одна рекуррентная формула для an.
Ключевые слова
Об авторах
А. М. МагомедовРоссия
Магомедов Абдулкарим Магомедович, доктор физико-математических наук, профессор, заведующий кафедрой дискретной математики и информатики
367000, Республика Дагестан, г. Махачкала, ул. Гаджиева, д. 43-а
Н. Ш. Раджабова
Россия
Раджабова Наима Шамильевна, кандидат физико-математических наук, доцент кафедры дискретной математики и информатики
367000, Республика Дагестан, г. Махачкала, ул. Гаджиева, д. 43-а
Список литературы
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
Рецензия
Для цитирования:
Магомедов А.М., Раджабова Н.Ш. Замощение клетчатой полосы шириной 4. Информатика в школе. 2022;(1):81-84. https://doi.org/10.32517/2221-1993-2022-21-1-81-84
For citation:
Magomedov A.M., Radzhabova N.S. 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