login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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, 77-82.

D. Stevanovic, Graphs with palindromic independence polynomial, Graph Theory Notes of New  York, 34, 1998, 31-36.

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 17 23:26 EST 2019. Contains 329242 sequences. (Running on oeis4.)