A235118 -id:A235118 - cp's OEIS frontend

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

Emeric Deutsch, Jan 13 2014

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

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

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

Cf. A235118.

[4*5^(n-1)+2^(2*n-2): n in [1..25]]; // Vincenzo Librandi, Aug 01 2017

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

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

Vec(x*(5 - 21*x) / ((1 - 4*x)*(1 - 5*x)) + O(x^30)) \\ Colin Barker, Jul 31 2017

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

A235117 Irregular triangle read by rows: T(n,k) = number of independent vertex subsets of size k of the graph g_n obtained by attaching two pendant edges to each vertex of the ladder graph L_n (i.e., L_n is the 2 X n grid graph; 0 <= k <= 4n+1).

Original entry on oeis.org

1, 1, 6, 10, 6, 1, 1, 12, 54, 124, 162, 124, 54, 12, 1, 1, 18, 134, 556, 1451, 2530, 3036, 2530, 1451, 556, 134, 18, 1, 1, 24, 250, 1516, 6042, 16892, 34430, 52352, 60122, 52352, 34430, 16892, 6042, 1516, 250, 24, 1, 1, 30, 402, 3220, 17393, 67676, 197588, 444584, 784702, 1098826, 1228500, 1098826, 784702, 444584, 197588, 67676, 17393, 3220, 402, 30, 1

Offset: 0

Emeric Deutsch, Jan 14 2014

Each row is palindromic (see the Stevanovic and Mandrescu references).
Row n (n >= 0) contains 4n+1 entries.
Sum of entries in row n = A235118(n).
In the Maple program, P(n) gives the independence polynomial of the graph g_n.

			Triangle begins:
1;
1,6,10,6,1;
1,12,54,124,162,124,54,12,1;
1,18,134,556,1451,2530,3036,2530,1451,556,134,18,1;

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.

Cf. A235118.

P := proc (n) option remember: if n = 0 then 1 elif n = 1 then sort(expand((1+x)^2*(1+4*x+x^2))) else sort(expand((1+x)^2*(1+3*x+x^2)*P(n-1) +x*(1+x)^6*P(n-2))) end if end proc: for n from 0 to 5 do seq(coeff(P(n), x, i), i = 0 .. 4*n) end do; # yields sequence in triangular form

Generating polynomial P(n) of row n (i.e., the independence polynomial of the graph g_n) satisfies the recurrence relation P(n) = (1 + x)^2*(1 + 3x + x^2)P(n-1) + x(1 + x)^6 *P(n-2); P(0)=1; P(1)=(1 + 4x + x^2)*(1 + x)^2.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula