A235116 - OEIS

%I #11 Feb 27 2020 22:38:34

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

%T 91,297,584,728,584,297,91,15,1,1,18,136,574,1519,2672,3216,2672,1519,

%U 574,136,18,1,1,21,190,986,3297,7553,12272,14400,12272,7553,3297,986,190,21,1

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

%C Sum of entries in row n = A086347(n).

%C In the Maple program, P[n] gives the independence polynomial of the graph g_n.

%H E. Mandrescu, <a href="http://ajc.maths.uq.edu.au/pdf/53/ajc_v53_p077.pdf">Unimodality of some independence polynomials via their palindromicity</a>, Australasian J. of Combinatorics, 53, 2012, 77-82.

%H D. Stevanovic, <a href="https://draganstevanovic.files.wordpress.com/2012/09/gtn-341998-31-36-acro6.pdf">Graphs with palindromic independence polynomial</a>, Graph Theory Notes of New York, 34, 1998, 31-36.

%F 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.

%F Bivariate generating polynomial: G(x,z) = (1 + xz)/(1 - z(1 + xz)*(1 + x)^2).

%F G(1/x, x^2*z) = G(x,z) (implies that the independence polynomials of g_n are palindromic).

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

%e Triangle begins:

%e 1;

%e 1,3,1;

%e 1,6,10,6,1;

%e 1,9,28,40,28,9,1;

%e 1,12,55,128,168,128,55,12,1;

%p 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

%Y Cf. A086347.

%K nonn,tabf

%O 0,3

%A _Emeric Deutsch_, Jan 13 2014