cp's OEIS Frontend

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

%I A213667 #25 Sep 17 2016 00:19:54
%S A213667 1,6,16,40,98,238,576,1392,3362,8118,19600,47320,114242,275806,665856,
%T A213667 1607520,3880898,9369318,22619536,54608392,131836322,318281038,
%U A213667 768398400,1855077840,4478554082,10812186006,26102926096,63018038200,152139002498,367296043198
%N 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).
%H A213667 Colin Barker, <a href="/A213667/b213667.txt">Table of n, a(n) for n = 1..1000</a>
%H A213667 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 [math.CO], 2009.
%H A213667 É. Czabarka, L. Székely, and S. Wagner, <a href="http://dx.doi.org/10.1016/j.dam.2009.07.004">The inverse problem for certain tree parameters</a>, Discrete Appl. Math., 157, 2009, 3314-3319.
%H A213667 T. Kotek, J. Preen, F. Simon, P. Tittmann, and M. Trinks, <a href="http://arxiv.org/abs/1206.5926">Recurrence relations and splitting formulas for the domination polynomial</a>, arXiv:1206.5926 [math.CO], 2012.
%H A213667 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,-1,-1).
%F A213667 a(1)=1, a(2)=6, a(3)=16, a(n) = 2*a(n-1) + a(n-2) + 2 for n>=4.
%F A213667 G.f.: (1 + x)/(1 - 2*x - x^2) - 1/(1 - x) - x.
%F A213667 a(k) = sum(A213666(n,k), n>=1).
%F A213667 a(n) = A001333(n+1)-1 for n>=2.
%F A213667 a(n) = (-2+(1-sqrt(2))^(1+n)+(1+sqrt(2))^(1+n))/2 for n>1. - _Colin Barker_, Mar 16 2016
%e A213667 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.
%p A213667 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);
%t A213667 Table[2 Fibonacci[n, 2] + LucasL[n, 2]/2 - KroneckerDelta[n - 1] - 1, {n, 20}] (* _Vladimir Reshetnikov_, Sep 16 2016 *)
%o A213667 (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
%Y A213667 Cf. A001333, A213666.
%K A213667 nonn,easy
%O A213667 1,2
%A A213667 _Emeric Deutsch_, Jul 01 2012