A235115 Number of independent vertex subsets of the graph obtained by attaching two pendant edges to each vertex of the star graph S_n (having n vertices; see A235114).

5, 24, 116, 564, 2756, 13524, 66596, 328884, 1628036, 8074644, 40111076, 199506804, 993339716, 4949921364, 24682497956, 123144054324, 614646529796, 3068937681684, 15327508539236, 76568823219444, 382569238190276, 1911746679323604, 9554335350106916, 47754084564490164, 238700054078273156

Offset

1,1

Comments

a(n) is the sum of the entries of row n of the triangle A235114.

Links

Colin Barker, Table of n, a(n) for n = 1..1000

E. Mandrescu, Unimodality of some independence polynomials via their palindromicity, Australasian J. of Combinatorics, 53, 2012, 77-82.

D. Stevanovic, Graphs with palindromic independence polynomial, Graph Theory Notes of New York, 34, 1998, 31-36.

Index entries for linear recurrences with constant coefficients, signature (9,-20).

Formula

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

G.f.: x*(5 - 21*x)/((1 - 4*x)*(1 - 5*x)).

a(n) = 9*a(n-1) - 20*a(n-2) for n>1. - Colin Barker, Jul 31 2017

Example

a(1)=5; indeed, S_1 is the one-vertex graph and after attaching two pendant vertices we obtain the path graph ABC; the independent vertex subsets are: empty, {A}, {B}, {C}, and {A,C}.

Maple

seq(4*5^(n-1)+2^(2*n-2), n = 1 .. 27);

Mathematica

Rest@ CoefficientList[Series[x (5 - 21 x)/((1 - 4 x) (1 - 5 x)), {x, 0, 25}], x] (* or *)
LinearRecurrence[{9, -20}, {5, 24}, 25] (* Michael De Vlieger, Jul 31 2017 *)

Prog

(PARI) Vec(x*(5 - 21*x) / ((1 - 4*x)*(1 - 5*x)) + O(x^30)) \\ Colin Barker, Jul 31 2017
(Magma) [4*5^(n-1)+2^(2*n-2): n in [1..25]]; // Vincenzo Librandi, Aug 01 2017

Crossrefs

Cf. A235118.

Sequence in context: A086347 A200739 A026707 * A110190 A026784 A017977

Adjacent sequences: A235112 A235113 A235114 * A235116 A235117 A235118

Keyword

nonn,easy

Author

Emeric Deutsch, Jan 13 2014

Status

approved