A321268 -id:A321268 - cp's OEIS frontend

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

Alois P. Heinz, Nov 01 2018

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

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.

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.

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

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

A321269 Number of permutations on [n] whose up-down signature has nonnegative partial sums and which have exactly three descents.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 604, 7296, 54746, 330068, 1756878, 8641800, 40298572, 180969752, 790697160, 3385019968, 14270283414, 59457742524, 245507935018, 1006678811272, 4105447763032, 16672235476128, 67482738851220, 272439143364672, 1097660274098482, 4415486996246052

Offset: 1

Sam Spiro, Nov 01 2018

Also the number of permutations of [n] of odd order whose M statistic (as defined in the Spiro paper) is equal to three.

			The permutations counted by a(7) include 1237654 and 17265243.

Alois P. Heinz, Table of n, a(n) for n = 1..1660
S. Spiro, Ballot Permutations, Odd Order Permutations, and a New Permutation Statistic, arXiv preprint arXiv:1810.00993 [math.CO], 2018.
Index entries for linear recurrences with constant coefficients, signature (24,-260,1684,-7278,22172,-49004,79596,-95065,82508,-50616,20800,-5136,576).

Cf. A000246, A005803, A321268, A303285, A177042.

Column k=3 of A321280.

t[n_, k_] := Sum[(-1)^j (k - j)^n Binomial[n + 1, j], {j, 0, k}];
a[n_] := If[n<7, 0, 4 t[n-1, 4] - (Binomial[n, 3] - Binomial[n, 2] + 4) * 2^(n-2) - 22 Binomial[n, 5] + 16 Binomial[n, 4] - 4 Binomial[n, 3] + 2n];
Array[a, 30] (* Jean-François Alcover, Feb 29 2020, from Sam Spiro's 1st formula *)

concat([0,0,0,0,0,0], Vec(2*x^7*(302 - 3600*x + 18341*x^2 - 52006*x^3 + 89327*x^4 - 94728*x^5 + 61016*x^6 - 23368*x^7 + 5424*x^8 - 576*x^9) / ((1 - x)^6*(1 - 2*x)^4*(1 - 3*x)^2*(1 - 4*x)) + O(x^30))) \\ Colin Barker, Mar 07 2019

From Sam Spiro, Mar 07 2019: (Start)
a(n) = 4*A008292(n-1,4)-(binomial(n,3)-binomial(n,2)+4)*2^(n-2)-22*binomial(n,5)+16*binomial(n,4)-4*binomial(n,3)+2n for n>3.
a(n) = A065826(n-1,4)-(binomial(n,3)-binomial(n,2)+4)*2^(n-2)-22*binomial(n,5)+16*binomial(n,4)-4*binomial(n,3)+2n for n>3.
a(n) = 4^n-4*n*3^(n-1)+9*binomial(n,2)*2^(n-2)-binomial(n,3)*2^(n-2)-2^n-8*binomial(n,3)-22*binomial(n,5)+16*binomial(n,4)+2*n for n>3.
(End)
From Colin Barker, Mar 07 2019: (Start)
G.f.: 2*x^7*(302 - 3600*x + 18341*x^2 - 52006*x^3 + 89327*x^4 - 94728*x^5 + 61016*x^6 - 23368*x^7 + 5424*x^8 - 576*x^9) / ((1 - x)^6*(1 - 2*x)^4*(1 - 3*x)^2*(1 - 4*x)).
a(n) = 24*a(n-1) - 260*a(n-2) + 1684*a(n-3) - 7278*a(n-4) + 22172*a(n-5) - 49004*a(n-6) + 79596*a(n-7) - 95065*a(n-8) + 82508*a(n-9) - 50616*a(n-10) + 20800*a(n-11) - 5136*a(n-12) + 576*a(n-13) for n>16.
(End)

More terms from Alois P. Heinz, Nov 01 2018

cp's OEIS Frontend

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A321269 Number of permutations on [n] whose up-down signature has nonnegative partial sums and which have exactly three descents.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions