A059020 Number of 2 X n checkerboards (with at least one red square) in which the set of red squares is edge connected.

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

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

Adjacent sequences: A059017 A059018 A059019 * A059021 A059022 A059023

Keyword

nonn,easy

Author

John W. Layman, Dec 14 2000

Status

approved