30
$\begingroup$

How many ways are there to tile an $n\times n$ square with exactly $n$ rectangles, each of which has integer sides and area $n$?

The sequence $C(n)$ begins 1, 2, 2, 9, 2, 46, 2, 250, 37. Clearly $C(p) = 2$ for prime $p$. The value $C(8) = 250$ was provided to me by Sjoerd Visscher, but I cannot vouch for it personally, not having seen the details of his enumeration.

OEIS was no help.

  • 0
    The OEIS sequence has been approved and published.2012-04-16

1 Answers 1

5

Sorry to poke a dead post but it was near the top of the "unanswered questions" queue for me and it's a decent problem.

Working locally should provide a good avenue of attack on this problem.

For instance, a relatively straightforward analysis (which I'll post if there is interest) yields:

$ C(p^2) = 2\left(\sum_{k=0}^{p} {p^2-k(p-1) \choose k}\right)-1 $