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, 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

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.

Links

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

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.

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 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}.
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)/(1-z*(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