cp's OEIS Frontend

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

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