A063650 -id:A063650 - cp's OEIS frontend

A063443 Number of ways to tile an n X n square with 1 X 1 and 2 X 2 tiles.

1, 1, 2, 5, 35, 314, 6427, 202841, 12727570, 1355115601, 269718819131, 94707789944544, 60711713670028729, 69645620389200894313, 144633664064386054815370, 540156683236043677756331721, 3641548665525780178990584908643, 44222017282082621251230960522832336

Offset: 0

Reiner Martin, Jul 23 2001

a(n) is also the number of ways to populate an n-1 X n-1 chessboard with nonattacking kings (including the case of zero kings). Cf. A193580. - Andrew Woods, Aug 27 2011

Also the number of vertex covers and independent vertex sets of the n-1 X n-1 king graph.

Steven R. Finch, Mathematical Constants, Cambridge, 2003, p. 343

Andrew Woods and Vaclav Kotesovec and Johan Nilsson, Table of n, a(n) for n = 0..40 (terms 0..21 from Andrew Woods, terms 22..24 from Vaclav Kotesovec and terms 25..40 from Johan Nilsson)
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 68-69.
R. J. Mathar, Tiling n x m rectangles with 1 x 1 and s x s squares, arXiv:1609.03964 [math.CO], 2016, Section 4.1.
J. 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.
Eric Weisstein's World of Mathematics, Independent Vertex Set
Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Vertex Cover

Cf. A001045, A006506, A054854, A054855, A063650-A063653, A067966, etc.
Cf. A045846, A211348, A247413, A201513.
Cf. A212269, A067958.
a(n) = row sum n-1 of A193580.
Main diagonal of A245013.

Needs["LinearAlgebra`MatrixManipulation`"] Remove[mat] step[sa[rules1_, {dim1_, dim1_}], sa[rules2_, {dim2_, dim2_}]] := sa[Join[rules2, rules1 /. {x_Integer, y_Integer} -> {x + dim2, y}, rules1 /. {x_Integer, y_Integer} -> {x, y + dim2}], {dim1 + dim2, dim1 + dim2}] mat[0] = sa[{{1, 1} -> 1}, {1, 1}]; mat[1] = sa[{{1, 1} -> 1, {1, 2} -> 1, {2, 1} -> 1}, {2, 2}]; mat[n_] := mat[n] = step[mat[n - 2], mat[n - 1]]; A[n_] := mat[n] /. sa -> SparseArray; F[n_] := MatrixPower[A[n], n + 1][[1, 1]]; (* Mark McClure (mcmcclur(AT)bulldog.unca.edu), Mar 19 2006 *)
$RecursionLimit = 1000; Clear[a, b]; b[n_, l_List] := 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_] := a[n] = If[n<2, 1, b[n, Table[0, {n}]]]; Table[Print[a[n]]; a[n], {n, 0, 17}] (* Jean-François Alcover, Dec 11 2014, after Alois P. Heinz *)

Lim_{n -> infinity} (a(n))^(1/n^2) = A247413 = 1.342643951124... . - Brendan McKay, 1996

4 more terms from R. H. Hardin, Jan 23 2002
2 more terms from Keith Schneider (kschneid(AT)bulldog.unca.edu), Mar 19 2006
5 more terms from Andrew Woods, Aug 27 2011
a(22)-a(24) in b-file from Vaclav Kotesovec, May 01 2012
a(0) inserted by Alois P. Heinz, Sep 17 2014
a(25)-a(40) in b-file from Johan Nilsson, Mar 10 2016

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.

Original entry on oeis.org

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

A063654 Number of ways to tile a 10 X n rectangle with 1 X 1 and 2 X 2 tiles.

Original entry on oeis.org

1, 1, 89, 683, 16717, 221799, 4005785, 61643709, 1029574631, 16484061769, 269718819131, 4364059061933, 71019435701025, 1152314664726905, 18725412666911121, 304052089851133193, 4939032362569285343

Offset: 0

Reiner Martin, Jul 23 2001

nonn

Index entries for linear recurrences with constant coefficients, signature (11, 195, -1459, -10427, 79002, 188873, -1922453, -522744, 21726132, -11085988, -137059276, 114023550, 533938164, -503739499, -1345858084, 1272444796, 2223076291, -1997887777, -2382027317, 2015253425, 1613022647, -1309632545, -660948344, 533727589, 152685069, -128889883, -17772195, 16954690, 883980, -1089264, -11392, 26112).

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

Column k=10 of A245013.

a(n) = 11a(n-1) + 195a(n-2) - 1459a(n-3) - 10427a(n-4) + 79002a(n-5) + 188873a(n-6) - 1922453a(n-7) - 522744a(n-8) + 21726132a(n-9) - 11085988a(n-10) - 137059276a(n-11) + 114023550a(n-12) + 533938164a(n-13) - 503739499a(n-14) - 1345858084a(n-15) + 1272444796a(n-16) + 2223076291a(n-17) - 1997887777a(n-18) - 2382027317a(n-19) + 2015253425a(n-20) + 1613022647a(n-21) - 1309632545a(n-22) - 660948344a(n-23) + 533727589a(n-24) + 152685069a(n-25) - 128889883a(n-26) - 17772195a(n-27) + 16954690a(n-28) + 883980a(n-29) - 1089264a(n-30) - 11392a(n-31) + 26112a(n-32) - 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

A063443 Number of ways to tile an n X n square with 1 X 1 and 2 X 2 tiles.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

A063654 Number of ways to tile a 10 X n rectangle with 1 X 1 and 2 X 2 tiles.

Views

Author

Keywords

Links

Crossrefs

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