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
KEYWORD
nonn,easy
AUTHOR
Emeric Deutsch, Jul 01 2012
STATUS
approved