A245013 -id:A245013 - 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

A054854 Number of ways to tile a 4 X n region with 1 X 1 and 2 X 2 tiles.

Original entry on oeis.org

1, 1, 5, 11, 35, 93, 269, 747, 2115, 5933, 16717, 47003, 132291, 372157, 1047181, 2946251, 8289731, 23323853, 65624397, 184640891, 519507267, 1461688413, 4112616845, 11571284395, 32557042499, 91602704493, 257733967693, 725161963867

Offset: 0

Silvia Heubach (silvi(AT)cine.net), Apr 21 2000

			a(2) = 5 as there is one tiling of a 4x2 region with only 1 X 1 tiles, 3 tilings with exactly one 2 X 2 tile and one tiling consisting of two 2 X 2 tiles.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
D. Abadie, J. Andreoli, S. Egan, T. Reddy, D. Xiong, Y. Zhao, and A. Zhu, On the Number of Tilings of a 4-By-N Rectangle with 1-By-1 and 2-By-2 Squares, Girls' Angle Bulletin, Vol. 15, No. 2 (2021), 8-12.
S. Heubach, Tiling an m-by-n area with squares of size up to k-by-k (m<=5), Congressus Numerantium 140 (1999), 43-64.
Richard M. Low and Ardak Kapbasov, Non-Attacking Bishop and King Positions on Regular and Cylindrical Chessboards, Journal of Integer Sequences, Vol. 20 (2017), Article 17.6.1, Table 7.
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.
A. Ugolnikova, Pavages Aleatories, Phd Thesis (2016) Section 2.2.3
Index entries for linear recurrences with constant coefficients, signature (2,3,-2).

Cf. A054855.

Column k=4 of A245013. First differences of A046672.

A:= Matrix([[5,1,1],[1,1,0],[1,0,1/2]]); M:= Matrix([[2,1,0],[3,0,1],[ -2,0,0]]): a:= n->(A.M^n)[2,2]: seq(a(n), n=0..50); # Alois P. Heinz, May 18 2008

f[{A_, B_}] := Module[{til = A, basic = B}, {Flatten[Append[til, ListConvolve[A, B]]], AppendTo[basic, 2]}]; NumOfTilings[n_] := Nest[f, {{1, 1}, {1, 4}}, n - 2][[1]] NumOfTilings[30]
(* Second program: *)
LinearRecurrence[{2, 3, -2}, {1, 1, 5}, 30] (* Jean-François Alcover, Jul 28 2018 *)

G.f.: (1-x)/(1-2*x-3*x^2+2*x^3). - N. J. A. Sloane, Nov 17 2002
a(n) = a(n-1)+4*a(n-2)+2*( a(n-3)+a(n-4)+...+a(0) ).
a(n) = 2*a(n-1)+3*a(n-2)-2*a(n-3). [See proofs in Mathar (a transfer matrix approach) and in Abadie et al.(direct proof).] - Keith Schneider (kschneid(AT)bulldog.unca.edu), Apr 02 2006
a(n) = Term (2,2) of matrix [5,1,1; 1,1,0; 1,0,1/2]*[2,1,0; 3,0,1; -2,0,0]^n. - Alois P. Heinz, May 18 2008
a(n) = F(n+1)^2 + Sum_{k=1..n-1} F(k)^2 * a(n-k-1), for n >= 0, where F(k) = A000045(k) (Fibonacci numbers), see Abadie, et al. - Richard S. Chang, Jan 21 2022

A054855 Number of ways to tile a 5 X n area with 1 X 1 and 2 X 2 tiles.

Original entry on oeis.org

1, 1, 8, 21, 93, 314, 1213, 4375, 16334, 59925, 221799, 817280, 3018301, 11134189, 41096528, 151643937, 559640289, 2065192514, 7621289593, 28124714395, 103789150046, 383013144129, 1413437041011, 5216013647648, 19248692843977

Offset: 0

Silvia Heubach (silvi(AT)cine.net), Apr 21 2000

			a(2)=8 as there is one tiling of a 5 X 2 area with only 1 X 1 tiles, 4 tilings with exactly one 2 X 2 tile and 3 tilings with exactly two 2 X 2 tiles.

S. Heubach, Tiling an m-by-n area with squares of size up to k-by-k (m<=5), Congressus Numerantium 140 (1999), 43-64.
R. J. Mathar, Tiling nxm rectangles with 1 X 1 and s X s squares arXiv:1609.03964 [math.CO], 2016.
Index entries for linear recurrences with constant coefficients, signature (2,7,-2,-3).

Cf. A054854, A000045.

Column k=5 of A245013.

f[{A_, B_}] := Module[{til = A, basic = B}, {Flatten[Append[til, ListConvolve[A, B]]], AppendTo[basic, 2 Fibonacci[Length[B] + 2]]}]; NumOfTilings[n_] := Nest[f, {{1, 1}, {1, 7}}, n - 2][[1]] NumOfTilings[30]

a(n) = b(1)a(n-1)+b(2)a(n-2)+...+b(n)a(0), where a(0)=a(1)=1 and b(1)=1, b(2)=7, b(n)=F(n+1)of A000045 (Fibonacci numbers) for n>2.
a(n) = 2*a(n-1) + 7*a(n-2) - 2*a(n-3) - 3*a(n-4). - Keith Schneider (kschneid(AT)bulldog.unca.edu), Apr 02 2006
G.f.: (1-x-x^2)/(1-2*x-7*x^2+2*x^3+3*x^4). [R. J. Mathar, Nov 02 2008]

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

A286849 Array read by antidiagonals: T(m,n) = number of minimal dominating sets in the n X m king graph.

Original entry on oeis.org

1, 2, 2, 2, 4, 2, 4, 6, 6, 4, 4, 16, 12, 16, 4, 7, 20, 36, 36, 20, 7, 9, 52, 64, 256, 64, 52, 9, 13, 80, 204, 400, 400, 204, 80, 13, 18, 176, 446, 2704, 971, 2704, 446, 176, 18, 25, 296, 1184, 6400, 6486, 6486, 6400, 1184, 296, 25

Offset: 1

Andrew Howroyd, Aug 01 2017

			Array begins:
===========================================================
m\n|  1   2    3     4      5       6        7         8
---|-------------------------------------------------------
1  |  1   2    2     4      4       7        9        13...
2  |  2   4    6    16     20      52       80       176...
3  |  2   6   12    36     64     204      446      1184...
4  |  4  16   36   256    400    2704     6400     30976...
5  |  4  20   64   400    971    6486    22177    112317...
6  |  7  52  204  2704   6486   85405   351503   3082745...
7  |  9  80  446  6400  22177  351503  1997448  21587536...
8  | 13 176 1184 30976 112317 3082745 21587536 360584008...
...

Andrew Howroyd, Table of n, a(n) for n = 1..153
Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Minimal Dominating Set

Rows 1-2 are A253413, A286850.
Main diagonal is A286881.
Cf. A218663 (dominating sets), A245013 (independent), A286870 (irredundant).
Cf. A286847 (grid graph).

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

A332347 Array read by antidiagonals: T(m,n) is the number of maximal independent sets in the m X n king graph.

Original entry on oeis.org

1, 2, 2, 2, 4, 2, 3, 6, 6, 3, 4, 12, 8, 12, 4, 5, 20, 22, 22, 20, 5, 7, 36, 40, 79, 40, 36, 7, 9, 64, 82, 194, 194, 82, 64, 9, 12, 112, 176, 537, 544, 537, 176, 112, 12, 16, 200, 340, 1519, 1882, 1882, 1519, 340, 200, 16, 21, 352, 722, 4011, 6490, 8197, 6490, 4011, 722, 352, 21

Offset: 1

Andrew Howroyd, Feb 10 2020

Also the number of minimal vertex covers in the m X n king graph.

			Array begins:
=====================================================
m\n | 1   2   3    4     5      6       7       8
----+------------------------------------------------
  1 | 1   2   2    3     4      5       7       9 ...
  2 | 2   4   6   12    20     36      64     112 ...
  3 | 2   6   8   22    40     82     176     340 ...
  4 | 3  12  22   79   194    537    1519    4011 ...
  5 | 4  20  40  194   544   1882    6490   20534 ...
  6 | 5  36  82  537  1882   8197   36301  144409 ...
  7 | 7  64 176 1519  6490  36301  201611 1009321 ...
  8 | 9 112 340 4011 20534 144409 1009321 6214593 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..496
Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
Eric Weisstein's World of Mathematics, Minimal Vertex Cover

Rows 1..4 are A000931(n+6), A107383(n+2), A332348, A332349.
Main diagonal is A288956.
Cf. A197054 (grid graph), A218663 (dominating sets), A245013 (independent sets), A286849 (minimal dominating sets).

T(n,m) = T(m,n).

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

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

A054854 Number of ways to tile a 4 X n region with 1 X 1 and 2 X 2 tiles.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A054855 Number of ways to tile a 5 X n area with 1 X 1 and 2 X 2 tiles.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

A286849 Array read by antidiagonals: T(m,n) = number of minimal dominating sets in the n X m king graph.

Views

Author

Keywords

Examples

Links

Crossrefs

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

A332347 Array read by antidiagonals: T(m,n) is the number of maximal independent sets in the m X n king graph.

Views

Author

Keywords

Comments

Examples

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