A177485 - OEIS

%I #15 Sep 22 2024 19:13:25

%S 1,2,3,5,7,11,15,23,32,49,69,105,149,225,321,482,691,1033,1487,2215,

%T 3199,4751,6880,10193,14793,21873,31801,46945,68353,100770,146899,

%U 216333,315671,464467,678287,997287,1457344,2141473,3131021,4598617,6726509,9875521

%N G.f.: (1+x+x^3+x^5)/( (1-x^2+x^3)*(1-x-x^3) ).

%C This counts independent sets in certain graphs.

%H S. Kitaev and A. Burstein, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Kitaev/kitaev45.html">Counting independent sets on path-schemes</a> Journal of Integer Sequences 9, no. 2 (2006), Article 06.2.2

%H <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,-1,1,-1,1).

%e For n=4, a(4)=7 because the graph is a cycle, and the independent sets are the empty set, {1}, {2}, {3}, {4}, {1,3} and {2,4}.

%t CoefficientList[Series[(1+x+x^3+x^5)/( (1-x^2+x^3)*(1-x-x^3) ), {x, 0, 40}], x] (* _Vaclav Kotesovec_, Aug 25 2014 *)

%t LinearRecurrence[{1,1,-1,1,-1,1},{1,2,3,5,7,11},50] (* _Harvey P. Dale_, Sep 22 2024 *)

%o (PARI) Vec((1+x+x^3+x^5)/((1-x^2+x^3)*(1-x-x^3)) + O(x^50)) \\ _Michel Marcus_, May 24 2015

%K nonn

%O 0,2

%A Signy Olafsdottir (signy06(AT)ru.is), May 09 2010

%E Edited by _N. J. A. Sloane_, May 18 2010

%E More terms from _Vaclav Kotesovec_, Aug 25 2014