A156232 a(n) is the number of induced subgraphs with odd number of edges in the cycle graph C(n).

0, 4, 4, 16, 24, 64, 112, 256, 480, 1024, 1984, 4096, 8064, 16384, 32512, 65536, 130560, 262144, 523264, 1048576, 2095104, 4194304, 8384512, 16777216, 33546240, 67108864, 134201344, 268435456, 536838144, 1073741824, 2147418112

Offset

2,2

Comments

Essentially the same sequence (see A204696) appears in the Cusick-Stanica paper.

Links

G. C. Greubel, Table of n, a(n) for n = 2..1000

Thomas W. Cusick, and Pantelimon Stanica, Fast evaluation, weights and nonlinearity of rotation-symmetric functions, Discrete Math. 258 (2002), no. 1-3, 289-301.

Index entries for linear recurrences with constant coefficients, signature (2, 2, -4).

Formula

a(n) = 2^(n-1) - 2^(n/2) if n is even, 2^(n-1) otherwise.

G.f.: 4*x^3*(1-x)/((1-2*x)*(1-2*x^2)). a(n)=2*a(n-1)+2*a(n-2)-4*a(n-3). - R. J. Mathar, Feb 10 2009

E.g.f.: 2*(exp(2*x) - cosh(sqrt(2)*x)). - G. C. Greubel, Aug 26 2015

Mathematica

RecurrenceTable[{a[n]== 2*a[n-1]  + 2*a[n-2] - 4*a[n-3], a[0]==0, a[1]==4, a[2]==4}, a, {n, 0, 50}] (* G. C. Greubel, Aug 26 2015 *)
LinearRecurrence[{2, 2, -4}, {0, 4, 4}, 40] (* Vincenzo Librandi, Aug 27 2015 *)

Prog

(PARI) Vec(4*x^3*(1-x)/((1-2*x)*(1-2*x^2)) + O(x^40)) \\ Michel Marcus, Aug 26 2015

Crossrefs

Cf. A000749, A032085.

Sequence in context: A321677 A223819 A082649 * A053441 A065732 A092959

Adjacent sequences: A156229 A156230 A156231 * A156233 A156234 A156235

Keyword

nonn

Author

Alessandro Cosentino (cosenal(AT)gmail.com), Feb 06 2009

Extensions

More terms from R. J. Mathar, Feb 10 2009

Status

approved