login
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
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,2
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).
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.
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).
EXAMPLE
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;
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 *)
CROSSREFS
Sequence in context: A067882 A215771 A110033 * A166407 A285123 A159059
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Jul 01 2012
STATUS
approved