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

 

Logo


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. 24
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 X n 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.

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

Limit n ->infinity (a(n))^(1/n^2) = A247413 = 1.342643951124... (B. D. 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 March 27 16:36 EDT 2017. Contains 284177 sequences.