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,3

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

Links

Table of n, a(n) for n=0..33.

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

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

Example

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

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

Prog

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

Crossrefs

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

Cf. A105422, A113980.

Sequence in context: A145883 A062820 A113336 * A053442 A019082 A345323

Adjacent sequences: A113976 A113977 A113978 * A113980 A113981 A113982

Keyword

easy,nonn

Author

Vladeta Jovovic, Jan 31 2006

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

Status

approved