A182106 Number of tilings of an n X n square with rectangles with integer sides and area n.

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

Author

Felix A. Pahl, Apr 12 2012

Keywords

• nonn
• more

Links

• Math StackExchange, Dividing a square into equal-sized rectangles.

Crossrefs

Diagonal of A220122. - Alois P. Heinz, Dec 07 2012

Programs

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;
        }
    }
}

Extensions

a(24)-a(31) from Lars Blomberg, Oct 09 2023