A058622 a(n) = 2^(n-1) - ((1+(-1)^n)/4)*binomial(n, n/2).

0, 1, 1, 4, 5, 16, 22, 64, 93, 256, 386, 1024, 1586, 4096, 6476, 16384, 26333, 65536, 106762, 262144, 431910, 1048576, 1744436, 4194304, 7036530, 16777216, 28354132, 67108864, 114159428, 268435456, 459312152, 1073741824, 1846943453

Offset: 0

Author

Yong Kong (ykong(AT)curagen.com), Dec 29 2000

Keywords

• nonn
• changed

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

Examples

			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)
		

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

Crossrefs

The odd bisection is A000302.

The even bisection is A000346.

The following relate to compositions with nonzero alternating sum:

- The complement is counted by A001700 or A138364.

- The version for alternating sum > 0 is A027306.

- The unordered version is A086543 (even bisection: A182616).

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

A103919 counts partitions by sum and alternating sum (reverse: A344612).

A345197 counts compositions by length and alternating sum.

Compositions of n, 2n, or 2n+1 with alternating/reverse-alternating sum k:

- k = 0: counted by A088218, ranked by A344619/A344619.

- k = 1: counted by A000984, ranked by A345909/A345911.

- k = -1: counted by A001791, ranked by A345910/A345912.

- k = 2: counted by A088218, ranked by A345925/A345922.

- k = -2: counted by A002054, ranked by A345924/A345923.

- k >= 0: counted by A116406, ranked by A345913/A345914.

- k > 0: counted by A027306, ranked by A345917/A345918.

- k < 0: counted by A294175, ranked by A345919/A345920.

- k even: counted by A081294, ranked by A053754/A053754.

- k odd: counted by A000302, ranked by A053738/A053738.

Cf. A000070, A000097, A007318, A008549, A034871, A114121, A120452, A163493, A210736, A239830, A344611.

Programs

Magma

[(2^n -(1+(-1)^n)*Binomial(n, Floor(n/2))/2)/2: n in [0..40]]; // G. C. Greubel, Aug 08 2022

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

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

Python

from math import comb
def A058622(n): return (1<>1)>>1) if n else 0 # Chai Wah Wu, Aug 25 2025

SageMath

[(2^n - binomial(n, n//2)*((n+1)%2))/2 for n in (0..40)] # G. C. Greubel, Aug 08 2022

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

A027306(n) - a(n) = A126869(n). - R. J. Mathar, Sep 23 2021