

A045846


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


22



1, 1, 2, 6, 40, 472, 10668, 450924, 35863972, 5353011036, 1500957422222, 790347882174804, 781621363452405930, 1451740730942350766748, 5064070747064013556294032, 33176273260130056822126522884, 408199838581532754602910469192704
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


LINKS

Steve Butler, Table of n, a(n) for n = 0..20
Steve Butler, Jason Ekstrand, Steven Osborne, Counting Tilings by Taking Walks in a Graph, A ProjectBased 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 nextlargest 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 nextlargest 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 nextlargest 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


FORMULA

It appears lim n>infinity a(n)*a(n3)/(a(n1)*a(n2)) = 3.527...  Gerald McGarvey, May 03 2005
It appears that lim n>infinity a(n)*a(n2)/(a(n1))^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


EXAMPLE

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).


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(nt, map(h>ht, 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..k1, 1+ik$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[nt, lt], 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 ;; k1]], Table[1+ik, {ik+1}], l[[i+1 ;; Length[l]]]]]]; s]]; a[n_] := b[n, Array[0&, n]]; Table[a[n], {n, 0, 11}] (* JeanFrançois Alcover, Feb 25 2015, after Alois P. Heinz *)


CROSSREFS

Diagonal of A219924.  Alois P. Heinz, Dec 01 2012
See A224239 for the number of inequivalent ways.
Cf. A034295, A063443, A211348, A226554.
Sequence in context: A274275 A081471 A133939 * A238818 A199574 A320489
Adjacent sequences: A045843 A045844 A045845 * A045847 A045848 A045849


KEYWORD

hard,nonn,nice


AUTHOR

Erich Friedman


EXTENSIONS

More terms from Hugo van der Sanden, Nov 06 2000
a(14)a(15) from Alois P. Heinz, Nov 30 2012
a(16)a(20) from Steve Butler, Mar 14 2014


STATUS

approved



