cp's OEIS Frontend

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

%I A045846 #80 Jan 13 2024 13:07:26
%S A045846 1,1,2,6,40,472,10668,450924,35863972,5353011036,1500957422222,
%T A045846 790347882174804,781621363452405930,1451740730942350766748,
%U A045846 5064070747064013556294032,33176273260130056822126522884,408199838581532754602910469192704
%N A045846 Number of distinct ways to cut an n X n square into squares with integer sides.
%H A045846 Andrew Gozzard and Max Ward, <a href="/A045846/b045846.txt">Table of n, a(n) for n = 0..25</a> (terms 0..20 from Steve Butler).
%H A045846 Steve Butler, Jason Ekstrand, Steven Osborne, <a href="https://doi.org/10.1007/978-3-030-37853-0_5">Counting Tilings by Taking Walks in a Graph</a>, A Project-Based Guide to Undergraduate Research in Mathematics, Birkhäuser, Cham (2020), see page 169.
%H A045846 N. J. A. Sloane, <a href="/A224239/a224239_4.jpg">Illustration of the first five terms of A045846 and A224239, page 1 of 4</a> (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).)
%H A045846 N. J. A. Sloane, <a href="/A224239/a224239_5.jpg">Illustration of the first five terms of A045846 and A224239, page 2 of 4</a> (The largest squares are drawn in red. The next-largest squares, unless of size 1, are drawn in blue.)
%H A045846 N. J. A. Sloane, <a href="/A224239/a224239_6.jpg">Illustration of the first five terms of A045846 and A224239, page 3 of 4</a> (The largest squares are drawn in red. The next-largest squares, unless of size 1, are drawn in blue.)
%H A045846 N. J. A. Sloane, <a href="/A224239/a224239_7.jpg">Illustration of the first five terms of A045846 and A224239, page 4 of 4</a> (The largest squares are drawn in red. The next-largest squares, unless of size 1, are drawn in blue.)
%H A045846 Ed Wynn, <a href="http://arxiv.org/abs/1308.5420">Exhaustive generation of Mrs Perkins's quilt square dissections for low orders</a>, arXiv:1308.5420 [math.CO], 2013-2014.
%F A045846 It appears lim n->oo a(n)*a(n-3)/(a(n-1)*a(n-2)) = 3.527... - _Gerald McGarvey_, May 03 2005
%F A045846 It appears that lim n->oo a(n)*a(n-2)/(a(n-1))^2 = 1.8781... - _Christopher Hunt Gribble_, Jun 21 2013
%F A045846 a(n) = (1/n^2) * Sum_{k=1..n} k^2 * A226936(n,k). - _Alois P. Heinz_, Jun 22 2013
%e A045846 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).
%p A045846 b:= proc(n, l) option remember; local i, k, s, t;
%p A045846       if max(l[])>n then 0 elif n=0 or l=[] then 1
%p A045846     elif min(l[])>0 then t:=min(l[]); b(n-t, map(h->h-t, l))
%p A045846     else for k do if l[k]=0 then break fi od; s:=0;
%p A045846          for i from k to nops(l) while l[i]=0 do s:=s+
%p A045846            b(n, [l[j]$j=1..k-1, 1+i-k$j=k..i, l[j]$j=i+1..nops(l)])
%p A045846          od; s
%p A045846       fi
%p A045846     end:
%p A045846 a:= n-> b(n, [0$n]):
%p A045846 seq(a(n), n=0..11);  # _Alois P. Heinz_, Apr 15 2013
%t A045846 $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_ *)
%Y A045846 Diagonal of A219924. - _Alois P. Heinz_, Dec 01 2012
%Y A045846 See A224239 for the number of inequivalent ways.
%Y A045846 Cf. A034295, A063443, A211348, A226554.
%K A045846 hard,nonn,nice
%O A045846 0,3
%A A045846 _Erich Friedman_
%E A045846 More terms from _Hugo van der Sanden_, Nov 06 2000
%E A045846 a(14)-a(15) from _Alois P. Heinz_, Nov 30 2012
%E A045846 a(16) from _Steve Butler_, Mar 14 2014