Tiling a checkered strip with a width of 4
Абдулкарим Магомедович Магомедов, N. Sh. Radzhabova · Informatics in school · 2022
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 a n for m = 2 and m = 3 is given. In this article, a recursive formula is obtained for calculating a n 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 a n for n >= 3 and m = 4 is built. Then one recurrent formula for an is deduced from the system.