

A212633


Triangle read by rows: T(n,k) is the number of dominating subsets with cardinality k of the path tree P_n (n>=1, 1<=k<=n).


1



1, 2, 1, 1, 3, 1, 0, 4, 4, 1, 0, 3, 8, 5, 1, 0, 1, 10, 13, 6, 1, 0, 0, 8, 22, 19, 7, 1, 0, 0, 4, 26, 40, 26, 8, 1, 0, 0, 1, 22, 61, 65, 34, 9, 1, 0, 0, 0, 13, 70, 120, 98, 43, 10, 1, 0, 0, 0, 5, 61, 171, 211, 140, 53, 11, 1, 0, 0, 0, 1, 40, 192, 356, 343, 192, 64, 12, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

The entries in row n are the coefficients of the domination polynomial of the path P_n (see the Alikhani and Peng reference).
Sum of entries in row n = A000213(n+1) (number of dominating subsets; tribonacci numbers).


REFERENCES

S. Alikhani and Y. H. Peng, Dominating sets and domination polynomials of paths, International J. Math. and Math. Sci., Vol. 2009, Article ID542040.


LINKS



FORMULA

If p(n)=p(n,x) denotes the generating polynomial of row n (called the domination polynomial of the path tree P_n), then p(1)=x, p(2) = 2x + x^2, p(3) = x + 3x^2 + x^3 and p(n) = x*[p(n1) + p(n2) + p(n3)] for n>=4 (see Eq. (3.2) in the Alikhani & Peng journal reference).


EXAMPLE

Row 3 is [1,3,1] because the path tree ABC has dominating subsets B, AB, BC, AC, and ABC.
Triangle starts:
1;
2,1;
1,3,1;
0,4,4,1;
0,3,8,5,1;


MAPLE

p := proc (n) option remember; if n = 1 then x elif n = 2 then x^2+2*x elif n = 3 then x^3+3*x^2+x else sort(expand(x*(p(n1)+p(n2)+p(n3)))) end if end proc: for n to 15 do seq(coeff(p(n), x, k), k = 1 .. n) end do; # yields sequence in triangular form


MATHEMATICA

p[1] = x; p[2] = 2*x + x^2; p[3] = x + 3*x^2 + x^3; p[n_] := p[n] = x*(p[n  1] + p[n  2] + p[n  3]); row[n_] := CoefficientList[p[n], x] // Rest;
CoefficientList[LinearRecurrence[{x, x, x}, {1, 2 + x, 1 + 3 x + x^2}, 10], x] // Flatten (* Eric W. Weisstein, Apr 07 2017 *)


CROSSREFS



KEYWORD



AUTHOR



STATUS

approved



