A288038 Number of independent vertex sets in the n-Andrásfai graph.

3, 11, 33, 89, 225, 545, 1281, 2945, 6657, 14849, 32769, 71681, 155649, 335873, 720897, 1540097, 3276801, 6946817, 14680065, 30932993, 65011713, 136314881, 285212673, 595591169, 1241513985, 2583691265, 5368709121, 11140071425, 23085449217, 47781511169

Offset

1,1

Comments

The independence polynomial is given by I(n,x) = 1+(3*n-1)*x*(x+1)^(n-1).

Links

Andrew Howroyd, Table of n, a(n) for n = 1..200

Eric Weisstein's World of Mathematics, Andrásfai Graph

Eric Weisstein's World of Mathematics, Independent Vertex Set

Index entries for linear recurrences with constant coefficients, signature (5,-8,4).

Formula

a(n) = 1 + (3*n-1)*2^(n-1).

From Colin Barker, Jun 05 2017: (Start)

G.f.: x*(3 - 4*x + 2*x^2) / ((1 - x)*(1 - 2*x)^2).

a(n) = 5*a(n-1) - 8*a(n-2) + 4*a(n-3) for n>3.

(End)

Mathematica

Table[(3 n - 1) 2^(n - 1) + 1, {n, 20}]
LinearRecurrence[{5, -8, 4}, {3, 11, 33}, 20]
CoefficientList[Series[(-3 + 4 x - 2 x^2)/((-1 + x) (-1 + 2 x)^2), {x, 0, 20}], x]

Prog

(PARI) Vec(x*(3 - 4*x + 2*x^2) / ((1 - x)*(1 - 2*x)^2) + O(x^30)) \\ Colin Barker, Jun 05 2017
(PARI) a(n) = 1 + (3*n-1)*2^(n-1); \\ Michel Marcus, Jun 05 2017

Crossrefs

Sequence in context: A131747 A295626 A079996 * A186308 A352102 A171270

Adjacent sequences: A288035 A288036 A288037 * A288039 A288040 A288041

Keyword

nonn,easy

Author

Andrew Howroyd, Jun 04 2017

Status

approved