%I #18 Jan 02 2021 08:00:19
%S 1,1,2,5,20,87,522,3271,26168,214955,2149550,21881103,262573236,
%T 3191361201,44679056814,631546127049,10104738032784,162891774138339,
%U 2932051934490102,53094870211027831,1061897404220556620,21342730463672017301,469540070200784380622
%N Number of permutations p of [n] such that the up-down signature of 0,p has nonnegative partial sums.
%H Alois P. Heinz, <a href="/A258830/b258830.txt">Table of n, a(n) for n = 0..200</a>
%F a(n) ~ c * n! / sqrt(n), where c = 2.03565662136472375868003536175448... . - _Vaclav Kotesovec_, Jun 21 2015
%e 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.
%e a(0) = 1: the empty permutation.
%e a(1) = 1: 1.
%e a(2) = 2: 12, 21.
%e a(3) = 5: 123, 132, 213, 231, 312.
%e a(4) = 20: 1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3241, 3412, 3421, 4123, 4132, 4231.
%p b:= proc(u, o, c) option remember;
%p `if`(c<0, 0, `if`(u+o<=c, (u+o)!,
%p add(b(u-j, o-1+j, c+1), j=1..u)+
%p add(b(u+j-1, o-j, c-1), j=1..o)))
%p end:
%p a:= n-> b(n, 0$2):
%p seq(a(n), n=0..30);
%t b[u_, o_, c_] := b[u, o, c] = If[c < 0, 0, If[u + o <= c, (u + o)!,
%t Sum[b[u - j, o - 1 + j, c + 1], {j, 1, u}] +
%t Sum[b[u + j - 1, o - j, c - 1], {j, 1, o}]]];
%t a[n_] := b[n, 0, 0];
%t a /@ Range[0, 30] (* _Jean-François Alcover_, Jan 02 2021, after _Alois P. Heinz_ *)
%Y Row sums of A258829.
%Y Main diagonal of A262163.
%Y Cf. A000246.
%K nonn
%O 0,3
%A _Alois P. Heinz_, Jun 11 2015