

A213657


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, n vertices c_1, c_2, ..., c_n, and 2n edges ac_i, bc_i (i=1..n). (n triangles with a common edge).


0



3, 3, 1, 2, 6, 4, 1, 2, 7, 10, 5, 1, 2, 9, 16, 15, 6, 1, 2, 11, 25, 30, 21, 7, 1, 2, 13, 36, 55, 50, 28, 8, 1, 2, 15, 49, 91, 105, 77, 36, 9, 1, 2, 17, 64, 140, 196, 182, 112, 45, 10, 1, 2, 19, 81, 204, 336, 378, 294, 156, 55, 11, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

Row n contain n + 2 entries.
Sum of entries in row n = 1 + 3*2^n = A181565(n).


LINKS



FORMULA

Generating polynomial of row n is x^n + x*(2+x)*(1+x)^n; this is the domination polynomial of the graph G(n).
T(n,n) = (n+1)*(n+3)/2; T(n,k) = 2*binomial(n, k1) + binomial(n, k2) if k != n.


EXAMPLE

Row 1 is 3,3,1 because the graph G(1) is the triangle abc; there are 3 dominating subsets of size 1 ({a}, {b}, {c}), 3 dominating subsets of size 2 ({a,b}, {a,c}, {b,c}), and 1 dominating subset of size 3 ({a,b,c}).
T(n,1)=2 for n >= 2 because {a} and {b} are the only dominating subsets of size k=1.
Triangle starts:
3, 3, 1;
2, 6, 4, 1;
2, 7, 10, 5, 1;
2, 9, 16, 15, 6, 1;


MAPLE

T := proc (n, k) if k = n then (1/2)*(n+1)*(n+2) else 2*binomial(n, k1)+binomial(n, k2) end if end proc: for n to 12 do seq(T(n, k), k = 1 .. n+2) end do; # yields sequence in triangular form


MATHEMATICA

T[n_, k_] := If[k==n, (n+1)*(n+2)/2, 2*Binomial[n, k1]+Binomial[n, k2]];


CROSSREFS



KEYWORD

nonn,tabf


AUTHOR



STATUS

approved



