Suppose I have an empty rectangle $R=[0,A]\times [0,B]$ with sides of integer lengths $A,B$. I want to fill $R$ with $N=6$ rectangular tiles with integer side-lengths: $a_1\times b_1$, ... $a_6\times b_6$.

Given $A,B\in\mathbb N$, how many ``combinations'' $\{(a_1,b_1),\ldots, (a_6,b_6)\}$ are admissible for such filling? (I consider a shape $a\times b$ different than the shape $b\times a$ if $a\neq b$)

For example, if $R$ is of shape $2\times 3$, it can be filled only with six square tiles $1\times 1$ big. Instead, a rectangle $R$ of size $3\times 4$ can be tiled with sizes $\{(1,2), (1,2), (1,4), (1,1), (1,1), (2,1)$ but also with the combination $\{(1,2), (1,2), (2,2), (1,1), (1,1), (2,1)\}$.

How to calculate all the possibilities in a systematic way? I hope my question is understandable! Many thanks!

  • $\begingroup$ Do you need a "closed formula", an algorithm, an asymptotic or a recurrence? $\endgroup$ – Luca Ghidelli Jul 25 '18 at 14:06

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.