login
The OEIS is supported by the many generous donors 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. 31

%I #98 Oct 30 2022 18:19:59

%S 1,1,2,5,35,314,6427,202841,12727570,1355115601,269718819131,

%T 94707789944544,60711713670028729,69645620389200894313,

%U 144633664064386054815370,540156683236043677756331721,3641548665525780178990584908643,44222017282082621251230960522832336

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

%C 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

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

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

%H Andrew Woods and Vaclav Kotesovec and Johan Nilsson, <a href="/A063443/b063443.txt">Table of n, a(n) for n = 0..40</a> (terms 0..21 from Andrew Woods, terms 22..24 from Vaclav Kotesovec and terms 25..40 from Johan Nilsson)

%H Vaclav Kotesovec, <a href="https://oeis.org/wiki/User:Vaclav_Kotesovec">Non-attacking chess pieces</a>, 6ed, 2013, p. 68-69.

%H R. J. Mathar, <a href="http://arxiv.org/abs/1609.03964">Tiling n x m rectangles with 1 x 1 and s x s squares</a>, arXiv:1609.03964 [math.CO], 2016, Section 4.1.

%H J. Nilsson, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL20/Nilsson/nilsson15.html">On Counting the Number of Tilings of a Rectangle with Squares of Size 1 and 2</a>, Journal of Integer Sequences, Vol. 20 (2017), Article 17.2.2.

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IndependentVertexSet.html">Independent Vertex Set</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/KingGraph.html">King Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/VertexCover.html">Vertex Cover</a>

%F Lim_{n -> infinity} (a(n))^(1/n^2) = A247413 = 1.342643951124... . - _Brendan McKay_, 1996

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

%t $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_ *)

%Y Cf. A001045, A006506, A054854, A054855, A063650-A063653, A067966, etc.

%Y Cf. A045846, A211348, A247413, A201513.

%Y Cf. A212269, A067958.

%Y a(n) = row sum n-1 of A193580.

%Y Main diagonal of A245013.

%K nonn,nice,hard

%O 0,3

%A _Reiner Martin_, Jul 23 2001

%E 4 more terms from _R. H. Hardin_, Jan 23 2002

%E 2 more terms from Keith Schneider (kschneid(AT)bulldog.unca.edu), Mar 19 2006

%E 5 more terms from _Andrew Woods_, Aug 27 2011

%E a(22)-a(24) in b-file from _Vaclav Kotesovec_, May 01 2012

%E a(0) inserted by _Alois P. Heinz_, Sep 17 2014

%E a(25)-a(40) in b-file from _Johan Nilsson_, Mar 10 2016

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 18:04 EDT 2024. Contains 371254 sequences. (Running on oeis4.)