login
A321268
Number of permutations on [n] whose up-down signature has nonnegative partial sums and which have exactly two descents.
3
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.
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
Column k=2 of A321280.
Sequence in context: A223775 A224407 A243143 * A086604 A041932 A125359
KEYWORD
nonn,easy
AUTHOR
Sam Spiro, Nov 01 2018
STATUS
approved