A262163 Number A(n,k) of permutations p of [n] such that the up-down signature of 0,p has nonnegative partial sums with a maximal value <= k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 2, 0, 1, 1, 2, 4, 5, 0, 1, 1, 2, 5, 16, 16, 0, 1, 1, 2, 5, 19, 54, 61, 0, 1, 1, 2, 5, 20, 82, 324, 272, 0, 1, 1, 2, 5, 20, 86, 454, 1532, 1385, 0, 1, 1, 2, 5, 20, 87, 516, 2795, 12256, 7936, 0, 1, 1, 2, 5, 20, 87, 521, 3135, 20346, 74512, 50521, 0

Offset

0,13

Links

Alois P. Heinz, Antidiagonals n = 0..140, flattened

Formula

A(n,k) = Sum_{i=0..k} A258829(n,i).

Example

Square array A(n,k) begins:
  1,   1,    1,    1,    1,    1,    1,    1, ...
  0,   1,    1,    1,    1,    1,    1,    1, ...
  0,   1,    2,    2,    2,    2,    2,    2, ...
  0,   2,    4,    5,    5,    5,    5,    5, ...
  0,   5,   16,   19,   20,   20,   20,   20, ...
  0,  16,   54,   82,   86,   87,   87,   87, ...
  0,  61,  324,  454,  516,  521,  522,  522, ...
  0, 272, 1532, 2795, 3135, 3264, 3270, 3271, ...

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:
A:= (n, k)-> (p-> add(coeff(p, x, i), i=0..min(n, k)))(b(0, n, 0)):
seq(seq(A(n, d-n), n=0..d), d=0..12);

Mathematica

b[u_, o_, c_] := b[u, o, c] = If[c < 0, 0, If[u + o == 0, x^c, Function[p, Sum[Coefficient[p, x, i]*x^Max[i, c], {i, 0, Exponent[p, 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}]]]]; A[n_, k_] := Function[p, Sum[Coefficient[p, x, i], {i, 0, Min[n, k]}]][b[0, n, 0]]; Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Feb 22 2016, after Alois P. Heinz *)

Crossrefs

Columns k=0-10 give: A000007, A000111 for n>0, A262164, A262165, A262166, A262167, A262168, A262169, A262170, A262171, A262172.

Main diagonal gives: A258830.

Cf. A258829, A262124.

Sequence in context: A339959 A255636 A292085 * A293112 A306910 A112185

Adjacent sequences: A262160 A262161 A262162 * A262164 A262165 A262166

Keyword

nonn,tabl

Author

Alois P. Heinz, Sep 13 2015

Status

approved