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
Examples
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, ...
Links
- Alois P. Heinz, Antidiagonals n = 0..140, flattened
Crossrefs
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)-> (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 *)
Formula
A(n,k) = Sum_{i=0..k} A258829(n,i).