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
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 (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

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Eric Weisstein's World of Mathematics, Connected Graph

Eric Weisstein's World of Mathematics, Induced Subgraph

Eric Weisstein's World of Mathematics, Ladder Graph

Index entries for linear recurrences with constant coefficients, signature (4, -4, 0, 1).

FORMULA

a(n) = 2a(n-1)+a(n-2)+4n-1.

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

a(n) = 3a(n-1)-a(n-2)-a(n-3)+4; a(n)=4a(n-1)-4a(n-2)+a(n-4). - Jaume Oliver Lafont, Nov 23 2008

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)-3a(n+2)-3a(n+1)+a(n) then {b(n)} is A052542 and (3) if b(n)=a(n+2)-2(a(n+1)+a(n) then {b(n)} is A001333.

a(n) = (LucasL[n+3,2]-8*n-14)/4. - Eric W. Weisstein, May 02 2017

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

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 A095109

Adjacent sequences:  A059017 A059018 A059019 * A059021 A059022 A059023

KEYWORD

nonn

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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 21 17:07 EST 2019. Contains 319350 sequences. (Running on oeis4.)