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
Alois P. Heinz, Rows n = 1..141, flattened
S. Alikhani and Y. H. Peng, Introduction to domination polynomial of a graph, arXiv:0905.2251.
JL Arocha, B Llano, The number of dominating k-sets of paths, cycles and wheels, arXiv preprint arXiv:1601.01268, 2016
Eric Weisstein's World of Mathematics, Domination Polynomial
Eric Weisstein's World of Mathematics, Path Graph
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(n-1) + p(n-2) + p(n-3)] for n>=4 (see Eq. (3.2) in the Alikhani & Peng journal reference).
EXAMPLE
Row 3 is [1,3,1] because the path tree A-B-C 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(n-1)+p(n-2)+p(n-3)))) 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;
Array[row, 15] // Flatten (* Jean-François Alcover, Feb 24 2016 *)
CoefficientList[LinearRecurrence[{x, x, x}, {1, 2 + x, 1 + 3 x + x^2}, 10], x] // Flatten (* Eric W. Weisstein, Apr 07 2017 *)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Jun 14 2012
STATUS
approved