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

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.

Example

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;
  ...

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

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.

Sequence in context: A208753 A118931 A101280 * A351708 A008309 A131175

Adjacent sequences: A321277 A321278 A321279 * A321281 A321282 A321283

Keyword

nonn,tabf

Author

Alois P. Heinz, Nov 01 2018

Status

approved