

A213658


Irregular triangle read by rows: T(n,k) is the number of dominating subsets with k vertices of the graph G(n) consisting of an edge ab and n triangles, each having one vertex identified with the vertex b.


1



1, 5, 4, 1, 1, 5, 14, 14, 6, 1, 1, 7, 21, 43, 47, 27, 8, 1, 1, 9, 36, 84, 142, 158, 108, 44, 10, 1, 1, 11, 55, 165, 330, 494, 542, 410, 205, 65, 12, 1, 1, 13, 78, 286, 715, 1287, 1780, 1908, 1527, 875, 346, 90, 14, 1, 1, 15, 105, 455, 1365, 3003, 5005
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Row n contains 2n + 2 entries.
Sum of entries in row n = 3^n + 2^{2n+1} = A213659(n).


LINKS

Table of n, a(n) for n=1..61.
S. Alikhani and E. Deutsch, Graphs with domination roots in the right halfplane, arXiv preprint arXiv:1305.3734, 2013
S. Alikhani and Y. H. Peng, Introduction to domination polynomial of a graph, arXiv:0905.2251.
T. Kotek, J. Preen, F. Simon, P. Tittmann, and M. Trinks, Recurrence relations and splitting formulas for the domination polynomial, arXiv:1206.5926.


FORMULA

Generating polynomial of row n is x^(n+1)*(2+x)^n + x*(1+x)^(2*n+1); this is the domination polynomial of the graph G(n).
T(n,k) = 2^(2*n+1k)*binom(n,kn1) + binom(2*n+1,k1) (n>=1; 1<=k<=2*n+2).


EXAMPLE

Row 1 is 1,5,4,1 because the graph G(1) is abcd with edges ab, bc, bd, and cd; there is 1 dominating subset of size 1 ({b}),; all binom(4,2)=6 subsets of size 2 of {a,b,c,d} with the exception of {c,d} are dominating; all binom(4,3)=4 subsets of size 3 of {a,b,c,d} are dominating; obviously, {a,b,c,d} is dominating.
Triangle starts:
1,5,4,1;
1,5,14,14,6,1;
1,7,21,43,47,27,8,1;


MAPLE

T := proc (n, k) options operator, arrow: 2^(2*n+1k)*binomial(n, kn1)+binomial(2*n+1, k1) end proc: for n to 8 do seq(T(n, k), k = 1 .. 2*n+2) end do; # yields sequence in triangular form


CROSSREFS

A213659
Sequence in context: A115637 A124602 A132707 * A046575 A154739 A136564
Adjacent sequences: A213655 A213656 A213657 * A213659 A213660 A213661


KEYWORD

nonn,tabf


AUTHOR

Emeric Deutsch, Jun 29 2012


STATUS

approved



