A213667 Number of dominating subsets with k vertices in all the graphs G(n) (n>=1) obtained by taking n copies of the path P_3 and identifying one of their endpoints (a star with n branches of length 2).

1, 6, 16, 40, 98, 238, 576, 1392, 3362, 8118, 19600, 47320, 114242, 275806, 665856, 1607520, 3880898, 9369318, 22619536, 54608392, 131836322, 318281038, 768398400, 1855077840, 4478554082, 10812186006, 26102926096, 63018038200, 152139002498, 367296043198

Offset

1,2

Links

Colin Barker, Table of n, a(n) for n = 1..1000

S. Alikhani and Y. H. Peng, Introduction to domination polynomial of a graph, arXiv:0905.2251 [math.CO], 2009.

É. Czabarka, L. Székely, and S. Wagner, The inverse problem for certain tree parameters, Discrete Appl. Math., 157, 2009, 3314-3319.

T. Kotek, J. Preen, F. Simon, P. Tittmann, and M. Trinks, Recurrence relations and splitting formulas for the domination polynomial, arXiv:1206.5926 [math.CO], 2012.

Index entries for linear recurrences with constant coefficients, signature (3,-1,-1).

Formula

a(1)=1, a(2)=6, a(3)=16, a(n) = 2*a(n-1) + a(n-2) + 2 for n>=4.

G.f.: (1 + x)/(1 - 2*x - x^2) - 1/(1 - x) - x.

a(k) = sum(A213666(n,k), n>=1).

a(n) = A001333(n+1)-1 for n>=2.

a(n) = (-2+(1-sqrt(2))^(1+n)+(1+sqrt(2))^(1+n))/2 for n>1. - Colin Barker, Mar 16 2016

Example

a(2)=6 because (i) the graph G(1) is the path P_3=abc with 3 dominating subsets of size 2 (ab,ac,bc); (ii) the graph G(2) is the path P_5=abcde with 3 dominating subsets of size 2 (ad,bd,be); the graphs G(n) (n>=3) do not have dominating subsets of size 2.

Maple

a := proc (n) if n = 1 then 1 elif n = 2 then 6 elif n = 3 then 16 else 2*a(n-1)+a(n-2)+2 end if end proc: seq(a(n), n = 1 .. 32);

Mathematica

Table[2 Fibonacci[n, 2] + LucasL[n, 2]/2 - KroneckerDelta[n - 1] - 1, {n, 20}] (* Vladimir Reshetnikov, Sep 16 2016 *)

Prog

(PARI) Vec(x*(1+3*x-x^2-x^3)/((1-x)*(1-2*x-x^2)) + O(x^50)) \\ Colin Barker, Mar 16 2016

Crossrefs

Cf. A001333, A213666.

Sequence in context: A300371 A009955 A160255 * A123205 A123607 A261819

Adjacent sequences: A213664 A213665 A213666 * A213668 A213669 A213670

Keyword

nonn,easy

Author

Emeric Deutsch, Jul 01 2012

Status

approved