login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A063443 Number of ways to tile an n X n square with 1 X 1 and 2 X 2 tiles. 26
1, 1, 2, 5, 35, 314, 6427, 202841, 12727570, 1355115601, 269718819131, 94707789944544, 60711713670028729, 69645620389200894313, 144633664064386054815370, 540156683236043677756331721, 3641548665525780178990584908643, 44222017282082621251230960522832336 (list; graph; refs; listen; history; text; internal format)
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)

V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 68-69.

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 A193323 A238752

Adjacent sequences:  A063440 A063441 A063442 * A063444 A063445 A063446

KEYWORD

nonn,nice,hard

AUTHOR

Reiner Martin (reinermartin(AT)hotmail.com), 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 23 21:46 EST 2017. Contains 295141 sequences.