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,3

Comments

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.

References

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

Links

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

Formula

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

Mathematica

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<Length[l] && l[[k+1]] == 0, b[n, ReplacePart[l, {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 *)

Crossrefs

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.

Sequence in context: A000659 A164919 A272678 * A133473 A350955 A193323

Adjacent sequences: A063440 A063441 A063442 * A063444 A063445 A063446

Keyword

nonn,nice,hard

Author

Reiner Martin, Jul 23 2001

Extensions

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

Status

approved