

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



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)*binomial(n,kn1) + binomial(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 binomial(4,2)=6 subsets of size 2 of {a,b,c,d} with the exception of {c,d} are dominating; all binomial(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


MATHEMATICA

row[n_] := CoefficientList[x^(n + 1)*(2 + x)^n + x*(1 + x)^(2*n + 1), x] // Rest;


PROG

(Magma) /* As triangle */ [[2^(2*n+1k)*Binomial(n, kn1) + Binomial(2*n+1, k1): k in [1..2*n+2]]: n in [1.. 15]]; // Vincenzo Librandi, Jul 21 2019


CROSSREFS



KEYWORD

nonn,tabf


AUTHOR



STATUS

approved



