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

1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 2, 0, 1, 1, 1, 3, 5, 0, 1, 1, 1, 3, 8, 16, 0, 1, 1, 1, 3, 9, 40, 61, 0, 1, 1, 1, 3, 9, 44, 162, 272, 0, 1, 1, 1, 3, 9, 45, 219, 1134, 1385, 0, 1, 1, 1, 3, 9, 45, 224, 1445, 6128, 7936, 0, 1, 1, 1, 3, 9, 45, 225, 1568, 9985, 55152, 50521, 0

Offset: 0

Author

Alois P. Heinz, Sep 11 2015

Keywords

• nonn
• tabl

Examples

			p = 1423 is counted by T(4,1) because the up-down signature of p = 1423 is 1,-1,1 with partial sums 1,0,1.
q = 1432 is not counted by any T(4,k) because the up-down signature of q = 1432 is 1,-1,-1 with partial sums 1,0,-1.
A(4,1) = 5: 1324, 1423, 2314, 2413, 3412.
A(4,2) = 8: 1243, 1324, 1342, 1423, 2314, 2341, 2413, 3412.
A(4,3) = 9: 1234, 1243, 1324, 1342, 1423, 2314, 2341, 2413, 3412.
Square array A(n,k) begins:
  1,   1,    1,    1,    1,    1,    1,    1, ...
  1,   1,    1,    1,    1,    1,    1,    1, ...
  0,   1,    1,    1,    1,    1,    1,    1, ...
  0,   2,    3,    3,    3,    3,    3,    3, ...
  0,   5,    8,    9,    9,    9,    9,    9, ...
  0,  16,   40,   44,   45,   45,   45,   45, ...
  0,  61,  162,  219,  224,  225,  225,  225, ...
  0, 272, 1134, 1445, 1568, 1574, 1575, 1575, ...
		

Links

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

Crossrefs

Columns k=1-10 give: A000111, A262126, A262128, A262129, A262130, A262131, A262132, A262133, A262134, A262135.

Main diagonal gives A000246.

Cf. A258829, A262125.

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:
A:= (n,k)-> `if`(n=0, 1, (p-> add(coeff(p, x, i), i=0..min(n, k))
              )(add(b(j-1, n-j, 0), j=1..n))):
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_] := If[n==0, 1, Function[p, Sum[Coefficient[p, x, i], {i, 0, Min[n, k]}]][ Sum[b[j-1, n-j, 0], {j, 1, n}]]]; Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Feb 22 2016, after Alois P. Heinz *)

Formula

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