login
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
OFFSET
1,1
COMMENTS
Row n contain n + 2 entries.
Sum of entries in row n = 1 + 3*2^n = A181565(n).
LINKS
S. Alikhani and E. Deutsch, Graphs with domination roots in the right half-plane, 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 + 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, k-1) + binomial(n, k-2) 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, k-1)+binomial(n, k-2) 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, k-1]+Binomial[n, k-2]];
Table[T[n, k], {n, 1, 10}, {k, 1, n+2}] // Flatten (* Jean-François Alcover, Dec 09 2017 *)
CROSSREFS
Sequence in context: A306690 A160326 A213662 * A215596 A268676 A354762
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Jun 29 2012
STATUS
approved