cp's OEIS Frontend

A228693 Largest number of maximal independent sets of nodes in any tree on n nodes.

%I A228693 #23 Sep 08 2022 08:46:05
%S A228693 1,1,2,2,3,4,5,8,9,16,17,32,33,64,65,128,129,256,257,512,513,1024,
%T A228693 1025,2048,2049,4096,4097,8192,8193,16384,16385,32768,32769,65536,
%U A228693 65537,131072,131073,262144,262145,524288,524289,1048576,1048577,2097152,2097153,4194304,4194305,8388608,8388609,16777216,16777217
%N A228693 Largest number of maximal independent sets of nodes in any tree on n nodes.
%H A228693 Vincenzo Librandi, <a href="/A228693/b228693.txt">Table of n, a(n) for n = 0..1000</a>
%H A228693 Herbert S. Wilf, <a href="https://doi.org/10.1137/0607015">The number of maximal independent sets in a tree</a>, SIAM Journal on Algebraic and Discrete Methods, volume 7, number 1, January 1986, pages 125-130.  Also <a href="http://www.math.upenn.edu/~wilf/website/Maximal%20independent%20sets%20in%20a%20tree.pdf">author's copy</a>.
%H A228693 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (0,3,0,-2).
%F A228693 From _Colin Barker_, Sep 08 2013: (Start)
%F A228693 G.f.: -(x^4+x^3+x^2-x-1) / ((x-1)*(x+1)*(2*x^2-1)).
%F A228693 a(n) = 3*a(n-2)-2*a(n-4) for n > 4. (End)
%p A228693 f:=proc(n) if n=0 then 1
%p A228693 elif (n mod 2) = 0 then 2^((n/2)-1)+1 else 2^((n-1)/2); fi;
%p A228693 end;
%t A228693 CoefficientList[Series[-(x^4 + x^3 + x^2 - x - 1) / ((x - 1) (x + 1) (2 x^2 - 1)), {x, 0, 60}], x] (* _Vincenzo Librandi_, Sep 09 2013 *)
%o A228693 (PARI) Vec(-(x^4+x^3+x^2-x-1)/((x-1)*(x+1)*(2*x^2-1)) + O(x^100)) \\ _Colin Barker_, Sep 08 2013
%o A228693 (Magma) I:=[1,1,2,2,3]; [n le 5 select I[n] else 3*Self(n-2)-2*Self(n-4): n in [1..55]]; // _Vincenzo Librandi_, Sep 09 2013
%Y A228693 Cf. A000051, A000079 (bisections).
%K A228693 nonn,easy
%O A228693 0,3
%A A228693 _N. J. A. Sloane_, Sep 02 2013