A226545 -id:A226545 - cp's OEIS frontend

A219924 Number A(n,k) of tilings of a k X n rectangle using integer-sided square tiles; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 3, 3, 1, 1, 1, 1, 5, 6, 5, 1, 1, 1, 1, 8, 13, 13, 8, 1, 1, 1, 1, 13, 28, 40, 28, 13, 1, 1, 1, 1, 21, 60, 117, 117, 60, 21, 1, 1, 1, 1, 34, 129, 348, 472, 348, 129, 34, 1, 1, 1, 1, 55, 277, 1029, 1916, 1916, 1029, 277, 55, 1, 1

Offset: 0

Alois P. Heinz, Dec 01 2012

For drawings of A(1,1), A(2,2), ..., A(5,5) see A224239.

			A(3,3) = 6, because there are 6 tilings of a 3 X 3 rectangle using integer-sided squares:
  ._____.  ._____.  ._____.  ._____.  ._____.  ._____.
  |     |  |   |_|  |_|   |  |_|_|_|  |_|_|_|  |_|_|_|
  |     |  |___|_|  |_|___|  |_|   |  |   |_|  |_|_|_|
  |_____|  |_|_|_|  |_|_|_|  |_|___|  |___|_|  |_|_|_|
Square array A(n,k) begins:
  1,  1,  1,   1,    1,    1,     1,      1, ...
  1,  1,  1,   1,    1,    1,     1,      1, ...
  1,  1,  2,   3,    5,    8,    13,     21, ...
  1,  1,  3,   6,   13,   28,    60,    129, ...
  1,  1,  5,  13,   40,  117,   348,   1029, ...
  1,  1,  8,  28,  117,  472,  1916,   7765, ...
  1,  1, 13,  60,  348, 1916, 10668,  59257, ...
  1,  1, 21, 129, 1029, 7765, 59257, 450924, ...

Alois P. Heinz, Antidiagonals n = 0..30, flattened
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.

Columns (or rows) k=0+1, 2-10 give: A000012, A000045(n+1), A002478, A054856, A054857, A219925, A219926, A219927, A219928, A219929.
Main diagonal gives A045846.
Cf. A113881, A226545.

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, k)-> `if`(n>=k, b(n, [0$k]), b(k, [0$n])):
seq(seq(A(n, d-n), n=0..d), d=0..14);
# The following is a second version of the program that lists the actual dissections. It produces a list of pairs for each dissection:
b:= proc(n, l, ll) local i, k, s, t;
      if max(l[])>n then 0 elif n=0 or l=[] then lprint(ll); 1
    elif min(l[])>0 then t:=min(l[]); b(n-t, map(h->h-t, l), ll)
    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)],
            [ll[],[k,1+i-k]])
         od; s
      fi
    end:
A:= (n, k)-> b(k, [0$n], []):
A(5,5);
# In each list [a,b] means put a square with side length b at
leftmost possible position with upper corner in row a.  For example
[[1,3], [4,2], [4,2], [1,2], [3,1], [3,1], [4,1], [5,1]], gives:
 ___.___.
|     |   |
|     |_|
|___|_|_|
|   |   |_|
|_|___|_|

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, k = Position[l, 0, 1][[1, 1]]; 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, {j, k, i}], l[[i+1;; -1]] ] ] ]; s]]; a[n_, k_] := If[n >= k, b[n, Array[0&, k]], b[k, Array[0&, n]]]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Dec 13 2013, translated from 1st Maple program *)

A113881 Table of smallest number of squares, T(m,n), needed to tile an m X n rectangle, read by antidiagonals.

Original entry on oeis.org

1, 2, 2, 3, 1, 3, 4, 3, 3, 4, 5, 2, 1, 2, 5, 6, 4, 4, 4, 4, 6, 7, 3, 4, 1, 4, 3, 7, 8, 5, 2, 5, 5, 2, 5, 8, 9, 4, 5, 3, 1, 3, 5, 4, 9, 10, 6, 5, 5, 5, 5, 5, 5, 6, 10, 11, 5, 3, 2, 5, 1, 5, 2, 3, 5, 11, 12, 7, 6, 6, 5, 5, 5, 5, 6, 6, 7, 12, 13, 6, 6, 4, 6, 4, 1, 4, 6, 4, 6, 6, 13, 14, 8, 4, 6, 2, 3, 7, 7, 3, 2, 6, 4, 8, 14

Offset: 1

Devin Kilminster (devin(AT)27720.net), Jan 27 2006

a(n) = A338573(n) for n <= 105, as stated by R. J. Mathar. These sequences are essentially different though, because a(13433) = T(67,98) = T(98,67) = a(13464), but A338573(13433) != A338573(13464). The relationship between the tiling problem and resistor networks is remarkable. There are explanations in M. Ortolano et al., 2013. - Rainer Rosenthal, Nov 09 2020

			T(n,n) = 1 (1 n X n square).
T(n,1) = n (n 1 X 1 squares).
T(6,7) = 6 (2 3 X 3, 1 4 X 4, 1 2 X 2, 2 1 X 1).
T(11,13) = 6 (1 7 X 7, 1 6 X 6, 1 5 X 5, 2 4 X 4 1 1 X 1).
Table T(m,n) begins:
:   1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...
:   2, 1, 3, 2, 4, 3, 5, 4, 6,  5, ...
:   3, 3, 1, 4, 4, 2, 5, 5, 3,  6, ...
:   4, 2, 4, 1, 5, 3, 5, 2, 6,  4, ...
:   5, 4, 4, 5, 1, 5, 5, 5, 6,  2, ...
:   6, 3, 2, 3, 5, 1, 5, 4, 3,  4, ...
:   7, 5, 5, 5, 5, 5, 1, 7, 6,  6, ...
:   8, 4, 5, 2, 5, 4, 7, 1, 7,  5, ...
:   9, 6, 3, 6, 6, 3, 6, 7, 1,  6, ...
:  10, 5, 6, 4, 2, 4, 6, 5, 6,  1, ...

Alois P. Heinz, Antidiagonals n = 1..350, flattened (using data from A219158)
Bertram Felgenhauer, Filling rectangles with integer-sided squares
Richard J. Kenyon, Tiling a rectangle with the fewest squares, Combin. Theory Ser. A 76 (1996), no. 2, 272-291.
M. Ortolano, M. Abrate, and L. Callegaro, On the synthesis of Quantum Hall Array Resistance Standards, arXiv preprint arXiv:1311.0756 [physics.ins-det], 2013.
Mark Walters, Rectangles as sums of squares, Discrete Math. 309 (2009), no. 9, 2913-2921.

Rows (or columns) m=1-10 give: A001477, A030451, A226576, A226577, A226578, A226579, A226580, A226581, A226582, A226583.

Cf. A219158, A219924, A226545, A338573.

(* *** Warning *** This empirical toy-program is based on the greedy algorithm. Its output was only verified for n+k <= 32. Any use outside this domain might produce only upper bounds instead of minimums. *)
nmax = 31; Clear[T];
Tmin[n_, k_] := Table[{1 + T[ c, k - c] + T[n - c, k], 1 + T[n, k - c] + T[n - c, c]}, {c, 1, k - 1}] // Flatten // Min;
Tmin2[n_, k_] := Module[{n1, n2, k1, k2}, 1 + T[n2, k1 + 1] + T[n - n1, k2] + T[n - n2, k1] + T[n1, k - k1] /. {Reduce[1 <= n1 <= n - 1 && 1 <= n2 <= n - 1 && 1 <= k1 <= k - 1 && 1 <= k2 <= k - 1 && n1 + 1 + n2 == n && k1 + 1 + k2 == k, Integers] // ToRules} // Min];
T[n_, n_] = 1;
T[n_, 1] := n;
T[1, k_] := k;
T[n_, k_ /; k > 1] /; n > k && Divisible[n, k] := n/k;
T[n_, k_ /; k > 1] /; n > k := T[n, k] = If[k >= 5 && n >= 6 && n - k <= 3, Min[Tmin[n, k], Tmin2[n, k], T[k, n - k] + 1], T[k, n - k] + 1];
T[n_, k_ /; k > 1] /; n < k := T[n, k] = T[k, n];
Table[T[n - k + 1, k], {n, 1, nmax}, {k, 1, n}] // Flatten (* Jean-François Alcover, Mar 11 2016, checked against first 496 terms of the b-file *)

A226554 Number of squares in all tilings of an n X n square using integer-sided square tiles.

Original entry on oeis.org

0, 1, 5, 34, 386, 6940, 221672, 12582472, 1293374998, 242394178200, 83374069529638, 52845726291860344, 61928161880183204434, 134499571879749571406816, 542432658409586214809714176, 4068438590479352629770422328000, 56820656114941381799512710314429768

Offset: 0

Alois P. Heinz, Jun 10 2013

nonn

Main diagonal of A226545.
Row sums of A226936.
Cf. A045846.

b:= proc(n, l) option remember; local i, k, s, t;
      if max(l[])>n then [0, 0] elif n=0 or l=[] then [1, 0]
    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$2];
         for i from k to nops(l) while l[i]=0 do s:=s+(h->h+[0, h[1]])
           (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])[2]:
seq(a(n), n=0..10);

b[n_, l_] := b[n, l] = Module[{i, k, s, t},
     Which[Max[l] > n, {0, 0}, n == 0 || l == {}, {1, 0},
     Min[l] > 0, t = Min[l]; b[n - t, l - t], True,
       k = Position[l, 0, 1][[1, 1]]; s = {0, 0};
     For[i = k, i <= Length[l] && l[[i]] == 0, i++,
       s = s + Function[h, h + {0, h[[1]]}][b[n, Join[l[[1;; k-1]],
       Table[1+i-k, {j, k, i}], l[[i+1;;]]]]]]; s]];
a[n_] := b[n, Array[0&, n]][[2]];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 15}] (* Jean-François Alcover, Apr 27 2022, after Alois P. Heinz in A226545 *)

a(16) from Alois P. Heinz, Nov 16 2016

A226546 Number of squares in all tilings of a 3 X n rectangle using integer-sided square tiles.

Original entry on oeis.org

0, 3, 12, 34, 98, 256, 654, 1625, 3964, 9533, 22662, 53373, 124728, 289572, 668514, 1535869, 3513614, 8008090, 18191184, 41200568, 93064834, 209710139, 471520566, 1058065647, 2369890254, 5299215579, 11830941840, 26375563624, 58722396932, 130576680919

Offset: 0

Alois P. Heinz, Jun 10 2013

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (2,3,-2,-6,-4,-1).

Column k=3 of A226545.

Cf. A002478.

concat(0, Vec(x*(3 + 6*x + x^2) / (1 - x - 2*x^2 - x^3)^2 + O(x^30))) \\ Colin Barker, Jun 07 2020

G.f.: (x^2+6*x+3)*x/(x^3+2*x^2+x-1)^2.

a(n) = 2*a(n-1) + 3*a(n-2) - 2*a(n-3) - 6*a(n-4) - 4*a(n-5) - a(n-6) for n>5. - Colin Barker, Jun 07 2020

A226547 Number of squares in all tilings of a 4 X n rectangle using integer-sided square tiles.

Original entry on oeis.org

0, 4, 25, 98, 386, 1402, 4938, 16936, 57020, 189172, 620397, 2015456, 6496391, 20801576, 66231279, 209847980, 662049349, 2080850248, 6518383898, 20358327362, 63413001935, 197042859318, 610922240964, 1890331512546, 5838350817615, 18001432735438, 55417333344241

Offset: 0

Alois P. Heinz, Jun 10 2013

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (4,2,-12,-11,2,10,6,-1,-2,-1).

Column k=4 of A226545.

Cf. A054856.

concat(0, Vec(x*(4 + 9*x - 10*x^2 - 8*x^3 + 6*x^4 + x^5) / ((1 + x)^2*(1 - 3*x + x^4)^2) + O(x^30))) \\ Colin Barker, Jun 07 2020

G.f.: (x^5+6*x^4-8*x^3-10*x^2+9*x+4)*x/((x+1)^2*(x^4-3*x+1)^2).

a(n) = 4*a(n-1) + 2*a(n-2) - 12*a(n-3) - 11*a(n-4) + 2*a(n-5) + 10*a(n-6) + 6*a(n-7) - a(n-8) - 2*a(n-9) - a(n-10) for n>9. - Colin Barker, Jun 07 2020

A226548 Number of squares in all tilings of a 5 X n rectangle using integer-sided square tiles.

Original entry on oeis.org

0, 5, 50, 256, 1402, 6940, 33502, 157279, 725080, 3293575, 14789640, 65785991, 290341336, 1272947979, 5549535668, 24075671345, 104002776564, 447586575256, 1919810662952, 8210002538205, 35015688030978, 148980204943747, 632466650426456, 2679623444793841

Offset: 0

Alois P. Heinz, Jun 10 2013

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Column k=5 of A226545.

Cf. A054857.

G.f.: (x^10 +12*x^9 +28*x^8 +54*x^7 +33*x^6 +18*x^5 -53*x^4 -42*x^3 +6*x^2 +30*x+5)*x / (x^8 +3*x^7 +2*x^6 +5*x^5 +x^4 -6*x^3 -7*x^2 -2*x+1)^2.

A226549 Number of squares in all tilings of a 6 X n rectangle using integer-sided square tiles.

Original entry on oeis.org

0, 6, 96, 654, 4938, 33502, 221672, 1426734, 9014839, 56128696, 345447208, 2106033948, 12739126739, 76548375758, 457375097789, 2719454021744, 16100269337597, 94961606031670, 558226473615469, 3271710478901046, 19123726111508773, 111510459865449832

Offset: 0

Alois P. Heinz, Jun 10 2013

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Column k=6 of A226545.

Cf. A219925.

G.f.: (4*x^23 +60*x^22 +203*x^21 +308*x^20 -35*x^19 -660*x^18 -964*x^17 -612*x^16 +239*x^15 +344*x^14 +683*x^13 +686*x^12 +1156*x^11 +1944*x^10 -341*x^9 -2280*x^8 -1775*x^7 +588*x^6 +1550*x^5 +70*x^4 -498*x^3 -48*x^2 +60*x+6)*x / (2*x^15 +7*x^14 +12*x^13 +6*x^12 -18*x^11 -13*x^10 -8*x^9 -27*x^8 -32*x^7 +x^6 +40*x^5 +34*x^4 -3*x^3 -15*x^2 -3*x+1)^2.

A226550 Number of squares in all tilings of a 7 X n rectangle using integer-sided square tiles.

Original entry on oeis.org

0, 7, 180, 1625, 16936, 157279, 1426734, 12582472, 108971358, 929801662, 7842704798, 65526395993, 543197940936, 4473218574611, 36628689696182, 298465716569236, 2421637058537566, 19574314969125483, 157692516088571216, 1266593481935599039, 10146033357194978996

Offset: 0

Alois P. Heinz, Jun 10 2013

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Column k=7 of A226545.

Cf. A219926.

G.f.: (36*x^42 +492*x^41 +97*x^40 -1280*x^39 +1374*x^38 +3986*x^37 -3294*x^36 -12844*x^35 -17178*x^34 -5612*x^33 -8231*x^32 -68874*x^31 -38198*x^30 +87106*x^29 +79120*x^28 +342382*x^27 +1028045*x^26 +1129834*x^25 +797531*x^24 +933000*x^23 +781401*x^22 -15364*x^21 -688028*x^20 -1167490*x^19 -1199056*x^18 -495108*x^17 +175219*x^16 +637592*x^15 +810642*x^14 +590608*x^13 +255600*x^12 -62792*x^11 -226422*x^10 -130944*x^9 -26229*x^8 +21996*x^7 +25573*x^6 +5782*x^5 -3711*x^4 -1682*x^3 +174*x^2 +138*x+7)*x / (6*x^25 +11*x^24 -9*x^23 -10*x^22 +39*x^21 +12*x^20 -70*x^19 -281*x^18 -403*x^17 -110*x^16 -118*x^15 -790*x^14 -179*x^13 +466*x^12 +327*x^11 +669*x^10 +1028*x^9 +231*x^8 -45*x^7 -284*x^6 -273*x^5 -61*x^4 +45*x^3 +31*x^2 +3*x-1)^2.

A226551 Number of squares in all tilings of an 8 X n rectangle using integer-sided square tiles.

Original entry on oeis.org

0, 8, 331, 3964, 57020, 725080, 9014839, 108971358, 1293374998, 15124830042, 174840029210, 2002005705582, 22744617716405, 256690848493684, 2880580641585200, 32167728035568302, 357685528356070536, 3962274174725426092, 43745566808355289539, 481531500069734159312

Offset: 0

Alois P. Heinz, Jun 10 2013

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..500

Column k=8 of A226545.

Cf. A219927.

A226552 Number of squares in all tilings of a 9 X n rectangle using integer-sided square tiles.

Original entry on oeis.org

0, 9, 600, 9533, 189172, 3293575, 56128696, 929801662, 15124830042, 242394178200, 3840094402532, 60260456120659, 938232581234924, 14511287055938491, 223171309100257664, 3415393756038359269, 52045507693324954598, 790109733965301854764, 11954668671384269574304

Offset: 0

Alois P. Heinz, Jun 10 2013

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..500

Column k=9 of A226545.

Cf. A219928.

cp's OEIS Frontend

A219924 Number A(n,k) of tilings of a k X n rectangle using integer-sided square tiles; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A113881 Table of smallest number of squares, T(m,n), needed to tile an m X n rectangle, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A226554 Number of squares in all tilings of an n X n square using integer-sided square tiles.

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

Extensions

A226546 Number of squares in all tilings of a 3 X n rectangle using integer-sided square tiles.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A226547 Number of squares in all tilings of a 4 X n rectangle using integer-sided square tiles.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A226548 Number of squares in all tilings of a 5 X n rectangle using integer-sided square tiles.

Views

Author

Keywords

Links

Crossrefs

Formula

A226549 Number of squares in all tilings of a 6 X n rectangle using integer-sided square tiles.

Views

Author

Keywords

Links

Crossrefs

Formula

A226550 Number of squares in all tilings of a 7 X n rectangle using integer-sided square tiles.

Views

Author

Keywords

Links

Crossrefs

Formula

A226551 Number of squares in all tilings of an 8 X n rectangle using integer-sided square tiles.

Views

Author

Keywords

Links

Crossrefs

A226552 Number of squares in all tilings of a 9 X n rectangle using integer-sided square tiles.

Views

Author

Keywords