A304001 Number of permutations of [n] whose up-down signature has a nonnegative total sum.

1, 1, 1, 5, 12, 93, 360, 3728, 20160, 259535, 1814400, 27820524, 239500800, 4251096402, 43589145600, 877606592736, 10461394944000, 235288904377275, 3201186852864000, 79476406782222500, 1216451004088320000, 33020655481590446318, 562000363888803840000

Offset

0,4

Comments

The up-down signature has (+1) for each ascent and (-1) for each descent.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..450

Maple

b:= proc(u, o, t) option remember; (n->
     `if`(t>=n, n!, `if`(t<-n, 0,
      add(b(u-j, o+j-1, t-1), j=1..u)+
      add(b(u+j-1, o-j, t+1), j=1..o))))(u+o)
    end:
a:= n-> `if`(n=0, 1, add(b(j-1, n-j, 0), j=1..n)):
seq(a(n), n=0..25);
# second Maple program:
a:= n-> `if`(irem(n, 2, 'r')=0, ceil(n!/2),
         add(combinat[eulerian1](n, j), j=0..r)):
seq(a(n), n=0..25);

Mathematica

Eulerian1[n_, k_] := If[k == 0, 1, If[n == 0, 0, Sum[(-1)^j (k - j + 1)^n Binomial[n + 1, j], {j, 0, k + 1}]]];
a[n_] := Module[{r, m}, {r, m} = QuotientRemainder[n, 2]; If[m == 0, Ceiling[n!/2], Sum[Eulerian1[n, j], {j, 0, r}]]];
a /@ Range[0, 25] (* Jean-François Alcover, Mar 26 2021, after 2nd Maple program *)

Crossrefs

Bisections give: A002674 (even part), A179457(2n+1,n+1) (odd part).

Cf. A000246 (for nonnegative partial sums), A006551 (total sums are 0 or 1), A008292, A303287.

Sequence in context: A249478 A009414 A009426 * A009731 A009427 A267271

Adjacent sequences: A303998 A303999 A304000 * A304002 A304003 A304004

Keyword

nonn

Author

Alois P. Heinz, May 04 2018

Status

approved