Problem:
A rectangular pavement is to be covered by tiles which are either green or yellow, each of width and of varying integer lengths from to . Suppose you have an unlimited supply of tiles for each color and for each of the varying lengths. How many distinct tilings of the rectangle are there, if at least one green and one yellow tile should be used, and adjacent tiles should have different colors?
Solution:
Note that the pavement is fixed and cannot be rotated, therefore a tiling is considered distinct from the reverse tiling. Also, note that the restriction that no two consecutive tiles can be of the same color can be addressed simply by treating consecutive tiles of the same color as one tile. Hence, the problem is just asking for the number of possible tilings that alternate both colors. For any division of the board into tiles, there are precisely two ways to color the tiles, as the coloring is determined solely by the color of the first tile. Now, to count the uncolored tilings, we divide the board into squares using dividers, and just count the number of subsets of the dividers with at least one element. There are exactly such subsets, and thus such colorings.