A262126 Number of permutations p of [n] such that the up-down signature of p has nonnegative partial sums with a maximal value <= 2.

1, 1, 1, 3, 8, 40, 162, 1134, 6128, 55152, 372560, 4098160, 33220512, 431866656, 4084265360, 61263980400, 662157708032, 11256681036544, 136873417800960, 2600594938218240, 35134918875668480, 737833296389038080, 10965215649174414848, 252199959931011541504

Offset: 0

Author

Alois P. Heinz, Sep 11 2015

Keywords

• nonn

Examples

			a(0) = 1: the empty permutation.
a(1) = 1: 1.
a(2) = 1: 12.
a(3) = 3: 123, 132, 231.
a(4) = 8: 1243, 1324, 1342, 1423, 2314, 2341, 2413, 3412.
		

Links

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

Crossrefs

Column k=2 of A262124.

Programs

Maple

b:= proc(u, o, c) option remember; `if`(c<0 or c>2, 0, `if`(u+o=0, x^c,
      (p-> add(coeff(p, x, i)*x^max(i, c), i=0..2))(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-> `if`(n=0, 1, (p-> add(coeff(p, x, i), i=0..2))(
         add(b(j-1, n-j, 0), j=1..n))):
seq(a(n), n=0..30);

Mathematica

b[u_, o_, c_] := b[u, o, c] = If[c < 0 || c > 2, 0, If[u + o == 0, x^c, Function[p, Sum[Coefficient[p, x, i]*x^Max[i, c], {i, 0, 2}]][Sum[b[u - j, o - 1 + j, c - 1], {j, u}] + Sum[b[u + j - 1, o - j, c + 1], {j, o}]]]];
a[n_] := If[n == 0, 1, Function[p, Sum[Coefficient[p, x, i], {i, 0, 2}]][Sum[b[j - 1, n - j, 0], {j, n}]]];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Aug 30 2021, after Alois P. Heinz *)

Formula

a(n) = A262124(n,2).