|
%I #21 Apr 07 2017 21:38:52
%S 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,
%T 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,
%U 61,171,211,140,53,11,1,0,0,0,1,40,192,356,343,192,64,12,1
%N 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).
%C The entries in row n are the coefficients of the domination polynomial of the path P_n (see the Alikhani and Peng reference).
%C Sum of entries in row n = A000213(n+1) (number of dominating subsets; tribonacci numbers).
%D S. Alikhani and Y. H. Peng, Dominating sets and domination polynomials of paths, International J. Math. and Math. Sci., Vol. 2009, Article ID542040.
%H Alois P. Heinz, <a href="/A212633/b212633.txt">Rows n = 1..141, flattened</a>
%H S. Alikhani and Y. H. Peng, <a href="http://arxiv.org/abs/0905.2251"> Introduction to domination polynomial of a graph</a>, arXiv:0905.2251.
%H JL Arocha, B Llano, <a href="http://arxiv.org/abs/1601.01268">The number of dominating k-sets of paths, cycles and wheels</a>, arXiv preprint arXiv:1601.01268, 2016
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DominationPolynomial.html">Domination Polynomial</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PathGraph.html">Path Graph</a>
%F 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).
%e Row 3 is [1,3,1] because the path tree A-B-C has dominating subsets B, AB, BC, AC, and ABC.
%e Triangle starts:
%e 1;
%e 2,1;
%e 1,3,1;
%e 0,4,4,1;
%e 0,3,8,5,1;
%p 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
%t 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;
%t Array[row, 15] // Flatten (* _Jean-François Alcover_, Feb 24 2016 *)
%t CoefficientList[LinearRecurrence[{x, x, x}, {1, 2 + x, 1 + 3 x + x^2}, 10], x] // Flatten (* _Eric W. Weisstein_, Apr 07 2017 *)
%Y Cf. A000213, A212634, A212635.
%K nonn,tabl
%O 1,2
%A _Emeric Deutsch_, Jun 14 2012
|
