%I #40 Jan 09 2023 15:39:00
%S 0,0,1,1,5,6,22,29,93,130,386,562,1586,2380,6476,9949,26333,41226,
%T 106762,169766,431910,695860,1744436,2842226,7036530,11576916,
%U 28354132,47050564,114159428,190876696,459312152,773201629,1846943453,3128164186,7423131482
%N a(n) = 2^(n-1) + ((1+(-1)^n)/4)*binomial(n, n/2) - binomial(n, floor(n/2)).
%C Number of subsets of {1,2,...,n} that contain more even than odd numbers.
%C Note that A058622 counts the nonempty subsets of {1,2,...,n} that contain more odd than even numbers.
%C From _Gus Wiseman_, Jul 22 2021: (Start)
%C Also the number of integer compositions of n + 1 with alternating sum < 0, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. For example, the a(0) = 0 through a(6) = 6 compositions (empty columns indicated by dots) are:
%C . . (12) (13) (14) (15)
%C (23) (24)
%C (131) (141)
%C (1112) (1113)
%C (1211) (1212)
%C (1311)
%C Also the number of integer compositions of n + 1 with reverse-alternating sum < 0. For a bijection, keep the odd-length compositions and reverse the even-length ones.
%C Also the number of (n+1)-digit binary numbers with more 0's than 1's. For example, the a(0) = 0 through a(5) = 6 binary numbers are:
%C . . 100 1000 10000 100000
%C 10001 100001
%C 10010 100010
%C 10100 100100
%C 11000 101000
%C 110000
%C (End)
%C 2*a(n) is the number of all-positive pinnacle sets that are admissible in the group S_{n+1}^B of signed permutations, but not admissible in S_{n+1}. - _Bridget Tenner_, Jan 06 2023
%H Nicolle González, Pamela E. Harris, Gordon Rojas Kirby, Mariana Smit Vega Garcia, and Bridget Eileen Tenner, <a href="https://arxiv.org/abs/2301.02628">Pinnacle sets of signed permutations</a>, arXiv:2301.02628 [math.CO] (2023).
%F From _Robert Israel_, Feb 12 2018: (Start)
%F G.f.: (x+1)*sqrt(1-4*x^2)/(2*x*(4*x^2-1))+(x-1)/(2*(2*x-1)*x).
%F D-finite with recurrence: (8+8*n)*a(n)+(4*n+16)*a(1+n)+(-20-6*n)*a(n+2)+(-5-n)*a(n+3)+(5+n)*a(n+4) = 0. (End)
%e For example, for n=5, a(5)=6 and the 6 subsets are {2}, {4}, {2,4}, {1,2,4}, {2,3,4}, {2,4,5}.
%p f:= gfun:-rectoproc({(8+8*n)*a(n)+(4*n+16)*a(1+n)+(-20-6*n)*a(n+2)+(-5-n)*a(n+3)+(5+n)*a(n+4), a(0) = 0, a(1) = 0, a(2) = 1, a(3) = 1}, a(n), remember):
%p map(f, [$0..40]); # _Robert Israel_, Feb 12 2018
%t f[n_] := 2^(n - 1) + ((1 + (-1)^n)/4) Binomial[n, n/2] - Binomial[n, Floor[n/2]]; Array[f, 38, 0] (* _Robert G. Wilson v_, Feb 10 2018 *)
%t Table[Length[Select[Tuples[{0,1},{n+1}],First[#]==1&&Count[#,0]>Count[#,1]&]],{n,0,10}] (* _Gus Wiseman_, Jul 22 2021 *)
%Y The even bisection is A000346.
%Y The odd bisection is A008549.
%Y The following relate to compositions of n + 1 with alternating sum k < 0.
%Y - The k = 1 version is A000984, ranked by A345909/A345911.
%Y - The opposite (k > 0) version is A027306, ranked by A345917/A345918.
%Y - The weak (k <= 0) version A058622, ranked by A345915/A345916.
%Y - The k != 0 version is also A058622, ranked by A345921.
%Y - The complement (k >= 0) is counted by A116406, ranked by A345913/A345914.
%Y - The k = 0 version is A138364, ranked by A344619.
%Y - The unordered version is A344608, ranked by A119899.
%Y - Ranked by A345919 (reverse: A345920).
%Y A097805 counts compositions by alternating (or reverse-alternating) sum.
%Y A101211 lists run-lengths in binary expansion (reverse: A227736).
%Y A103919 counts partitions by sum and alternating sum (reverse: A344612).
%Y A345197 counts compositions by length and alternating sum.
%Y Cf. A000070, A001700, A007318, A025047, A032443, A034871, A106356, A114121, A126869, A163493, A344743, A345908, A289871, A359066, A359067.
%K nonn
%O 0,5
%A _Enrique Navarrete_, Feb 10 2018