cp's OEIS Frontend

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

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