login
One half of the number of permutations of [n] such that the differences have three runs with the same signs.
(Formerly M3954 N1629)
4

%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