%I M3954 N1629 #65 Feb 08 2023 16:40:07
%S 5,29,118,418,1383,4407,13736,42236,128761,390385,1179354,3554454,
%T 10696139,32153963,96592972,290041072,870647517,2612991141,7841070590,
%U 23527406090,70590606895,211788597919,635399348208,1906265153508,5718929678273,17157057470297
%N One half of the number of permutations of [n] such that the differences have three runs with the same signs.
%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 260, #13
%D F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 260.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A000352/b000352.txt">Table of n, a(n) for n = 4..400</a>
%H E. Rodney Canfield and Herbert S. Wilf, <a href="http://arXiv.org/abs/math.CO/0609704">Counting permutations by their runs up and down</a>, arXiv:math/0609704 [math.CO], 2006.
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (7,-17,17,-6).
%F a(n) = (3^n-4*2^n-2*n+11)/4, n>=4. - _Tim Monahan_, Jul 14 2011
%F G.f.: x^4*(5-6*x)/((1-3*x)*(1-2*x)*(1-x)^2).
%F Limit_{n->infinity} 4*a(n)/3^n = 1. - _Philippe Deléham_, Feb 22 2004
%e a(4)=5 because the permutations of [4] with three sign runs are 1324, 1423, 2143, 2314, 2413 and their reversals.
%p A000352:=-(-5+6*z)/(3*z-1)/(2*z-1)/(z-1)**2; # [Conjectured by _Simon Plouffe_ in his 1992 dissertation.] [correct up to offset]
%p # second Maple program:
%p a:= n-> (<<0|0|1|2>>. <<7|1|0|0>, <-17|0|1|0>, <17|0|0|1>, <-6|0|0|0>>^n)[1, 4]:
%p seq(a(n), n=4..30); # _Alois P. Heinz_, Aug 26 2008
%t nn = 40; CoefficientList[Series[x^4*(5 - 6*x)/((1 - 3*x)*(1 - 2*x)*(1 - x)^2), {x, 0, nn}], x] (* _T. D. Noe_, Jun 19 2012 *)
%o (PARI) a(n) = (3^n-4*2^n-2*n+11)/4;
%Y a(n) = T(n, 3), where T(n, k) is the array defined in A008970.
%Y Cf. A000486, A000506.
%K nonn
%O 4,1
%A _N. J. A. Sloane_
%E Edited by _Emeric Deutsch_, Feb 18 2004