How many ways are there to tile an n×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.
Answer
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
Attribution
Source : Link , Question Author : MJD , Answer Author : Erel Segal-Halevi
