A262125 Number T(n,k) of permutations p of [n] such that the up-down signature of p has nonnegative partial sums with a maximal value of k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 1, 0, 0, 1, 0, 0, 2, 1, 0, 0, 5, 3, 1, 0, 0, 16, 24, 4, 1, 0, 0, 61, 101, 57, 5, 1, 0, 0, 272, 862, 311, 123, 6, 1, 0, 0, 1385, 4743, 3857, 778, 254, 7, 1, 0, 0, 7936, 47216, 27589, 14126, 1835, 514, 8, 1, 0, 0, 50521, 322039, 355751, 111811, 47673, 4189, 1031, 9, 1, 0

Offset: 0

Author

Alois P. Heinz, Sep 11 2015

Keywords

• nonn
• tabl

Examples

			T(4,1) = 5: 1324, 1423, 2314, 2413, 3412.
T(4,2) = 3: 1243, 1342, 2341.
T(4,3) = 1: 1234.
Triangle T(n,k) begins:
  1;
  1,    0;
  0,    1,    0;
  0,    2,    1,    0;
  0,    5,    3,    1,   0;
  0,   16,   24,    4,   1,   0;
  0,   61,  101,   57,   5,   1, 0;
  0,  272,  862,  311, 123,   6, 1, 0;
  0, 1385, 4743, 3857, 778, 254, 7, 1, 0;
		

Links

• Alois P. Heinz, Rows n = 0..100, flattened

Crossrefs

Columns k=1-10 give: A000111 (for n>1), A320976, A320977, A320978, A320979, A320980, A320981, A320982, A320983, A320984.

Row sums give A000246.

T(2n,n) gives A262127.

Cf. A258829, A262124.

Programs

Maple

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

Mathematica

b[u_, o_, c_] := b[u, o, c] = If[c<0, 0, If[u+o==0, x^c, Sum[Coefficient[ #, x, i]*x^Max[i, c], {i, 0, Exponent[#, x]}]]& @ Sum[b[u-j, o-1+j, c-1], {j, 1, u}] + Sum[b[u+j-1, o-j, c+1], {j, 1, o}]];
T[n_] := If[n==0, {1}, Table[Coefficient[#, x, i], {i, 0, n}]]& @ Sum[b[j-1, n-j, 0], {j, 1, n}];
T /@ Range[0, 10] // Flatten (* Jean-François Alcover, Jan 19 2020, after Alois P. Heinz *)

Formula

T(n,k) = A262124(n,k) - A262124(n,k-1) for k>0, T(n,0) = A262124(n,0).