login
A182106
Number of tilings of an n X n square with rectangles with integer sides and area n.
1
1, 1, 2, 2, 9, 2, 46, 2, 250, 37, 254, 2, 31052, 2, 1480, 896, 306174, 2, 2097506, 2, 6025516, 6638, 59930, 2, 22119057652, 1141, 400776, 1028162, 1205138020, 2, 188380348290, 2
OFFSET
0,3
PROG
(Java)
public class Question130758 {
final static int maxn = 23;
static int n;
static int [] divisors = new int [maxn];
static int ndivisors;
static boolean [] [] grid;
static int count;
public static void main (String [] args) {
for (n = 0; n <= maxn; n++) {
ndivisors = 0;
for (int divisor = 1; divisor <= n; divisor++)
if (n % divisor == 0)
divisors [ndivisors++] = divisor;
grid = new boolean [n] [n];
count = 0;
recurse (0, 0, 0);
System.out.print (count + ", ");
}
System.out.println ();
}
static void recurse (int x, int y, int depth) {
if (depth == n) {
count++;
return;
}
while (grid [x] [y])
if (++x == n) {
x = 0;
y++;
}
outer:
for (int k = 0; k < ndivisors; k++) {
int w = divisors [k];
int h = n / w;
if (x + w > n || y + h > n)
continue;
for (int i = 0; i < w; i++)
for (int j = 0; j < h; j++)
if (grid [x + i] [y + j])
continue outer;
for (int i = 0; i < w; i++)
for (int j = 0; j < h; j++)
grid [x + i] [y + j] = true;
recurse (x, y, depth + 1);
for (int i = 0; i < w; i++)
for (int j = 0; j < h; j++)
grid [x + i] [y + j] = false;
}
}
}
CROSSREFS
Diagonal of A220122. - Alois P. Heinz, Dec 07 2012
Sequence in context: A108462 A327859 A343824 * A308037 A011403 A113554
KEYWORD
nonn,more
AUTHOR
Felix A. Pahl, Apr 12 2012
EXTENSIONS
a(24)-a(31) from Lars Blomberg, Oct 09 2023
STATUS
approved