The OEIS is supported by the many generous donors to the OEIS Foundation. Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 60th year, we have over 367,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”). Other ways to Give
 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 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 = x; p = 2*x + x^2; p = 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 Cf. A000213, A212634, A212635. Sequence in context: A146014 A344824 A226173 * A202241 A248156 A352780 Adjacent sequences: A212630 A212631 A212632 * A212634 A212635 A212636 KEYWORD nonn,tabl AUTHOR Emeric Deutsch, Jun 14 2012 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified December 3 17:32 EST 2023. Contains 367540 sequences. (Running on oeis4.)