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

%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