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, 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

Offset: 1

Author

Emeric Deutsch, Jun 14 2012

Keywords

• nonn
• tabl

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

Examples

			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;
		

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

Crossrefs

Cf. A000213, A212634, A212635.

Programs

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

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