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.

  • 6
    $C(8)=250$ is correct, but $C(9)=2\left(\binom90+\binom71+\binom52\right)+1=37$. [Here's code](https://gist.github.com/2365404) 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.)2012-04-12
  • 1
    I've submitted this sequence as [OEIS sequence A182106](https://oeis.org/A182106) (it's pending review).2012-04-12
  • 0
    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.2012-04-13
  • 0
    The OEIS sequence has been approved and published.2012-04-16

1 Answers 1