cp's OEIS Frontend

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

%I A182106 #21 Oct 09 2023 09:25:12
%S A182106 1,1,2,2,9,2,46,2,250,37,254,2,31052,2,1480,896,306174,2,2097506,2,
%T A182106 6025516,6638,59930,2,22119057652,1141,400776,1028162,1205138020,2,
%U A182106 188380348290,2
%N A182106 Number of tilings of an n X n square with rectangles with integer sides and area n.
%H A182106 Math StackExchange, <a href="http://math.stackexchange.com/questions/130758">Dividing a square into equal-sized rectangles</a>.
%o A182106 (Java)
%o A182106 public class Question130758 {
%o A182106     final static int maxn = 23;
%o A182106     static int n;
%o A182106     static int [] divisors = new int [maxn];
%o A182106     static int ndivisors;
%o A182106     static boolean [] [] grid;
%o A182106     static int count;
%o A182106     public static void main (String [] args) {
%o A182106         for (n = 0;n <= maxn;n++) {
%o A182106             ndivisors = 0;
%o A182106             for (int divisor = 1;divisor <= n;divisor++)
%o A182106                 if (n % divisor == 0)
%o A182106                     divisors [ndivisors++] = divisor;
%o A182106             grid = new boolean [n] [n];
%o A182106             count = 0;
%o A182106             recurse (0,0,0);
%o A182106             System.out.print (count + ",");
%o A182106         }
%o A182106         System.out.println ();
%o A182106     }
%o A182106     static void recurse (int x,int y,int depth) {
%o A182106         if (depth == n) {
%o A182106             count++;
%o A182106             return;
%o A182106         }
%o A182106         while (grid [x] [y])
%o A182106             if (++x == n) {
%o A182106                 x = 0;
%o A182106                 y++;
%o A182106             }
%o A182106         outer:
%o A182106         for (int k = 0;k < ndivisors;k++) {
%o A182106             int w = divisors [k];
%o A182106             int h = n / w;
%o A182106             if (x + w > n || y + h > n)
%o A182106                 continue;
%o A182106             for (int i = 0;i < w;i++)
%o A182106                 for (int j = 0;j < h;j++)
%o A182106                     if (grid [x + i] [y + j])
%o A182106                         continue outer;
%o A182106             for (int i = 0;i < w;i++)
%o A182106                 for (int j = 0;j < h;j++)
%o A182106                     grid [x + i] [y + j] = true;
%o A182106             recurse (x,y,depth + 1);
%o A182106             for (int i = 0;i < w;i++)
%o A182106                 for (int j = 0;j < h;j++)
%o A182106                     grid [x + i] [y + j] = false;
%o A182106         }
%o A182106     }
%o A182106 }
%Y A182106 Diagonal of A220122. - _Alois P. Heinz_, Dec 07 2012
%K A182106 nonn,more
%O A182106 0,3
%A A182106 _Felix A. Pahl_, Apr 12 2012
%E A182106 a(24)-a(31) from _Lars Blomberg_, Oct 09 2023