A258830 Number of permutations p of [n] such that the up-down signature of 0,p has nonnegative partial sums.

1, 1, 2, 5, 20, 87, 522, 3271, 26168, 214955, 2149550, 21881103, 262573236, 3191361201, 44679056814, 631546127049, 10104738032784, 162891774138339, 2932051934490102, 53094870211027831, 1061897404220556620, 21342730463672017301, 469540070200784380622

Offset: 0

Author

Alois P. Heinz, Jun 11 2015

Keywords

• nonn

Examples

			p = 1432 is counted by a(4) because the up-down signature of 0,p = 01432 is 1,1,-1,-1 with partial sums 1,2,1,0.
a(0) = 1: the empty permutation.
a(1) = 1: 1.
a(2) = 2: 12, 21.
a(3) = 5: 123, 132, 213, 231, 312.
a(4) = 20: 1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3241, 3412, 3421, 4123, 4132, 4231.
		

Links

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

Crossrefs

Row sums of A258829.

Main diagonal of A262163.

Cf. A000246.

Programs

Maple

b:= proc(u, o, c) option remember;
      `if`(c<0, 0, `if`(u+o<=c, (u+o)!,
       add(b(u-j, o-1+j, c+1), j=1..u)+
       add(b(u+j-1, o-j, c-1), j=1..o)))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..30);

Mathematica

b[u_, o_, c_] := b[u, o, c] = If[c < 0, 0, If[u + o <= c, (u + o)!,
    Sum[b[u - j, o - 1 + j, c + 1], {j, 1, u}] +
    Sum[b[u + j - 1, o - j, c - 1], {j, 1, o}]]];
a[n_] := b[n, 0, 0];
a /@ Range[0, 30] (* Jean-François Alcover, Jan 02 2021, after Alois P. Heinz *)

Formula

a(n) ~ c * n! / sqrt(n), where c = 2.03565662136472375868003536175448... . - Vaclav Kotesovec, Jun 21 2015