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

%I #50 Sep 09 2024 09:36:20

%S 1,0,2,1,6,6,20,28,72,120,272,496,1056,2016,4160,8128,16512,32640,

%T 65792,130816,262656,523776,1049600,2096128,4196352,8386560,16781312,

%U 33550336,67117056,134209536,268451840,536854528,1073774592,2147450880

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

%C 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

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

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

%F G.f.: (1-z)*(1-z-z^2)/((1-2*z)*(1-2*z^2)). - _Emeric Deutsch_, Feb 03 2006

%F 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

%F 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

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

%p 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

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

%o (PARI) a(n) = n-=2; (n==-2) + 1<<n + if(n>=0, (-1)^n << (n>>1)); \\ _Kevin Ryde_, May 02 2023

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

%Y Cf. A105422, A113980.

%K easy,nonn

%O 0,3

%A _Vladeta Jovovic_, Jan 31 2006

%E More terms from _Robert G. Wilson v_ and _Emeric Deutsch_, Feb 01 2006

%E a(0)=1 prepended and formulas corrected by _Jason Yuen_, Sep 09 2024