A113980 Number of compositions of n with an odd number of 1's.

1, 0, 3, 2, 10, 12, 36, 56, 136, 240, 528, 992, 2080, 4032, 8256, 16256, 32896, 65280, 131328, 261632, 524800, 1047552, 2098176, 4192256, 8390656, 16773120, 33558528, 67100672, 134225920, 268419072, 536887296, 1073709056, 2147516416

Offset: 1

Author

Vladeta Jovovic, Jan 31 2006

Keywords

• easy
• nonn

Examples

			a(4)=2 because only the compositions 31 and 13 of 4 have an odd number of 1's (the other compositions are 4,22,211,121,112 and 1111).
		

Links

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

Crossrefs

Cf. A020522, A007582, A063083, A100818, A092295, A111752, A111753, A111723, A111724, A088336, A088506.

Cf. A105422.

Programs

Maple

a:=proc(n) if n mod 2 = 0 then 2^(n-2)-2^((n-2)/2) else 2^(n-2)+2^((n-3)/2) fi end: seq(a(n),n=1..38); # Emeric Deutsch, Feb 01 2006

Mathematica

f[n_] := If[EvenQ[n], 2^(n - 2) - 2^((n - 2)/2), 2^(n - 2) + 2^((n - 3)/2)]; Array[f, 34] (* Robert G. Wilson v, Feb 01 2006 *)

Formula

a(n) = 2^(n-2)-2^((n-2)/2) if n is even, else a(n) = 2^(n-2)+2^((n-3)/2).

G.f.: z(1-z)^2/[(1-2z)(1-2z^2)]. - Emeric Deutsch, Feb 03 2006

G.f.: 1 + x + Q(0), where Q(k)= 1 - 1/(2^k - 2*x*2^(2*k)/(2*x*2^k - 1/(1 + 1/(2*2^k - 8*x*2^(2*k)/(4*x*2^k + 1/Q(k+1)))))); (continued fraction). - Sergei N. Gladkovskii, May 22 2013

Extensions

More terms from Robert G. Wilson v and Emeric Deutsch, Feb 01 2006