A063654 -id:A063654 - cp's OEIS frontend

A245013 Number A(n,k) of tilings of a k X n rectangle using 1 X 1 squares and 2 X 2 squares; 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, 5, 5, 1, 1, 1, 1, 8, 11, 11, 8, 1, 1, 1, 1, 13, 21, 35, 21, 13, 1, 1, 1, 1, 21, 43, 93, 93, 43, 21, 1, 1, 1, 1, 34, 85, 269, 314, 269, 85, 34, 1, 1, 1, 1, 55, 171, 747, 1213, 1213, 747, 171, 55, 1, 1

Offset: 0

Alois P. Heinz, Sep 16 2014

			A(3,3) = 5:
  ._._._.  .___._.  ._.___.  ._._._.  ._._._.
  |_|_|_|  |   |_|  |_|   |  |_|_|_|  |_|_|_|
  |_|_|_|  |___|_|  |_|___|  |_|   |  |   |_|
  |_|_|_|  |_|_|_|  |_|_|_|  |_|___|  |___|_| .
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,  5,  11,   21,    43,     85, ...
  1, 1,  5, 11,  35,   93,   269,    747, ...
  1, 1,  8, 21,  93,  314,  1213,   4375, ...
  1, 1, 13, 43, 269, 1213,  6427,  31387, ...
  1, 1, 21, 85, 747, 4375, 31387, 202841, ...

Liang Kai, Antidiagonals n = 0..80, flattened (antidiagonals n = 0..45 from Alois P. Heinz)
Kai Liang, Independent Set Enumeration in King Graphs by Tensor Network Contractions, arXiv:2505.12776 [math.CO], 2025. See p. 4.
R. J. Mathar, Tiling n x m rectangles with 1 x 1 and s x s squares, arXiv:1609.03964 [math.CO], 2016.
Johan Nilsson, On Counting the Number of Tilings of a Rectangle with Squares of Size 1 and 2, Journal of Integer Sequences, Vol. 20 (2017), Article 17.2.2.

Columns (or rows) k=0+1,2-10 give: A000012, A000045(n+1), A001045(n+1), A054854, A054855, A063650, A063651, A063652, A063653, A063654.

Main diagonal gives A063443.

b:= proc(n, l) option remember; local m, k; m:= min(l[]);
      if m>0 then b(n-m, map(x->x-m, l))
    elif n=0 then 1
    else for k while l[k]>0 do od; b(n, subsop(k=1, l))+
         `if`(n>1 and k `if`(min(n, k)<2, 1, b(max(n, k), [0$min(n, k)])):
seq(seq(A(n, d-n), n=0..d), d=0..14);

b[n_, l_] := b[n, l] = Module[{m=Min[l], k}, If[m>0, b[n-m, l-m], If[n == 0, 1, k=Position[l, 0, 1, 1][[1, 1]]; b[n, ReplacePart[l, k -> 1]] + If[n>1 && k 2, k+1 -> 2}]], 0]]]]; A[n_, k_] := If[Min[n, k]<2, 1, b[Max[n, k], Table[0, {Min[n, k]}]]]; Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Dec 11 2014, after Alois P. Heinz *)

A063650 Number of ways to tile a 6 X n rectangle with 1 X 1 and 2 X 2 tiles.

Original entry on oeis.org

1, 1, 13, 43, 269, 1213, 6427, 31387, 159651, 795611, 4005785, 20064827, 100764343, 505375405, 2536323145, 12724855013, 63851706457, 320373303983, 1607526474153, 8065864257905, 40471399479495, 203068825478591, 1018918472214687, 5112520236292975, 25652573037707685

Offset: 0

Reiner Martin, Jul 23 2001

nonn

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
R. J. Mathar, Tiling nXm rectangles with 1X1 and sXs squares arXiv:1609.03964 [math.CO] (2016) Section 4.1.
Index entries for linear recurrences with constant coefficients, signature (2,16,1,-27,1,4).

Cf. A001045, A054854, A054855, A063650-A063654.

Column k=6 of A245013.

I:=[1,1,13,43,269,1213]; [n le 6 select I[n] else 2*Self(n-1)+16*Self(n-2)+Self(n-3)-27*Self(n-4)+Self(n-5)+4*Self(n-6): n in [1..30]]; // Vincenzo Librandi, Oct 30 2018

LinearRecurrence[{2, 16, 1, -27, 1, 4}, {1, 1, 13, 43, 269, 1213}, 22] (* Jean-François Alcover, Oct 30 2018 *)
CoefficientList[Series[(-1+x+5*x^2-x^4)/(-1+2*x+16*x^2+x^3-27*x^4+x^5+4*x^6), {x, 0, 50}], x] (* Stefano Spezia, Oct 30 2018 *)

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

a(n) = 2a(n-1) + 16a(n-2) + a(n-3) - 27a(n-4) + a(n-5) + 4a(n-6) - Keith Schneider (kschneid(AT)bulldog.unca.edu), Apr 02 2006

A063652 Number of ways to tile an 8 X n rectangle with 1 X 1 and 2 X 2 tiles.

Original entry on oeis.org

1, 1, 34, 171, 2115, 16334, 159651, 1382259, 12727570, 113555791, 1029574631, 9258357134, 83605623809, 753361554685, 6795928721858, 61270295494859, 552555688390363, 4982395765808506, 44929655655496287, 405145692220245539, 3653405881837027898

Offset: 0

Reiner Martin, Jul 23 2001

nonn

S. Butler and S. Osborne, Counting tilings by taking walks, 2012. - From _N. J. A. Sloane_, Dec 27 2012
R. J. Mathar, Tiling nXm rectangles with 1X1 and sXs squares, arXiv:1609.03964 (2016) Section 4.1
Index entries for linear recurrences with constant coefficients, signature (6, 50, -171, -514, 1800, 845, -5430, 704, 6175, -1762, -2810, 870, 392, -120).

Cf. A001045, A054854, A054855, A063650-A063654.

Column k=8 of A245013.

a(n) = 6a(n-1) + 50a(n-2) - 171a(n-3) - 514a(n-4) + 1800a(n-5) + 845a(n-6) - 5430a(n-7) + 704a(n-8) + 6175a(n-9) - 1762a(n-10) - 2810a(n-11) + 870a(n-12) + 392a(n-13) - 120a(n-14). - Keith Schneider (kschneid(AT)bulldog.unca.edu), Apr 02 2006

G.f.: ( 1 -5*x -22*x^2 +88*x^3 +74*x^4 -378*x^5 -31*x^6 +597*x^7 -114*x^8 -336*x^9 +94*x^10 +52*x^11 -16*x^12 ) / ( 1 -6*x -50*x^2 +171*x^3 +514*x^4 -1800*x^5 -845*x^6 +5430*x^7 -704*x^8 -6175*x^9 +1762*x^10 +2810*x^11 -870*x^12 -392*x^13 +120*x^14 ). - R. J. Mathar, Dec 19 2015

A063653 Number of ways to tile a 9 X n rectangle with 1 X 1 and 2 X 2 tiles.

Original entry on oeis.org

1, 1, 55, 341, 5933, 59925, 795611, 9167119, 113555791, 1355115601, 16484061769, 198549329897, 2403674442213, 29023432116879, 350917980468767, 4239961392742933, 51247532773412135, 619304595300705203, 7484739788762129061, 90454037365096154821

Offset: 0

Reiner Martin, Jul 23 2001

nonn

a(8) is number of ways can kings be placed on an 8 X 8 chessboard so that no two kings can attack each other. - Vaclav Kotesovec, Apr 02 2010

Index entries for linear recurrences with constant coefficients, signature (6, 110, -262, -2786, 5916, 25168, -53907, -95299, 197820, 193866, -340168, -228528, 279636, 137864, -108909, -33736, 20214, 2460, -1296).

Cf. A001045, A054854, A054855, A063650, A063651, A063652, A063654.

Column k=9 of A245013.

a(n) = 6*a(n-1) + 110*a(n-2) - 262*a(n-3) - 2786*a(n-4) + 5916*a(n-5) + 25168*a(n-6) - 53907*a(n-7) - 95299*a(n-8) + 197820*a(n-9) + 193866*a(n-10) - 340168*a(n-11) - 228528*a(n-12) + 279636*a(n-13) + 137864*a(n-14) - 108909*a(n-15) - 33736*a(n-16) + 20214*a(n-17) + 2460*a(n-18) - 1296*a(n-19).

Subscripts in formula repaired by Ron Hardin, Dec 29 2010

A063651 Number of ways to tile a 7 X n rectangle with 1 X 1 and 2 X 2 tiles.

Original entry on oeis.org

1, 1, 21, 85, 747, 4375, 31387, 202841, 1382259, 9167119, 61643709, 411595537, 2758179839, 18448963469, 123518353059, 826573277157, 5532716266089, 37028886137273, 247839719105625, 1658772577825883, 11102227136885119

Offset: 0

Reiner Martin, Jul 23 2001

Index entries for linear recurrences with constant coefficients, signature (3,30,-17,-138,85,116,-42,-32).

Cf. A001045, A054854, A054855, A063650-A063654.

Column k=7 of A245013.

a(n) = 3a(n-1) + 30a(n-2) - 17a(n-3) - 138a(n-4) + 85a(n-5) + 116a(n-6) - 42a(n-7) - 32a(n-8). - Keith Schneider (kschneid(AT)bulldog.unca.edu), Apr 02 2006

G.f.: ( 1 -2*x -12*x^2 +9*x^3 +17*x^4 -6*x^5 -6*x^6 ) / ( 1 -3*x -30*x^2 +17*x^3 +138*x^4 -85*x^5 -116*x^6 +42*x^7 +32*x^8 ). - Colin Barker, Nov 29 2012

A179618 T(n,k) = Half the number of (n+1) X (k+1) 0..2 arrays with every 2 X 2 subblock diagonal sum differing from its antidiagonal sum by more than 2.

Original entry on oeis.org

5, 11, 11, 21, 35, 21, 43, 93, 93, 43, 85, 269, 314, 269, 85, 171, 747, 1213, 1213, 747, 171, 341, 2115, 4375, 6427, 4375, 2115, 341, 683, 5933, 16334, 31387, 31387, 16334, 5933, 683, 1365, 16717, 59925, 159651, 202841, 159651, 59925, 16717, 1365, 2731

Offset: 1

R. H. Hardin, Jan 10 2011

T(n,k) apparently is also the number of ways to tile an (n+2) X (k+2) rectangle with 1 X 1 and 2 X 2 tiles.

			Table starts
     5     11      21        43         85         171           341
    11     35      93       269        747        2115          5933
    21     93     314      1213       4375       16334         59925
    43    269    1213      6427      31387      159651        795611
    85    747    4375     31387     202841     1382259       9167119
   171   2115   16334    159651    1382259    12727570     113555791
   341   5933   59925    795611    9167119   113555791    1355115601
   683  16717  221799   4005785   61643709  1029574631   16484061769
  1365  47003  817280  20064827  411595537  9258357134  198549329897
  2731 132291 3018301 100764343 2758179839 83605623809 2403674442213
Some solutions for 6 X 6:
  0 2 0 2 0 2    0 1 0 2 1 2    0 2 0 2 0 2    0 1 0 2 0 1
  2 0 2 0 2 1    2 0 2 0 2 0    2 0 1 0 1 0    2 0 2 0 2 0
  0 2 0 2 0 2    1 2 1 2 0 2    0 2 0 2 0 2    0 2 0 2 0 2
  2 0 2 0 2 1    2 0 2 0 1 0    1 0 2 0 2 0    1 0 2 0 2 0
  0 2 0 2 0 2    0 2 0 2 0 2    0 2 0 2 0 2    0 2 1 2 1 2
  1 0 1 0 1 0    2 1 2 1 2 0    2 1 2 1 2 1    2 0 2 0 2 0

R. H. Hardin, Table of n, a(n) for n = 1..839

Diagonal is A063443(n+2).
Column 1 is A001045(n+3).
Column 2 is A054854(n+2).
Column 3 is A054855(n+2).
Column 4 is A063650(n+2).
Column 5 is A063651(n+2).
Column 6 is A063652(n+2).
Column 7 is A063653(n+2).
Column 8 is A063654(n+2).

cp's OEIS Frontend

A245013 Number A(n,k) of tilings of a k X n rectangle using 1 X 1 squares and 2 X 2 squares; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A063650 Number of ways to tile a 6 X n rectangle with 1 X 1 and 2 X 2 tiles.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A063652 Number of ways to tile an 8 X n rectangle with 1 X 1 and 2 X 2 tiles.

Views

Author

Keywords

Links

Crossrefs

Formula

A063653 Number of ways to tile a 9 X n rectangle with 1 X 1 and 2 X 2 tiles.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A063651 Number of ways to tile a 7 X n rectangle with 1 X 1 and 2 X 2 tiles.

Views

Author

Keywords

Links

Crossrefs

Formula

A179618 T(n,k) = Half the number of (n+1) X (k+1) 0..2 arrays with every 2 X 2 subblock diagonal sum differing from its antidiagonal sum by more than 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs