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

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

Comments

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

Links

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

Formula

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)

Example

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

Mathematica

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

Prog

(PARI) 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

Crossrefs

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

Column k=3 of A321280.

Sequence in context: A031792 A020383 A234109 * A234343 A234338 A250969

Adjacent sequences: A321266 A321267 A321268 * A321270 A321271 A321272

Keyword

nonn,easy

Author

Sam Spiro, Nov 01 2018

Extensions

More terms from Alois P. Heinz, Nov 01 2018

Status

approved