A213666 Irregular triangle read by rows: T(n,k) is the number of dominating subsets with k vertices of the graph G(n) obtained by taking n copies of the path P_3 and identifying one of their endpoints (a star with n branches of length 2).

1, 3, 1, 0, 3, 8, 5, 1, 0, 0, 7, 20, 18, 7, 1, 0, 0, 0, 15, 48, 56, 32, 9, 1, 0, 0, 0, 0, 31, 112, 160, 120, 50, 11, 1, 0, 0, 0, 0, 0, 63, 256, 432, 400, 220, 72, 13, 1, 0, 0, 0, 0, 0, 0, 127, 576, 1120, 1232, 840, 364, 98, 15, 1

Offset: 1

Author

Emeric Deutsch, Jul 01 2012

Keywords

• nonn
• tabf

Comments

Rows also give the coefficients of the domination polynomial of the n-helm graph (divided by x, i.e., with initial 0 dropped from rows). - Eric W. Weisstein, May 28 2017

Row n contains 2n + 1 entries (first n-1 of which are 0).

Sum of entries in row n = 2*3^{n-1} - 1 = A048473(n).

Sum of entries in column k = A213667(k).

Examples

			Row 2 is 0,3,8,5,1 because G(2) is the path P_5 abcde; no domination subset of size 1, three of size 2 (ad, bd, be), all subsets of size 3 with the exception of abc and cde are dominating (binomial(5,3)-2=8), all binomial(5,4)=5 subsets of size 4 are dominating, and abcde is dominating.
Triangle starts:
  1, 3, 1;
  0, 3, 8,  5,  1;
  0, 0, 7, 20, 18,  7,  1;
  0, 0, 0, 15, 48, 56, 32, 9, 1;
		

Links

• S. Alikhani and Y. H. Peng, Introduction to domination polynomial of a graph, arXiv:0905.2251 [math.CO], 2009.
• É. Czabarka, L. Székely, and S. Wagner, The inverse problem for certain tree parameters, Discrete Appl. Math., 157, 2009, 3314-3319.
• T. Kotek, J. Preen, F. Simon, P. Tittmann, and M. Trinks, Recurrence relations and splitting formulas for the domination polynomial, arXiv:1206.5926 [math.CO], 2012.
• Eric Weisstein's World of Mathematics, Domination Polynomial.
• Eric Weisstein's World of Mathematics, Helm Graph.

Crossrefs

Cf. A048473, A213667.

Programs

Maple

T := proc (n, k) if k = n then 2^n-1 else 2^(2*n-k)*(2*binomial(n, k-n-1) + binomial(n, k-n)) end if end proc: for n to 10 do seq(T(n, k), k = 1 .. 2*n+1) end d; # yields sequence in triangular form

Mathematica

T[n_, n_] := 2^n - 1;
T[n_, k_] := 2^(2*n - k)*(2*Binomial[n, k - n - 1] + Binomial[n, k - n]);
Table[T[n, k], {n, 1, 10}, {k, 1, 2*n + 1}] // Flatten (* Jean-François Alcover, Dec 02 2017 *)

Formula

T(n,k) = 2^(2*n-k)*(2*binomial(n,k-n-1)+binomial(n,k-n)) if k > n; T(n,n)=2^n - 1.

The generating polynomial of row n is g[n] = g[n,x] = (1+x)(x*(2+x))^n - x^n (= domination polynomial of the graph G(n)).

Bivariate g.f.: G(x,z) = x*z*(1+x)*(2+x)/(1-2*x*z-x^2*z)-x*z/(1-xz).