A113979 Number of compositions of n with an even number of 1's.

1, 0, 2, 1, 6, 6, 20, 28, 72, 120, 272, 496, 1056, 2016, 4160, 8128, 16512, 32640, 65792, 130816, 262656, 523776, 1049600, 2096128, 4196352, 8386560, 16781312, 33550336, 67117056, 134209536, 268451840, 536854528, 1073774592, 2147450880

Offset: 0

Author

Vladeta Jovovic, Jan 31 2006

Keywords

• easy
• nonn

Comments

More generally, the g.f. for the number of compositions such that part m occurs with even multiplicity is (1-x)/(1-2*x)*(1-2*x+x^m-x^(m+1))/(1-2*x+2*x^m-2*x^(m+1)). - Vladeta Jovovic, Sep 01 2007

Examples

			a(4)=6 because the compositions of 4 having an even number of 1's are 4,22,211,121,112 and 1111 (the other compositions of 4 are 31 and 13).
		

Links

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

Crossrefs

Cf. A063376, A006516, A063083, A100818, A092295, A111752, A111753, A111723, A111724, A088336, A088506.

Cf. A105422, A113980.

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

PARI

a(n) = n-=2; (n==-2) + 1<=0, (-1)^n << (n>>1)); \\ Kevin Ryde, May 02 2023

Formula

a(0) = 1, a(n) = 2^(n-2) + 2^((n-2)/2) if n is positive and even, otherwise a(n) = 2^(n-2) - 2^((n-3)/2).

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

E.g.f.: (1 + exp(2*x) - sqrt(2)*sinh(x*sqrt(2)) + 2*cosh(x*sqrt(2)))/4. - Sergei N. Gladkovskii, Nov 18 2011

a(k) = (1/4)*0^k + (1/4)*2^k + (1/8)*(2-sqrt(2))*(sqrt(2))^k + (1/8)*(2+sqrt(2))*(-sqrt(2))^k. - Sergei N. Gladkovskii, Nov 18 2011

Extensions

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

a(0)=1 prepended and formulas corrected by Jason Yuen, Sep 09 2024