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

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

Author

Emeric Deutsch, Jan 14 2014

Keywords

• nonn
• tabf

Comments

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.

Examples

			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;
		

Links

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

Crossrefs

Cf. A235118.

Programs

Maple

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

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*(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.