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

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

Table of n, a(n) for n=1..63.

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

Cf. A181565

Sequence in context: A306690 A160326 A213662 * A215596 A268676 A354762

Adjacent sequences: A213654 A213655 A213656 * A213658 A213659 A213660

Keyword

nonn,tabf

Author

Emeric Deutsch, Jun 29 2012

Status

approved