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
KEYWORD
nonn,easy
AUTHOR
Emeric Deutsch, Jan 13 2014
STATUS
approved