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

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

Comments

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

Links

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

Formula

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)

Example

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

Mathematica

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

Prog

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

Crossrefs

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

Column k=2 of A321280.

Sequence in context: A223775 A224407 A243143 * A086604 A041932 A125359

Adjacent sequences: A321265 A321266 A321267 * A321269 A321270 A321271

Keyword

nonn,easy

Author

Sam Spiro, Nov 01 2018

Status

approved