Generating functions for straight polyomino tilings of narrow rectangles

Abstract

Let $m,k$ be fixed positive integers. Determining the generating function for the number of tilings of an $m\times n$ rectangle by $k\times 1$ rectangles is a long-standing open problem to which the answer is only known in certain special cases. We give an explicit formula for this generating function in the case where $m<2k$. This result is used to obtain the generating function for the number of tilings of an $m\times n\times k$ box with $k\times k\times 1$ bricks.

12 pages, 9 figures, new multivariate generating functions added