A294175 - OEIS

A294175

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

0, 0, 1, 1, 5, 6, 22, 29, 93, 130, 386, 562, 1586, 2380, 6476, 9949, 26333, 41226, 106762, 169766, 431910, 695860, 1744436, 2842226, 7036530, 11576916, 28354132, 47050564, 114159428, 190876696, 459312152, 773201629, 1846943453, 3128164186, 7423131482

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,5

COMMENTS

Number of subsets of {1,2,...,n} that contain more even than odd numbers.

Note that A058622 counts the nonempty subsets of {1,2,...,n} that contain more odd than even numbers.

From Gus Wiseman, Jul 22 2021: (Start)

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:

. . (12) (13) (14) (15)

(23) (24)

(131) (141)

(1112) (1113)

(1211) (1212)

(1311)

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.

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:

. . 100 1000 10000 100000

10001 100001

10010 100010

10100 100100

11000 101000

110000

(End)

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

LINKS

Table of n, a(n) for n=0..34.

Nicolle González, Pamela E. Harris, Gordon Rojas Kirby, Mariana Smit Vega Garcia, and Bridget Eileen Tenner, Pinnacle sets of signed permutations, arXiv:2301.02628 [math.CO] (2023).

FORMULA

From Robert Israel, Feb 12 2018: (Start)

G.f.: (x+1)*sqrt(1-4*x^2)/(2*x*(4*x^2-1))+(x-1)/(2*(2*x-1)*x).

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)

EXAMPLE

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

MAPLE

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

map(f, [$0..40]); # Robert Israel, Feb 12 2018

MATHEMATICA

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

Table[Length[Select[Tuples[{0, 1}, {n+1}], First[#]==1&&Count[#, 0]>Count[#, 1]&]], {n, 0, 10}] (* Gus Wiseman, Jul 22 2021 *)

CROSSREFS

The even bisection is A000346.

The odd bisection is A008549.

The following relate to compositions of n + 1 with alternating sum k < 0.

- The k = 1 version is A000984, ranked by A345909/A345911.

- The opposite (k > 0) version is A027306, ranked by A345917/A345918.

- The weak (k <= 0) version A058622, ranked by A345915/A345916.

- The k != 0 version is also A058622, ranked by A345921.

- The complement (k >= 0) is counted by A116406, ranked by A345913/A345914.

- The k = 0 version is A138364, ranked by A344619.

- The unordered version is A344608, ranked by A119899.

- Ranked by A345919 (reverse: A345920).

A097805 counts compositions by alternating (or reverse-alternating) sum.

A101211 lists run-lengths in binary expansion (reverse: A227736).

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

A345197 counts compositions by length and alternating sum.

Cf. A000070, A001700, A007318, A025047, A032443, A034871, A106356, A114121, A126869, A163493, A344743, A345908, A289871, A359066, A359067.

Sequence in context: A110344 A224915 A135301 * A369853 A370337 A192917

Adjacent sequences: A294172 A294173 A294174 * A294176 A294177 A294178

KEYWORD

nonn

AUTHOR

Enrique Navarrete, Feb 10 2018

STATUS

approved