A321269 -id:A321269 - 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 *)

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

Original entry on oeis.org

0, 0, 0, 0, 22, 172, 856, 3488, 12746, 43628, 143244, 457536, 1434318, 4438540, 13611136, 41473216, 125797010, 380341580, 1147318004, 3455325600, 10394291094, 31242645420, 93853769320, 281825553760, 846030314842, 2539248578732, 7620161662556, 22865518160768

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

			Some permutations counted by a(5) include 14253 and 34521.

Sam Spiro, Table of n, a(n) for n = 1..100
S. Spiro, Ballot Permutations, Odd Order Permutations, and a New Permutation Statistic, arXiv:1810.00993 [math.CO], 2018.
Index entries for linear recurrences with constant coefficients, signature (11,-50,122,-173,143,-64,12).

Cf. A000246, A005803, A321269, A303285, A177042.

Column k=2 of A321280.

a[1] = 0; a[n_] := 2n^2 - 2n - 1 - n 2^(n-1) - 2 Binomial[n, 3] + Sum[ Binomial[n, k] (2^k - 2k), {k, 0, n}];
Table[a[n], {n, 1, 28}] (* Jean-François Alcover, Nov 11 2018 *)

a(n)={if(n<2, 0, 2*n^2 - 2*n - 1 - n*2^(n-1) - 2*binomial(n,3) + sum(k=0, n, binomial(n, k)*(2^k - 2*k)))} \\ Andrew Howroyd, Nov 01 2018

concat([0,0,0,0], Vec(2*x^5*(11 - 35*x + 32*x^2 - 6*x^3) / ((1 - x)^4*(1 - 2*x)^2*(1 - 3*x)) + O(x^40))) \\ Colin Barker, Mar 07 2019

a(n) = 3*A008292(n-1,3)- 2*binomial(n,3)+binomial(n,2)-1 for n > 1.
a(n) =   A065826(n-1,3)- 2*binomial(n,3)+binomial(n,2)-1 for n > 1.
a(n) = 3^n-3*n*2^(n-1)-2*binomial(n,3)+4*binomial(n,2)-1 for n > 1.
From Colin Barker, Mar 07 2019: (Start)
G.f.: 2*x^5*(11 - 35*x + 32*x^2 - 6*x^3) / ((1 - x)^4*(1 - 2*x)^2*(1 - 3*x)).
a(n) = 11*a(n-1) - 50*a(n-2) + 122*a(n-3) - 173*a(n-4) + 143*a(n-5) - 64*a(n-6) + 12*a(n-7) for n>8.
a(n) = -1 + 3^n - (16+9*2^n)*n/6 + 3*n^2 - n^3/3 for n>1.
(End)

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