

A235116


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 path graph P_n (having n vertices).


1



1, 1, 3, 1, 1, 6, 10, 6, 1, 1, 9, 28, 40, 28, 9, 1, 1, 12, 55, 128, 168, 128, 55, 12, 1, 1, 15, 91, 297, 584, 728, 584, 297, 91, 15, 1, 1, 18, 136, 574, 1519, 2672, 3216, 2672, 1519, 574, 136, 18, 1, 1, 21, 190, 986, 3297, 7553, 12272, 14400, 12272, 7553, 3297, 986, 190, 21, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Sum of entries in row n = A086347(n).
In the Maple program, P[n] gives the independence polynomial of the graph g_n.


REFERENCES

E. Mandrescu, Unimodality of some independence polynomials via their palindromicity, Australasian J. of Combinatorics, 53, 2012, 7782.
D. Stevanovic, Graphs with palindromic independence polynomial, Graph Theory Notes of New York, 34, 1998, 3136.


LINKS

Table of n, a(n) for n=0..63.


FORMULA

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*p(n  1) + x(1 + x)^2 *p(n  2); p(0)=1; p(1)=1 + 3x + x^2.
Bivariate generating polynomial: G(x,z) = (1 + xz)/(1  z(1 + xz)*(1 + x)^2).
G(1/x, x^2*z) = G(x,z) (implies that the independence polynomials of g_n are palindromic).


EXAMPLE

Row 1 is 1,3,1; indeed, S_1 is the onevertex 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}.
Triangle begins:
1;
1,3,1;
1,6,10,6,1;
1,9,28,40,28,9,1;
1,12,55,128,168,128,55,12,1;


MAPLE

G := (1+x*z)/(1z*(1+x)^2*(1+x*z)): Gser := simplify(series(G, z = 0, 12)): for n from 0 to 10 do P[n] := sort(coeff(Gser, z, n)) end do: for n from 0 to 10 do seq(coeff(P[n], x, i), i = 0 .. 2*n) end do; # yields sequence in triangular form


CROSSREFS

Cf. A086347.
Sequence in context: A123354 A120247 A235113 * A235114 A272866 A228899
Adjacent sequences: A235113 A235114 A235115 * A235117 A235118 A235119


KEYWORD

nonn,tabf


AUTHOR

Emeric Deutsch, Jan 13 2014


STATUS

approved



