Магомедов Абдулкарим Магомедович, доктор физико-математических наук, профессор, заведующий кафедрой дискретной математики и информатики
367000, Республика Дагестан, г. Махачкала, ул. Гаджиева, д. 43-а
Makhachkala, The Republic of Dagestan
Раджабова Наима Шамильевна, кандидат физико-математических наук, доцент кафедры дискретной математики и информатики
367000, Республика Дагестан, г. Махачкала, ул. Гаджиева, д. 43-а
Makhachkala, The Republic of Dagestan
Рассматривается проблема подсчета числа всевозможных покрытий клетчатого прямоугольника 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.
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.
The authors declare that there are no conflicts of interest present.