The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
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!)
A059020 Number of 2 X n checkerboards (with at least one red square) in which the set of red squares is edge connected. 21
0, 3, 13, 40, 108, 275, 681, 1664, 4040, 9779, 23637, 57096, 137876, 332899, 803729, 1940416, 4684624, 11309731, 27304157, 65918120, 159140476, 384199155, 927538873, 2239276992, 5406092952, 13051462995, 31509019045, 76069501192, 183648021540, 443365544387 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,2
COMMENTS
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
Also, the number of cycles in the grid graph P_3 X P_{n+1}. - Andrew Howroyd, Jun 12 2017
LINKS
Eric Weisstein's World of Mathematics, Connected Graph.
Eric Weisstein's World of Mathematics, Induced Subgraph.
Eric Weisstein's World of Mathematics, Ladder Graph.
FORMULA
a(n) = 2*a(n-1) + a(n-2) + 4*n - 1.
From Jaume Oliver Lafont, Nov 23 2008: (Start)
a(n) = 3*a(n-1) - a(n-2) - a(n-3) + 4;
a(n) = 4*a(n-1) - 4*a(n-2) + a(n-4). (End)
G.f.: x*(3+x)/((1-2*x-x^2)*(1-x)^2). - Jaume Oliver Lafont, Sep 28 2009
Empirical observations (from Superseeker):
(1) if b(n) = a(n) + n then {b(n)} is A048777;
(2) if b(n) = a(n+3) - 3*a(n+2) - 3*a(n+1) + a(n) then {b(n)} is A052542;
(3) if b(n) = a(n+2) - 2*a(n+1) + a(n) then {b(n)} is A001333.
4*a(n) = A002203(n+3) - 8*n - 14. - Eric W. Weisstein, May 02 2017
a(n) = 3*A048776(n-1) + A048776(n-2). - R. J. Mathar, May 12 2019
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
MATHEMATICA
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 *)
Table[(LucasL[n + 3, 2] - 8 n - 14)/4, {n, 0, 20}] (* Eric W. Weisstein, May 02 2017 *)
PROG
(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
CROSSREFS
Row 2 of A287151 and row 2 of A231829.
See also A059021, A059524.
Cf. A000129. - Jaume Oliver Lafont, Sep 28 2009
Other sequences counting connected induced subgraphs: A020873, A059525, A286139, A286182, A286183, A286184, A286185, A286186, A286187, A286188, A286189, A286191, A285765, A285934, A286304.
Sequence in context: A147042 A018492 A227446 * A290720 A289654 A360787
KEYWORD
nonn,easy
AUTHOR
John W. Layman, Dec 14 2000
STATUS
approved

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 June 17 23:38 EDT 2024. Contains 373468 sequences. (Running on oeis4.)