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

Links

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

Formula

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

Example

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;

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

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.

Sequence in context: A079508 A057150 A185663 * A360068 A105868 A371568

Adjacent sequences: A262122 A262123 A262124 * A262126 A262127 A262128

Keyword

nonn,tabl

Author

Alois P. Heinz, Sep 11 2015

Status

approved