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,3

Links

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

Formula

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

Example

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.

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 *)

Crossrefs

Row sums of A258829.

Main diagonal of A262163.

Cf. A000246.

Sequence in context: A262170 A262171 A262172 * A002484 A280102 A366452

Adjacent sequences: A258827 A258828 A258829 * A258831 A258832 A258833

Keyword

nonn

Author

Alois P. Heinz, Jun 11 2015

Status

approved