A045846 Number of distinct ways to cut an n X n square into squares with integer sides.

1, 1, 2, 6, 40, 472, 10668, 450924, 35863972, 5353011036, 1500957422222, 790347882174804, 781621363452405930, 1451740730942350766748, 5064070747064013556294032, 33176273260130056822126522884, 408199838581532754602910469192704

Offset: 0

Author

Erich Friedman

Keywords

• hard
• nonn
• nice

Examples

			For n=3 the 6 dissections are: the full 3 X 3 square; 9 1 X 1 squares; one 2 X 2 square and five 1 X 1 squares (in 4 ways).
		

Links

• Andrew Gozzard and Max Ward, Table of n, a(n) for n = 0..25 (terms 0..20 from Steve Butler).
• Steve Butler, Jason Ekstrand, Steven Osborne, Counting Tilings by Taking Walks in a Graph, A Project-Based Guide to Undergraduate Research in Mathematics, Birkhäuser, Cham (2020), see page 169.
• N. J. A. Sloane, Illustration of the first five terms of A045846 and A224239, page 1 of 4 (Each dissection from A224239 is labeled with the number of its images under the symmetry group of the square. The sum of these numbers is A045846(n).)
• N. J. A. Sloane, Illustration of the first five terms of A045846 and A224239, page 2 of 4 (The largest squares are drawn in red. The next-largest squares, unless of size 1, are drawn in blue.)
• N. J. A. Sloane, Illustration of the first five terms of A045846 and A224239, page 3 of 4 (The largest squares are drawn in red. The next-largest squares, unless of size 1, are drawn in blue.)
• N. J. A. Sloane, Illustration of the first five terms of A045846 and A224239, page 4 of 4 (The largest squares are drawn in red. The next-largest squares, unless of size 1, are drawn in blue.)
• Ed Wynn, Exhaustive generation of Mrs Perkins's quilt square dissections for low orders, arXiv:1308.5420 [math.CO], 2013-2014.

Crossrefs

Diagonal of A219924. - Alois P. Heinz, Dec 01 2012

See A224239 for the number of inequivalent ways.

Cf. A034295, A063443, A211348, A226554.

Programs

Maple

b:= proc(n, l) option remember; local i, k, s, t;
      if max(l[])>n then 0 elif n=0 or l=[] then 1
    elif min(l[])>0 then t:=min(l[]); b(n-t, map(h->h-t, l))
    else for k do if l[k]=0 then break fi od; s:=0;
         for i from k to nops(l) while l[i]=0 do s:=s+
           b(n, [l[j]$j=1..k-1, 1+i-k$j=k..i, l[j]$j=i+1..nops(l)])
         od; s
      fi
    end:
a:= n-> b(n, [0$n]):
seq(a(n), n=0..11);  # Alois P. Heinz, Apr 15 2013

Mathematica

$RecursionLimit = 1000; b[n_, l_List] := b[n, l] = Module[{i, k, s, t}, Which[ Max[l]>n, 0, n == 0 || l == {}, 1, Min[l]>0, t = Min[l]; b[n-t, l-t], True, For[k = 1, True, k++, If[l[[k]] == 0, Break[]]]; s=0; For[i=k, i <= Length[l] && l[[i]] == 0, i++, s = s + b[n, Join[l[[1 ;; k-1]], Table[1+i-k, {i-k+1}], l[[i+1 ;; Length[l]]]]]]; s]]; a[n_] := b[n, Array[0&, n]]; Table[a[n], {n, 0, 11}] (* Jean-François Alcover, Feb 25 2015, after Alois P. Heinz *)

Formula

It appears lim n->oo a(n)*a(n-3)/(a(n-1)*a(n-2)) = 3.527... - Gerald McGarvey, May 03 2005

It appears that lim n->oo a(n)*a(n-2)/(a(n-1))^2 = 1.8781... - Christopher Hunt Gribble, Jun 21 2013

a(n) = (1/n^2) * Sum_{k=1..n} k^2 * A226936(n,k). - Alois P. Heinz, Jun 22 2013

Extensions

More terms from Hugo van der Sanden, Nov 06 2000

a(14)-a(15) from Alois P. Heinz, Nov 30 2012

a(16) from Steve Butler, Mar 14 2014