login
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.
4

%I #25 Dec 16 2020 19:15:19

%S 1,1,1,1,2,1,8,1,22,22,1,52,172,1,114,856,604,1,240,3488,7296,1,494,

%T 12746,54746,31238,1,1004,43628,330068,518324,1,2026,143244,1756878,

%U 5300418,2620708,1,4072,457536,8641800,43235304,55717312,1,8166,1434318,40298572,309074508,728888188,325024572

%N 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.

%H Alois P. Heinz, <a href="/A321280/b321280.txt">Rows n = 0..100, flattened</a>

%H S. Spiro, <a href="https://arxiv.org/abs/1810.00993">Ballot Permutations, Odd Order Permutations, and a New Permutation Statistic</a>, arXiv preprint arXiv:1810.00993 [math.CO], 2018.

%H David G. L. Wang, T. Zhao, <a href="https://arxiv.org/abs/2009.05973">The peak and descent statistics over ballot permutations</a>, arXiv:2009.05973 [math.CO], 2020.

%e Triangle T(n,k) begins:

%e 1;

%e 1;

%e 1;

%e 1, 2;

%e 1, 8;

%e 1, 22, 22;

%e 1, 52, 172;

%e 1, 114, 856, 604;

%e 1, 240, 3488, 7296;

%e 1, 494, 12746, 54746, 31238;

%e 1, 1004, 43628, 330068, 518324;

%e 1, 2026, 143244, 1756878, 5300418, 2620708;

%e 1, 4072, 457536, 8641800, 43235304, 55717312;

%e 1, 8166, 1434318, 40298572, 309074508, 728888188, 325024572;

%e 1, 16356, 4438540, 180969752, 2026885824, 7589067592, 8460090160;

%e ...

%p b:= proc(u, o, c) option remember; `if`(c<0, 0, `if`(u+o=0, 1/x,

%p add(expand(x*b(u-j, o-1+j, c-1)), j=1..u)+

%p add(b(u+j-1, o-j, c+1), j=1..o)))

%p end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(`if`(n=0, 1, b(n, 0, 1))):

%p seq(T(n), n=0..14);

%t 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 T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][ If[n == 0, 1, b[n, 0, 1]]];

%t Table[T[n], {n, 0, 14}] // Flatten (* _Jean-François Alcover_, Dec 08 2018, after _Alois P. Heinz_ *)

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

%Y Row sums give A000246.

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

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

%Y Cf. A262124, A262125.

%K nonn,tabf

%O 0,5

%A _Alois P. Heinz_, Nov 01 2018