A219925 -id:A219925 - 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 *)

A359019 Number of inequivalent tilings of a 3 X n rectangle using integer-sided square tiles.

Original entry on oeis.org

1, 1, 2, 3, 6, 10, 21, 39, 82, 163, 347, 717, 1533, 3232, 6927, 14748, 31645, 67690, 145322, 311535, 668997, 1435645, 3083301, 6619842, 14218066, 30533005, 65580338, 140847132, 302522253, 649759735, 1395611508, 2997573501, 6438470626, 13829057884, 29703388721, 63799607283, 137035047576, 294336860797, 632205714741

Offset: 0

John Mason, Dec 12 2022

nonn

			a(4) is 6 because of:
  +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+
  | | | | |     | |   | | |   | | |   | | | | | |
  +-+-+-+ +     + +   +-+ +   +-+ +   +-+ +-+-+-+
  | | | | |     | |   | | |   | | |   | | |   | |
  +-+-+-+ +     + +-+-+-+ +-+-+-+ +-+-+-+ +   +-+
  | | | | |     | |   | | | |   | | | | | |   | |
  +-+-+-+ +-+-+-+ +   +-+ +-+   + +-+-+-+ +-+-+-+
  | | | | |     | |   | | | |   | | | | | | | | |
  +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+

John Mason, Table of n, a(n) for n = 0..1000
John Mason, Counting free tilings of a rectangle

Column k = 3 of A227690.
Sequences for fixed and free (inequivalent) tilings of m X n rectangles, for 2 <= m <= 10:
Fixed: A000045, A002478, A054856, A054857, A219925, A219926, A219927, A219928, A219929.
Free: A001224, A359019, A359020, A359021, A359022, A359023, A359024, A359025, A359026.
Cf. A000930.

For n <= 1, a(n)=1;
otherwise for odd n > 1, a(n)=(A002478(n) + A000930(n) + 2 * A002478((n - 1) / 2) + 2 * A002478((n - 3) / 2)) / 4
and for even n, a(n)=(A002478(n) + A000930(n) + 2 * A002478((n - 2) / 2) + 2 * A002478(n / 2)) / 4
Alternatively, from Walter Trump:
For n <= 1, a(n)=1;
otherwise for odd n > 1, a(n)=(A000930(2n) + A000930(n) + 2 * A000930(n - 1) + 2 * A000930(n - 3)) / 4
and for even n, a(n)=(A000930(2n) + 2 * A000930(n - 2) + 3 * A000930(n)) / 4

A359020 Number of inequivalent tilings of a 4 X n rectangle using integer-sided square tiles.

Original entry on oeis.org

1, 1, 4, 6, 13, 39, 115, 295, 861, 2403, 7048, 20377, 60008, 175978, 519589, 1532455, 4531277, 13395656, 39639758, 117301153, 347248981, 1028011708, 3043852214, 9012879842, 26689014028, 79033362580, 234045889421, 693101137571, 2052569508948

Offset: 0

John Mason, Dec 12 2022

nonn

			a(3) is 6 because of:
  +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+
  | | | | |     | |   | | |   | | |   | | | | | |
  +-+-+-+ +     + +   +-+ +   +-+ +   +-+ +-+-+-+
  | | | | |     | |   | | |   | | |   | | |   | |
  +-+-+-+ +     + +-+-+-+ +-+-+-+ +-+-+-+ +   +-+
  | | | | |     | |   | | | |   | | | | | |   | |
  +-+-+-+ +-+-+-+ +   +-+ +-+   + +-+-+-+ +-+-+-+
  | | | | |     | |   | | | |   | | | | | | | | |
  +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+

John Mason, Table of n, a(n) for n = 0..1000
John Mason, Counting free tilings of a rectangle

Column k = 4 of A227690.
Sequences for fixed and free (inequivalent) tilings of m X n rectangles, for 2 <= m <= 10:
Fixed: A000045, A002478, A054856, A054857, A219925, A219926, A219927, A219928, A219929.
Free: A001224, A359019, A359020, A359021, A359022, A359023, A359024, A359025, A359026.

For even n > 4
a(n) = (A054856(n) + compo(n) + 4 * A054856((n - 2) / 2) +
2 * A054856((n - 4) / 2) + 2 * A054856(n / 2) +
2 * Sum_{k=0..(n - 2) / 2} (A054856(k))) / 4
For odd n > 4
a(n) = (A054856(n) + compo(n) + 2 * A054856((n - 3) / 2) +
2 * A054856((n - 1) / 2) + 2 * Sum_ {k=0..(n - 3) / 2} (A054856(k))) / 4
Where compo(n) is the number of distinct compositions of n as a sum of 1, 2, (1+1) and 4.

A359021 Number of inequivalent tilings of a 5 X n rectangle using integer-sided square tiles.

Original entry on oeis.org

1, 1, 5, 10, 39, 77, 521, 1985, 8038, 32097, 130125, 525676, 2131557, 8635656, 35017970, 141968455, 575692056, 2334344849, 9465939422, 38384559168, 155652202456, 631178976378, 2559476952229, 10378857744374, 42087027204278, 170665938023137, 692062856184512

Offset: 0

John Mason, Dec 12 2022

nonn

			a(2) is 5 because of:
  +-+-+ +-+-+ +-+-+ +-+-+ +-+-+
  | | | |   | |   | |   | |   |
  +-+-+ +-+-+ +   + +   + +-+-+
  | | | |   | |   | |   | |   |
  +-+-+ +   + +-+-+ +-+-+ +   +
  | | | |   | |   | | | | |   |
  +-+-+ +-+-+ +-+-+ +-+-+ +-+-+
  | | | |   | |   | | | | | | |
  +-+-+ +   + +   + +-+-+ +-+-+
  | | | |   | |   | | | | | | |
  +-+-+ +-+-+ +-+-+ +-+-+ +-+-+

John Mason, Table of n, a(n) for n = 0..1000
John Mason, Counting tilings of width 5 rectangles

Column k = 5 of A227690.
Sequences for fixed and free (inequivalent) tilings of m X n rectangles, for 2 <= m <= 10:
Fixed: A000045, A002478, A054856, A054857, A219925, A219926, A219927, A219928, A219929.
Free: A001224, A359019, A359020, A359021, A359022, A359023, A359024, A359025, A359026.
Cf. A079975.

For even n > 5:
a(n) = (A054857(n) + A079975(n) + 2*A054857(n/2) + 2* fixed_md(n/2) + 2*A054857((n-4)/2) + 4*A054857((n-2)/2) + 2* (A054857((n/2)-1) + fixed_md((n/2)-1)))/4.
For odd n > 5:
a(n) = (A054857(n) + A079975(n) + 2*A054857((n-1)/2) + 4*A054857((n-3)/2) + 2*fixed_md((n-3)/2) + 2*A054857((n-5)/2) + 2*fixed_md((n-1)/2))/4.
where
fixed_md(1)=1, fixed_md(2)=3, fixed_md(3)=15 and for n > 3, fixed_md(n) = A054857(n-1) + A054857(n-2) + fixed_md(n-2)+ fixed_md(n-1) + 2*A054857(n-3) + fixed_md(n-3).

A359022 Number of inequivalent tilings of a 6 X n rectangle using integer-sided square tiles.

Original entry on oeis.org

1, 1, 9, 21, 115, 521, 1494, 15129, 83609, 459957, 2551794, 14150081, 78597739

Offset: 0

John Mason, Dec 12 2022

Column k = 6 of A227690.
Sequences for fixed and free (inequivalent) tilings of m X n rectangles, for 2 <= m <= 10:
Fixed: A000045, A002478, A054856, A054857, A219925, A219926, A219927, A219928, A219929.
Free: A001224, A359019, A359020, A359021, A359022, A359023, A359024, A359025, A359026.

A359023 Number of inequivalent tilings of a 7 X n rectangle using integer-sided square tiles.

Original entry on oeis.org

1, 1, 12, 39, 295, 1985, 15129, 56978, 861159, 6542578, 49828415

Offset: 0

John Mason, Dec 12 2022

Column k = 7 of A227690.
Sequences for fixed and free (inequivalent) tilings of m X n rectangles, for 2 <= m <= 10:
Fixed: A000045, A002478, A054856, A054857, A219925, A219926, A219927, A219928, A219929.
Free: A001224, A359019, A359020, A359021, A359022, A359023, A359024, A359025, A359026.

A359024 Number of inequivalent tilings of an 8 X n rectangle using integer-sided square tiles.

Original entry on oeis.org

1, 1, 21, 82, 861, 8038, 83609, 861159, 4495023

Offset: 0

John Mason, Dec 12 2022

Column k = 8 of A227690.
Sequences for fixed and free (inequivalent) tilings of m X n rectangles, for 2 <= m <= 10:
Fixed: A000045, A002478, A054856, A054857, A219925, A219926, A219927, A219928, A219929.
Free: A001224, A359019, A359020, A359021, A359022, A359023, A359024, A359025, A359026.

A359025 Number of inequivalent tilings of a 9 X n rectangle using integer-sided square tiles.

Original entry on oeis.org

1, 1, 30, 163, 2403, 32097, 459957, 6542578, 93604244

Offset: 0

John Mason, Dec 12 2022

Column k = 9 of A227690.
Sequences for fixed and free (inequivalent) tilings of m X n rectangles, for 2 <= m <= 10:
Fixed: A000045, A002478, A054856, A054857, A219925, A219926, A219927, A219928, A219929.
Free: A001224, A359019, A359020, A359021, A359022, A359023, A359024, A359025, A359026.

A359026 Number of inequivalent tilings of a 10 X n rectangle using integer-sided square tiles.

Original entry on oeis.org

1, 1, 51, 347, 7048, 130125, 2551794, 49828415

Offset: 0

John Mason, Dec 12 2022

Column k = 10 of A227690.
Sequences for fixed and free (inequivalent) tilings of m X n rectangles, for 2 <= m <= 10:
Fixed: A000045, A002478, A054856, A054857, A219925, A219926, A219927, A219928, A219929.
Free: A001224, A359019, A359020, A359021, A359022, A359023, A359024, A359025, A359026.

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.

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

A359019 Number of inequivalent tilings of a 3 X n rectangle using integer-sided square tiles.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A359020 Number of inequivalent tilings of a 4 X n rectangle using integer-sided square tiles.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A359021 Number of inequivalent tilings of a 5 X n rectangle using integer-sided square tiles.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A359022 Number of inequivalent tilings of a 6 X n rectangle using integer-sided square tiles.

Views

Author

Keywords

Crossrefs

A359023 Number of inequivalent tilings of a 7 X n rectangle using integer-sided square tiles.

Views

Author

Keywords

Crossrefs

A359024 Number of inequivalent tilings of an 8 X n rectangle using integer-sided square tiles.

Views

Author

Keywords

Crossrefs

A359025 Number of inequivalent tilings of a 9 X n rectangle using integer-sided square tiles.

Views

Author

Keywords

Crossrefs

A359026 Number of inequivalent tilings of a 10 X n rectangle using integer-sided square tiles.

Views

Author

Keywords

Crossrefs

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

Views

Author

Keywords

Links

Crossrefs

Formula