|
%I #36 Feb 29 2020 03:29:25
%S 0,0,0,0,0,0,604,7296,54746,330068,1756878,8641800,40298572,180969752,
%T 790697160,3385019968,14270283414,59457742524,245507935018,
%U 1006678811272,4105447763032,16672235476128,67482738851220,272439143364672,1097660274098482,4415486996246052
%N Number of permutations on [n] whose up-down signature has nonnegative partial sums and which have exactly three descents.
%C Also the number of permutations of [n] of odd order whose M statistic (as defined in the Spiro paper) is equal to three.
%H Alois P. Heinz, <a href="/A321269/b321269.txt">Table of n, a(n) for n = 1..1660</a>
%H S. Spiro, <a href="https://arxiv.org/abs/1810.00993">Ballot Permutations, Odd Order Permutations, and a New Permutation Statistic</a>, arXiv preprint arXiv:1810.00993 [math.CO], 2018.
%H <a href="/index/Rec#order_13">Index entries for linear recurrences with constant coefficients</a>, signature (24,-260,1684,-7278,22172,-49004,79596,-95065,82508,-50616,20800,-5136,576).
%F From _Sam Spiro_, Mar 07 2019: (Start)
%F 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.
%F 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.
%F 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.
%F (End)
%F From _Colin Barker_, Mar 07 2019: (Start)
%F 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)).
%F 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.
%F (End)
%e The permutations counted by a(7) include 1237654 and 17265243.
%t t[n_, k_] := Sum[(-1)^j (k - j)^n Binomial[n + 1, j], {j, 0, k}];
%t 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];
%t Array[a, 30] (* _Jean-François Alcover_, Feb 29 2020, from _Sam Spiro_'s 1st formula *)
%o (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
%Y Cf. A000246, A005803, A321268, A303285, A177042.
%Y Column k=3 of A321280.
%K nonn,easy
%O 1,7
%A _Sam Spiro_, Nov 01 2018
%E More terms from _Alois P. Heinz_, Nov 01 2018
|
