This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A058622 #79 Aug 26 2025 00:40:31
%S A058622 0,1,1,4,5,16,22,64,93,256,386,1024,1586,4096,6476,16384,26333,65536,
%T A058622 106762,262144,431910,1048576,1744436,4194304,7036530,16777216,
%U A058622 28354132,67108864,114159428,268435456,459312152,1073741824,1846943453
%N A058622 a(n) = 2^(n-1) - ((1+(-1)^n)/4)*binomial(n, n/2).
%C A058622 a(n) is the number of n-digit binary sequences that have more 1's than 0's. - _Geoffrey Critzer_, Jul 16 2009
%C A058622 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
%C A058622 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
%C A058622 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
%C A058622 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
%D A058622 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)
%H A058622 G. C. Greubel, <a href="/A058622/b058622.txt">Table of n, a(n) for n = 0..1000</a>
%H A058622 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/FoldedCubeGraph.html">Folded Cube Graph</a>
%H A058622 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IndependenceNumber.html">Independence Number</a>
%F A058622 a(n) = 2^(n-1) - ((1+(-1)^n)/4)*binomial(n, n/2).
%F A058622 a(n) = Sum_{i=0..floor((n-1)/2)} binomial(n, i).
%F A058622 G.f.: 2*x/((1-2*x)*(1+2*x+((1+2*x)*(1-2*x))^(1/2))). - _Vladeta Jovovic_, Apr 27 2003
%F A058622 E.g.f: (e^(2x)-I_0(2x))/2 where I_n is the Modified Bessel Function. - _Benjamin Phillabaum_, Mar 06 2011
%F A058622 Logarithmic derivative of the g.f. of A210736 is a(n+1). - _Michael Somos_, Nov 22 2014
%F A058622 Even index: a(2n) = 2^(n-1) - A088218(n). Odd index: a(2n+1) = 2^(2n). - _Gus Wiseman_, Jul 19 2021
%F A058622 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
%F A058622 a(n) = 2^n-A027306(n). - _R. J. Mathar_, Sep 23 2021
%F A058622 A027306(n) - a(n) = A126869(n). - _R. J. Mathar_, Sep 23 2021
%e A058622 G.f. = x + x^2 + 4*x^3 + 5*x^4 + 16*x^5 + 22*x^6 + 64*x^7 + 93*x^8 + ...
%e A058622 From _Gus Wiseman_, Jul 19 2021: (Start)
%e A058622 The a(1) = 1 through a(5) = 16 compositions with nonzero alternating sum:
%e A058622 (1) (2) (3) (4) (5)
%e A058622 (1,2) (1,3) (1,4)
%e A058622 (2,1) (3,1) (2,3)
%e A058622 (1,1,1) (1,1,2) (3,2)
%e A058622 (2,1,1) (4,1)
%e A058622 (1,1,3)
%e A058622 (1,2,2)
%e A058622 (1,3,1)
%e A058622 (2,1,2)
%e A058622 (2,2,1)
%e A058622 (3,1,1)
%e A058622 (1,1,1,2)
%e A058622 (1,1,2,1)
%e A058622 (1,2,1,1)
%e A058622 (2,1,1,1)
%e A058622 (1,1,1,1,1)
%e A058622 (End)
%t A058622 Table[Sum[Binomial[n, Floor[n/2 + i]], {i, 1, n}], {n, 0, 32}] (* _Geoffrey Critzer_, Jul 16 2009 *)
%t A058622 a[n_] := If[n < 0, 0, (2^n - Boole[EvenQ @ n] Binomial[n, Quotient[n, 2]])/2]; (* _Michael Somos_, Nov 22 2014 *)
%t A058622 a[n_] := If[n < 0, 0, n! SeriesCoefficient[(Exp[2 x] - BesselI[0, 2 x])/2, {x, 0, n}]]; (* _Michael Somos_, Nov 22 2014 *)
%t A058622 Table[2^(n - 1) - (1 + (-1)^n) Binomial[n, n/2]/4, {n, 0, 40}] (* _Eric W. Weisstein_, Mar 21 2018 *)
%t A058622 CoefficientList[Series[2 x/((1-2x)(1 + 2x + Sqrt[(1+2x)(1-2x)])), {x, 0, 40}], x] (* _Eric W. Weisstein_, Mar 21 2018 *)
%t A058622 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 *)
%o A058622 (PARI) a(n) = 2^(n-1) - ((1+(-1)^n)/4)*binomial(n, n\2); \\ _Michel Marcus_, Dec 30 2015
%o A058622 (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
%o A058622 (Magma) [(2^n -(1+(-1)^n)*Binomial(n, Floor(n/2))/2)/2: n in [0..40]]; // _G. C. Greubel_, Aug 08 2022
%o A058622 (SageMath) [(2^n - binomial(n, n//2)*((n+1)%2))/2 for n in (0..40)] # _G. C. Greubel_, Aug 08 2022
%o A058622 (Python)
%o A058622 from math import comb
%o A058622 def A058622(n): return (1<<n-1)-(0 if n&1 else comb(n,n>>1)>>1) if n else 0 # _Chai Wah Wu_, Aug 25 2025
%Y A058622 The odd bisection is A000302.
%Y A058622 The even bisection is A000346.
%Y A058622 The following relate to compositions with nonzero alternating sum:
%Y A058622 - The complement is counted by A001700 or A138364.
%Y A058622 - The version for alternating sum > 0 is A027306.
%Y A058622 - The unordered version is A086543 (even bisection: A182616).
%Y A058622 - The version for alternating sum < 0 is A294175.
%Y A058622 - These compositions are ranked by A345921.
%Y A058622 A011782 counts compositions.
%Y A058622 A097805 counts compositions by alternating (or reverse-alternating) sum.
%Y A058622 A103919 counts partitions by sum and alternating sum (reverse: A344612).
%Y A058622 A345197 counts compositions by length and alternating sum.
%Y A058622 Compositions of n, 2n, or 2n+1 with alternating/reverse-alternating sum k:
%Y A058622 - k = 0: counted by A088218, ranked by A344619/A344619.
%Y A058622 - k = 1: counted by A000984, ranked by A345909/A345911.
%Y A058622 - k = -1: counted by A001791, ranked by A345910/A345912.
%Y A058622 - k = 2: counted by A088218, ranked by A345925/A345922.
%Y A058622 - k = -2: counted by A002054, ranked by A345924/A345923.
%Y A058622 - k >= 0: counted by A116406, ranked by A345913/A345914.
%Y A058622 - k > 0: counted by A027306, ranked by A345917/A345918.
%Y A058622 - k < 0: counted by A294175, ranked by A345919/A345920.
%Y A058622 - k even: counted by A081294, ranked by A053754/A053754.
%Y A058622 - k odd: counted by A000302, ranked by A053738/A053738.
%Y A058622 Cf. A000070, A000097, A007318, A008549, A034871, A114121, A120452, A163493, A210736, A239830, A344611.
%K A058622 nonn,changed
%O A058622 0,4
%A A058622 Yong Kong (ykong(AT)curagen.com), Dec 29 2000