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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A059020 Number of 2 X n checkerboards in which the set of red squares is edge connected. 19

%I

%S 0,3,13,40,108,275,681,1664,4040,9779,23637,57096,137876,332899,

%T 803729,1940416,4684624,11309731,27304157,65918120,159140476,

%U 384199155,927538873,2239276992,5406092952,13051462995,31509019045,76069501192

%N Number of 2 X n checkerboards in which the set of red squares is edge connected.

%C In other words, the number of connected (non-null) induced subgraphs in the n-ladder graph P_2 X P_n. - _Eric W. Weisstein_, May 02 2017

%C Also, the number of cycles in the grid graph P_3 X P_{n+1}. - _Andrew Howroyd_, Jun 12 2017

%H Vincenzo Librandi, <a href="/A059020/b059020.txt">Table of n, a(n) for n = 0..1000</a>

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

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

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

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (4,-4,0,1).

%F a(n) = 2*a(n-1) + a(n-2) + 4*n - 1.

%F a(n) = -7/2 + (7/4)*(1+sqrt(2))^n - 2*n - (5/4)*sqrt(2)*(1-sqrt(2))^n + (7/4)*(1-sqrt(2))^n + (5/4)*(1+sqrt(2))^n*sqrt(2), with n >= 0. - _Paolo P. Lava_, Jun 10 2008

%F From _Jaume Oliver Lafont_, Nov 23 2008: (Start)

%F a(n) = 3*a(n-1) - a(n-2) - a(n-3) + 4;

%F a(n) = 4*a(n-1) - 4*a(n-2) + a(n-4). (End)

%F G.f.: x*(3+x)/((1-2*x-x^2)*(1-x)^2). - _Jaume Oliver Lafont_, Sep 28 2009

%F Empirical observations (from Superseeker):

%F (1) if b(n) = a(n)+n then {b(n)} is A048777;

%F (2) if b(n) = a(n+3)-3*a(n+2)-3*a(n+1)+a(n) then {b(n)} is A052542;

%F (3) if b(n) = a(n+2)-2*(a(n+1)+a(n) then {b(n)} is A001333.

%F a(n) = (LucasL(n+3,2)-8*n-14)/4. - _Eric W. Weisstein_, May 02 2017

%F a(n) = 3*A048776(n-1) + A048776(n-2). - _R. J. Mathar_, May 12 2019

%F E.g.f.: (1/2)*exp(x)*(-7-4*x+7*cosh(sqrt(2)*x)+5*sqrt(2)*sinh(sqrt(2)*x)). - _Stefano Spezia_, Aug 25 2019

%t Join[{0},LinearRecurrence[{4, -4, 0, 1}, {3, 13, 40, 108}, 20]] (* _Eric W. Weisstein_, May 02 2017 *) (* adapted by _Vincenzo Librandi_, May 09 2017 *)

%t Table[(LucasL[n + 3, 2] - 8 n - 14)/4, {n, 0, 20}] (* _Eric W. Weisstein_, May 02 2017 *)

%o (MAGMA) I:=[0, 3, 13, 40];[n le 4 select I[n] else 4*Self(n-1) - 4*Self(n-2) + Self(n-4):n in [1..30]]; // _Marius A. Burtea_, Aug 25 2019

%Y Row 2 of A287151 and row 2 of A231829.

%Y See also A059021, A059524.

%Y Cf. A000129. - _Jaume Oliver Lafont_, Sep 28 2009

%Y Other sequences counting connected induced subgraphs: A020873, A059525, A286139, A286182, A286183, A286184, A286185, A286186, A286187, A286188, A286189, A286191, A285765, A285934, A286304.

%K nonn,easy

%O 0,2

%A _John W. Layman_, Dec 14 2000

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 16 12:41 EDT 2019. Contains 327113 sequences. (Running on oeis4.)