A286191 -id:A286191 - cp's OEIS frontend

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

John W. Layman, Dec 14 2000

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

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

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.

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

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

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

A290756 Number of (non-null) connected induced subgraphs of the complete tripartite graph K_{n,n,n}.

Original entry on oeis.org

7, 60, 499, 4062, 32689, 261972, 2096791, 16776474, 134216221, 1073738784, 8589928483, 68719464486, 549755789353, 4398046461996, 35184371990575, 281474976514098, 2251799813292085, 18014398508695608, 144115188074283067, 1152921504603701310

Offset: 1

Eric W. Weisstein, Aug 09 2017

The only disconnected induced subgraphs are those constructed from the vertices of a single partition. - Andrew Howroyd, Aug 10 2017

Eric Weisstein's World of Mathematics, Complete Tripartite Graph
Eric Weisstein's World of Mathematics, Connected Graph
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph
Index entries for linear recurrences with constant coefficients, signature (12, -37, 42, -16).

Cf. A286191.

Table[8^n - 3 2^n + 3 n + 2, {n, 20}]
LinearRecurrence[{12, -37, 42, -16}, {7, 60, 499, 4062}, 20]
CoefficientList[Series[(7 - 24 x + 38 x^2)/((-1 + x)^2 (1 - 10 x + 16 x^2)), {x, 0, 20}], x]

a(n) = 8^n - 3*2^n + 3*n + 2; \\ Andrew Howroyd, Aug 10 2017

a(n) = 8^n - 3*2^n + 3*n + 2. - Andrew Howroyd, Aug 10 2017
a(n) = 12*a(n-1) - 37*a(n-2) + 42*a(n-3) - 16*a(n-4).
G.f.: (x (7 - 24 x + 38 x^2))/((-1 + x)^2 (1 - 10 x + 16 x^2)).

a(7)-a(20) from Andrew Howroyd, Aug 10 2017

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Formula