A321280 Number T(n,k) of permutations p of [n] with exactly k descents such that the up-down signature of p has nonnegative partial sums; triangle T(n,k), n>=0, 0<=k<=max(0,floor((n-1)/2)), read by rows.

1, 1, 1, 1, 2, 1, 8, 1, 22, 22, 1, 52, 172, 1, 114, 856, 604, 1, 240, 3488, 7296, 1, 494, 12746, 54746, 31238, 1, 1004, 43628, 330068, 518324, 1, 2026, 143244, 1756878, 5300418, 2620708, 1, 4072, 457536, 8641800, 43235304, 55717312, 1, 8166, 1434318, 40298572, 309074508, 728888188, 325024572

Offset: 0

Author

Alois P. Heinz, Nov 01 2018

Keywords

• nonn
• tabf

Examples

			Triangle T(n,k) begins:
  1;
  1;
  1;
  1,     2;
  1,     8;
  1,    22,      22;
  1,    52,     172;
  1,   114,     856,       604;
  1,   240,    3488,      7296;
  1,   494,   12746,     54746,      31238;
  1,  1004,   43628,    330068,     518324;
  1,  2026,  143244,   1756878,    5300418,    2620708;
  1,  4072,  457536,   8641800,   43235304,   55717312;
  1,  8166, 1434318,  40298572,  309074508,  728888188,  325024572;
  1, 16356, 4438540, 180969752, 2026885824, 7589067592, 8460090160;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..100, flattened
• S. Spiro, Ballot Permutations, Odd Order Permutations, and a New Permutation Statistic, arXiv preprint arXiv:1810.00993 [math.CO], 2018.
• David G. L. Wang, T. Zhao, The peak and descent statistics over ballot permutations, arXiv:2009.05973 [math.CO], 2020.

Crossrefs

Columns k=0-3 give: A000012, A005803 (for n>0), A321268, A321269.

Row sums give A000246.

T(2n+1,n) gives A177042.

T(2n+2,n) gives A303285(n+1).

Cf. A262124, A262125.

Programs

Maple

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

Mathematica

b[u_, o_, c_] := b[u, o, c] = If[c < 0, 0, If[u + o == 0, 1/x, Sum[Expand[ x*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_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][ If[n == 0, 1, b[n, 0, 1]]];
Table[T[n], {n, 0, 14}] // Flatten (* Jean-François Alcover, Dec 08 2018, after Alois P. Heinz *)