29
$\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.

$\endgroup$
  • 6
    $\begingroup$ $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,59930,2$. (P.S.: I get a display bug in that line; the penultimate number is $59930$, without a space.) $\endgroup$ – joriki Apr 12 '12 at 7:21
  • 1
    $\begingroup$ I've submitted this sequence as OEIS sequence A182106 (it's pending review). $\endgroup$ – joriki Apr 12 '12 at 8:01
  • $\begingroup$ 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. $\endgroup$ – MJD Apr 13 '12 at 14:26
  • $\begingroup$ The OEIS sequence has been approved and published. $\endgroup$ – joriki Apr 16 '12 at 15:30
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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