Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
$C(8)=250$ is correct, but $C(9)=2\left(\binom90+\binom71+\binom52\right)+1=37$. Here's code that computes $C(n)$ up to $n=23$. (The computation for $n=24$ didn't complete after a couple of minutes.) The first terms are $1,2,2,9,2,46,2,250,37,254,2,31052,2,1480,896,306174,2,2097506,2,6025516,6638,59‌​930,2$. (P.S.: I get a display bug in that line; the penultimate number is $59930$, without a space.) – joriki Apr 12 '12 at 7:21
I've submitted this sequence as OEIS sequence A182106 (it's pending review). – joriki Apr 12 '12 at 8:01
For small $n$ one can break this down to a calculation of the form $\pm k + 2\sum{n-2i\choose i}$ as in @joriki's $n=9$ example, but as $n$ increases this will stop working in many cases. – MJD Apr 13 '12 at 14:26
The OEIS sequence has been approved and published. – joriki Apr 16 '12 at 15:30

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 $$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.