OFFSET
0,4
COMMENTS
a(n) is the number of n-digit binary sequences that have more 1's than 0's. - Geoffrey Critzer, Jul 16 2009
Maps to the number of walks that end above 0 on the number line with steps being 1 or -1. - Benjamin Phillabaum, Mar 06 2011
Chris Godsil observes that a(n) is the independence number of the (n+1)-folded cube graph; proof is by a Cvetkovic's eigenvalue bound to establish an upper bound and a direct construction of the independent set by looking at vertices at an odd (resp., even) distance from a fixed vertex when n is odd (resp., even). - Stan Wagon, Jan 29 2013
Also the number of subsets of {1,2,...,n} that contain more odd than even numbers. For example, for n=4, a(4)=5 and the 5 subsets are {1}, {3}, {1,3}, {1,2,3}, {1,3,4}. See A014495 when same number of even and odd numbers. - Enrique Navarrete, Feb 10 2018
Also half the number of length-n binary sequences with a different number of zeros than ones. This is also the number of integer compositions of n with nonzero alternating sum, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. Also the number of integer compositions of n+1 with alternating sum <= 0, ranked by A345915 (reverse: A345916). - Gus Wiseman, Jul 19 2021
REFERENCES
A. P. Prudnikov, Yu. A. Brychkov and O.I. Marichev, "Integrals and Series", Volume 1: "Elementary Functions", Chapter 4: "Finite Sums", New York, Gordon and Breach Science Publishers, 1986-1992, Eq. (4.2.1.7)
LINKS
G. C. Greubel, Table of n, a(n) for n = 0..1000
Eric Weisstein's World of Mathematics, Folded Cube Graph
Eric Weisstein's World of Mathematics, Independence Number
FORMULA
a(n) = 2^(n-1) - ((1+(-1)^n)/4)*binomial(n, n/2).
a(n) = Sum_{i=0..floor((n-1)/2)} binomial(n, i).
G.f.: 2*x/((1-2*x)*(1+2*x+((1+2*x)*(1-2*x))^(1/2))). - Vladeta Jovovic, Apr 27 2003
E.g.f: (e^(2x)-I_0(2x))/2 where I_n is the Modified Bessel Function. - Benjamin Phillabaum, Mar 06 2011
Logarithmic derivative of the g.f. of A210736 is a(n+1). - Michael Somos, Nov 22 2014
Even index: a(2n) = 2^(n-1) - A088218(n). Odd index: a(2n+1) = 2^(2n). - Gus Wiseman, Jul 19 2021
D-finite with recurrence n*a(n) +2*(-n+1)*a(n-1) +4*(-n+1)*a(n-2) +8*(n-2)*a(n-3)=0. - R. J. Mathar, Sep 23 2021
a(n) = 2^n-A027306(n). - R. J. Mathar, Sep 23 2021
EXAMPLE
G.f. = x + x^2 + 4*x^3 + 5*x^4 + 16*x^5 + 22*x^6 + 64*x^7 + 93*x^8 + ...
From Gus Wiseman, Jul 19 2021: (Start)
The a(1) = 1 through a(5) = 16 compositions with nonzero alternating sum:
(1) (2) (3) (4) (5)
(1,2) (1,3) (1,4)
(2,1) (3,1) (2,3)
(1,1,1) (1,1,2) (3,2)
(2,1,1) (4,1)
(1,1,3)
(1,2,2)
(1,3,1)
(2,1,2)
(2,2,1)
(3,1,1)
(1,1,1,2)
(1,1,2,1)
(1,2,1,1)
(2,1,1,1)
(1,1,1,1,1)
(End)
MATHEMATICA
Table[Sum[Binomial[n, Floor[n/2 + i]], {i, 1, n}], {n, 0, 32}] (* Geoffrey Critzer, Jul 16 2009 *)
a[n_] := If[n < 0, 0, (2^n - Boole[EvenQ @ n] Binomial[n, Quotient[n, 2]])/2]; (* Michael Somos, Nov 22 2014 *)
a[n_] := If[n < 0, 0, n! SeriesCoefficient[(Exp[2 x] - BesselI[0, 2 x])/2, {x, 0, n}]]; (* Michael Somos, Nov 22 2014 *)
Table[2^(n - 1) - (1 + (-1)^n) Binomial[n, n/2]/4, {n, 0, 40}] (* Eric W. Weisstein, Mar 21 2018 *)
CoefficientList[Series[2 x/((1-2x)(1 + 2x + Sqrt[(1+2x)(1-2x)])), {x, 0, 40}], x] (* Eric W. Weisstein, Mar 21 2018 *)
ats[y_]:=Sum[(-1)^(i-1)*y[[i]], {i, Length[y]}]; Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], ats[#]!=0&]], {n, 0, 15}] (* Gus Wiseman, Jul 19 2021 *)
PROG
(PARI) a(n) = 2^(n-1) - ((1+(-1)^n)/4)*binomial(n, n\2); \\ Michel Marcus, Dec 30 2015
(PARI) my(x='x+O('x^100)); concat(0, Vec(2*x/((1-2*x)*(1+2*x+((1+2*x)*(1-2*x))^(1/2))))) \\ Altug Alkan, Dec 30 2015
(Magma) [(2^n -(1+(-1)^n)*Binomial(n, Floor(n/2))/2)/2: n in [0..40]]; // G. C. Greubel, Aug 08 2022
(SageMath) [(2^n - binomial(n, n//2)*((n+1)%2))/2 for n in (0..40)] # G. C. Greubel, Aug 08 2022
CROSSREFS
The odd bisection is A000302.
The even bisection is A000346.
The following relate to compositions with nonzero alternating sum:
- The version for alternating sum > 0 is A027306.
- The version for alternating sum < 0 is A294175.
- These compositions are ranked by A345921.
A011782 counts compositions.
A097805 counts compositions by alternating (or reverse-alternating) sum.
A345197 counts compositions by length and alternating sum.
Compositions of n, 2n, or 2n+1 with alternating/reverse-alternating sum k:
KEYWORD
nonn
AUTHOR
Yong Kong (ykong(AT)curagen.com), Dec 29 2000
STATUS
approved